A Caltech Library Service

Sidorenko's conjecture for blow-ups

Conlon, David and Lee, Joonkyung (2018) Sidorenko's conjecture for blow-ups. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
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.
Funding AgencyGrant Number
European Research Council (ERC)676632
European Research Council (ERC)724903
Record Number:CaltechAUTHORS:20190819-170928301
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98031
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 23:11
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page