Monday, December 2, 2013
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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.