Füredi–Hajnal conjecture for arbitrary forbidden patterns
Füredi–Hajnal conjecture for arbitrary forbidden patterns
Let be any forbidden pattern, and let be its unordered bipartite graph. Let denote the maximum number of ones in an matrix avoiding , and let denote the Turán extremal function of . Füredi–Hajnal logarithmic conjecture. One should have
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
Sign in to submit a solution.
No solutions have been posted yet.