Gowers' clique-difference conjecture for graphs

Let δ>0\delta>0. Consider the collection of non-oriented graphs on the vertex set [n][n], with density measured relative to the number of such graphs. Gowers' clique-difference conjecture. For nn large enough depending on δ\delta, every subset of this collection with density at least δ\delta contains distinct graphs (H,G)(H,G) such that HH is a subgraph of GG and the complement of HH inside GG is a clique. This is presented as a graph-theoretic conjecture related to the square-difference conjecture; the supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

Thomas Karam, “Three applications of coverings to difference patterns”, arXiv:2408.06812 (2024).

Additional references

4 papers in this index state this conjecture (2020–2024). The statement above is taken from the most recent of them; the others are arXiv:2306.14682, arXiv:2102.10686, arXiv:2011.04039.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.