Füredi–Hajnal conjecture for acyclic patterns

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(ExTur(G(P),n)logn)=O(nlogn).\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.

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.