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

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).

Sources & referencesView supporting material

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.