UCL Discovery Stage
UCL home » Library Services » Electronic resources » UCL Discovery Stage

Two approaches to Sidorenko's conjecture

Kim, JH; Lee, C; Lee, J; (2015) Two approaches to Sidorenko's conjecture. Transactions of the American Mathematical Society , 368 (7) pp. 5057-5074. 10.1090/tran/6487. Green open access

[thumbnail of 2approaches.pdf]
Preview
Text
2approaches.pdf - Accepted Version

Download (472kB) | Preview

Abstract

Sidorenko’s conjecture states that for every bipartite graph H on {1, · · · , k} Z Y (i,j)∈E(H) h(xi , yj )dµ|V (H)| ≥ �Z h(x, y) dµ2 �|E(H)| holds, where µ is the Lebesgue measure on [0, 1] and h is a bounded, nonnegative, 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˝os-R´enyi 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 [3]. 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 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.

Type: Article
Title: Two approaches to Sidorenko's conjecture
Open access status: An open access version is available from UCL Discovery
DOI: 10.1090/tran/6487
Publisher version: https://doi.org/10.1090/tran/6487
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
URI: https://discovery-pp.ucl.ac.uk/id/eprint/10120246
Downloads since deposit
1,980Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item