The large empty bipartite pair conjecture under induced four-cycle-free restrictions

Let GG be a bipartite graph with vertex classes AA and BB, each of size nn. The maximum degree of GG is at most εn\varepsilon n, 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 k>0k>0 there exist ε,c>0\varepsilon,c>0 such that, if GG contains no induced four cycle-free subgraph of average degree more than kk, then there exist XAX\subset A and YBY\subset B with X=Ycn|X|=|Y|\geq cn and no edges between XX and YY. 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

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.