Axenovich–Martin conjecture on complete partitions of bipartite-free graphs

At least 2 years old · documented by

Let HH be a bipartite graph that is not a forest. Write f(r,H)f(r,H) for the least integer kk such that every HH-free (r,k)(r,k)-graph does not exist, and write ex⁡(N,H)\operatorname{ex}(N,H) for the maximum number of edges in an HH-free graph on NN vertices. An HH-free (r,k)(r,k)-graph is a graph whose vertex set is partitioned into rr parts of size at most kk, with at least one edge between every two parts. Axenovich–Martin conjecture. There is a positive constant c=c(H)c=c(H) such that for any positive integers rr and kk satisfying

ex⁡(rk,H)>c(r2),\operatorname{ex}(rk,H)>c\binom{r}{2},

there is an HH-free (r,k)(r,k)-graph, equivalently f(r,H)<kf(r,H)<k. If true, this would show that the trivial lower bound gives the correct order of magnitude and remove the logarithmic factor from the known upper bound for f(r,H)f(r,H).

References

Primary source

John Byrne, Michael Tait and Craig Timmons, “Forbidden subgraphs and complete partitions”, arXiv:2308.16728 (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.