Title: Two Approaches to Sidorenko's Conjecture
Speaker: Choongbum Lee, MIT
Date: Tuesday, October 29, 2013 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Sidorenko's conjecture states that the number of homomorphisms from a bipartite graph H to a graph G is asymptotically at least the expected number of homomorphisms from H to the binomial random graph with the same expected edge density as G. In this talk, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph H with bipartition (A, B) is tree-arrangeable if neighborhoods of vertices in A have a certain tree-like structure. We show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. This generalizes a recent result of Conlon, Fox, and Sudakov that Sidorenko's conjecture holds if A has a vertex adjacent to all vertices in B. Second, we develop a recursive procedure that constructs a new graph that satisfies Sidorenko's conjecture from a graph known to satisfy Sidorenko's conjecture. This approach yields a simple proof of the statement that hypercubes satisfy Sidorenko's conjecture, which was first proven by Hatami. Joint w/ Jeong Han Kim (KIAS) and Joonkyung Lee (Oxford)
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math