Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 20, 2019 | Submitted
Report Open

Sidorenko's conjecture for blow-ups


A celebrated conjecture of Sidorenko and Erdős-Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion. Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A ∪ B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A ∪ B, there is a positive integer p such that the blow-up H_(A)^(p) formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Another way of viewing this latter result is that for every bipartite H there is a positive integer p such that an L^(p)-version of Sidorenko's conjecture holds for H.

Additional Information

Conlon research supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. Lee research supported by ERC Consolidator Grant PEPCo 724903. We are greatly indebted to Yufei Zhao and also to Leonardo Nagami Coregliano and Sasha Razborov for spotting a substantial error in an earlier version of this paper. The upshot of the resulting changes is the divisibility condition in Theorem 1.1, which was not present in the previous version. This paper was partially written while the second author was working as a postdoctoral research associate at the University of Oxford and he would like to acknowledge the support of ERC Starting Grant 676632 during that period.

Attached Files

Submitted - 1809.01259.pdf


Files (177.8 kB)
Name Size Download all
177.8 kB Preview Download

Additional details

August 19, 2023
October 18, 2023