Pikhurko–Sousa conjecture on asymptotic extremal decompositions

At least 14 years old · documented by

Let HH be a graph with chromatic number at least 33. For an nn-vertex graph GG, let ϕ(G,H)\phi(G,H) be the minimum number of parts in an edge partition into copies of HH and single edges, and define ϕ(n,H):=max⁡G∈Gnϕ(G,H)\phi(n,H):=\max_{G\in\mathcal{G}_n}\phi(G,H). Let ex⁡(n,H)\operatorname{ex}(n,H) denote the maximum number of edges in an nn-vertex graph containing no copy of HH.

Pikhurko–Sousa conjecture. There is an integer n0=n0(H)n_0=n_0(H) such that

ϕ(n,H)=ex⁡(n,H)\phi(n,H)=\operatorname{ex}(n,H)

for every n≥n0n\geq n_0.

Pikhurko and Sousa had previously established the asymptotic relation ϕ(n,H)=ex⁡(n,H)+o(n2)\phi(n,H)=\operatorname{ex}(n,H)+o(n^2) for each fixed graph HH with chromatic number at least 33; the conjecture asks for eventual exact equality.

References

Primary source

Lale Özkahya and Yury Person, “Minimum Rainbow H-Decompositions of Graphs”, arXiv:1704.01000 (2017).

Additional references

2 papers in this index state this conjecture (2011–2017). The statement above is taken from the most recent of them; the others are arXiv:1109.2571.

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.