2013/10/16 by Kim, Jeong Han, Lee, Choongbum, Lee, Joonkyung · 4 citations
#Combinatorics (math.CO) #FOS: Mathematics #Functional Analysis (math.FA)
paper · doi:10.48550/arxiv.1310.4383
Sidorenko's conjecture states that for every bipartite graph H on \1,⋯,k\, ∫ ∏(i,j)∈ E(H) h(xi, yj) dμ|V(H)| ≥ ( ∫ h(x,y) dμ2 )|E(H)| holds, where μ is the Lebesgue measure on [0,1] and h is a bounded, non-negative, symmetric, measurable function on [0,1]2. An equivalent discrete form of the conjecture is 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 Erdős-Rényi random graph with the same expected edge density as G. In this paper, 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. In particular, this implies that Sidorenko's conjecture holds if there are two vertices a1, a2 in A such that each vertex a ∈ A satisfies N(a) ⊆ N(a1) or N(a) ⊆ N(a2), and also implies a recent result of Conlon, Fox, and Sudakov \citeCoFoSu. Second, if T is a tree and H is a bipartite graph satisfying Sidorenko's conjecture, then it is shown that the Cartesian product T \Box H of T and H also satisfies Sidorenko's conjecture. This result implies that, for all d ≥ 2, the d-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture.