Sidorenko’s Conjecture for Blow-ups

David Conlon, Joonkyung Lee

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

Abstract

A celebrated conjecture of Sidorenko and Erdos–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 Hp A 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 Lp-version of Sidorenko’s conjecture holds for H.

Original languageEnglish
Article number2
JournalDiscrete Analysis
Volume2021
DOIs
Publication statusPublished - 2021

Bibliographical note

Publisher Copyright:
© 2021. David Conlon, Joonkyung Lee

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Sidorenko’s Conjecture for Blow-ups'. Together they form a unique fingerprint.

Cite this