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.
References
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
No solutions have been posted yet.