Füredi–Hajnal conjecture for arbitrary forbidden patterns

Let P{0,1}k×lP\in\{0,1\}^{k\times l} be any forbidden pattern, and let G(P)G(P) be its unordered bipartite graph. Let Ex(P,n)\operatorname{Ex}(P,n) denote the maximum number of ones in an n×nn\times n matrix avoiding PP, and let ExTur(G(P),n)\operatorname{Ex}_{\mathit{Tur}}(G(P),n) denote the Turán extremal function of G(P)G(P). Füredi–Hajnal logarithmic conjecture. One should have

Ex(P,n)=O(ExTur(G(P),n)logn).\operatorname{Ex}(P,n)=O\bigl(\operatorname{Ex}_{\mathit{Tur}}(G(P),n)\log n\bigr).

Pach and Tardos refuted this conjecture in 2005, so it is no longer open.

Sources & referencesView supporting material

Primary source

Seth Pettie and Gábor Tardos, “A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices”, arXiv:2407.02638 (2024).

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.