Monday, December 2, 2013
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
Problems related to Hamilton cycles have long been between the most central in Graph Theory, with great many beautiful results accumulated over the years, complemented by a large and attractive set of conjectures. In this talk I will describe a general approach to a variety of Hamiltonicity-related problems (counting and packing) in undirected and directed graphs. This approach is based on estimates of permanents of non-negative matrices (the famous Minc and van der Waerden conjectures, that became theorems of Bregman, and of Egorychev and of Falikman, respectively). A joint work with Asaf Ferber (Tel Aviv/ETH) and Benny Sudakov (UCLA/ETH).
Colloquium - 16:00
For two graphs H and G, the H-density of G is the fraction of all one-to-one mappings from the vertices of H to the vertices of G that map edges of H to edges of G. Sidorenko's conjecture asserts that for a fixed bipartite graph H, the N-vertex random graph with edge density p attains the minimum H-density among all N-vertex graphs with edge density p. Equivalently, for any graph H with m edges and any graph G, the H-density of G is at least p^m, where p is the edge density of G. The assumption on H being bipartite is easily seen to be necessary, since bipartite graphs G may have edge density up to 1/2, but contain no triangle. Despite much attention the conjecture is known to be true only for some special graph classes. Sidorenko proved the conjecture in 1993 for a particular class of graphs, including complete bipartite graphs, trees and even cycles. In 2010, Hatami showed that all cubes satisfy the Sidorenko conjecture. In the same year, Conlon, Fox and Sudakov proved the conjecture for bipartite H if H has a vertex complete to the other part, using the powerful tool of dependent random choice. They also deduced an approximate version of Sidorenko's conjecture. Recently, Li and Szegedy gave an analytic proof using the language of graph limits, for a class of graphs that includes all previous settled special cases (as a proper subset).
In the talk, I plan to give an overview of the history on Sidorenko's conjecture, sketch the proof by Conlon, Fox and Sudakov, and explain some of the ideas that Li and Szegedy used.