Füredi–Hajnal conjecture for acyclic patterns

At least 1 year old · documented by

Let P∈{0,1}k×lP\in\{0,1\}^{k\times l} be an acyclic forbidden pattern, and let G(P)G(P) be its unordered bipartite graph. Füredi–Hajnal acyclic-pattern conjecture. One should have

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

The paper presents this as a stronger predecessor of the Pach–Tardos conjecture and states that it was later refuted.

References

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.