Conlon–Lee conjecture on improved extremal bounds for bipartite graphs

About 7 years old · traced to

Let HH be a Kr,rK_{r,r}-free bipartite graph with degree at most rr on one side.

Conlon–Lee conjecture. There exists c=cH>0c=c_H>0 such that

ex⁡(n,H)=O(n2−1/r−c).\operatorname{ex}(n,H)=O(n^{2-1/r-c}).

This strengthens the classical bound ex⁡(n,H)=O(n2−1/r)\operatorname{ex}(n,H)=O(n^{2-1/r}) for bipartite graphs with degree at most rr on one side. The conjecture is confirmed for hypercubes and bipartite Kneser graphs, but remains open in general.

References

Primary source

Jisun Baek, David Conlon and Joonkyung Lee, “On the extremal number of incidence graphs”, arXiv:2501.00521 (2024).

Additional references

3 papers in this index state this conjecture (2019–2024). The statement above is taken from the most recent of them; the others are arXiv:1910.11048, arXiv:1905.08001.

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.