The large empty bipartite pair conjecture under induced four-cycle-free restrictions
The large empty bipartite pair conjecture under induced four-cycle-free restrictions
Let be a bipartite graph with vertex classes and , each of size . The maximum degree of is at most , and an induced four cycle-free subgraph is an induced subgraph containing no cycle of length four. The large empty bipartite pair conjecture. For every there exist such that, if contains no induced four cycle-free subgraph of average degree more than , then there exist and with and no edges between and . The source states that proving this combinatorial assertion would suffice for the large constant submatrix consequence of the preceding conjecture, but gives no resolution status.
Sources & referencesView supporting material
Primary source
István Tomon, “Factorization norms and Zarankiewicz problems”, arXiv:2502.18429 (2025).
Progress summary
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.