## Abstract

Sidorenko’s conjecture states that for every bipartite graph H on {1,· ·, k} (Formula Presented) 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ő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 a_{1}, a_{2} in A such that each vertex a ∈ A satisfies N(a) ⊆ N(a_{1}) or N(a) ⊆ N(a_{2}), and also implies a recent result of Conlon, Fox, and Sudakov (2010). 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.

Original language | English |
---|---|

Pages (from-to) | 5057-5074 |

Number of pages | 18 |

Journal | Transactions of the American Mathematical Society |

Volume | 368 |

Issue number | 7 |

DOIs | |

Publication status | Published - 2016 Jul |

### Bibliographical note

Publisher Copyright:© 2015 American Mathematical Society.

## All Science Journal Classification (ASJC) codes

- General Mathematics
- Applied Mathematics