Georgia Institute of Technology College of Sciences

Sidorenko's conjecture states that the number of homomorphisms from a bipartite graph $H$ to a graph $G$ is 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, I will present two approaches to the conjecture. First, I will introduce the notion of tree-arrangeability, where a bipartite graph $H$ with bipartition $A \cup B$ is tree-arrangeable if neighborhoods of vertices in $A$ have a certain tree-like structure, and show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices $a_1, a_2$ in $A$ such that each vertex $a \in A$ satisfies $N(a) \subseteq N(a_1)$ or $N(a) \subseteq N(a_2)$. Second, I will prove that if $T$ is a tree and $H$ is a bipartite graph satisfying Sidorenko's conjecture, then the Cartesian product of $T$ and $H$ also satisfies Sidorenko's conjecture. This result implies that, for all $d \ge 2$, the $d$-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture. Joint work w/ Jeong Han Kim (KIAS) and Joonkyung Lee (Oxford).