q-divisible subdivision f(H,q) growth rate

Open Problem (asymptotic behavior of f(H,q)) · arXiv:2012.05112

arXiv Problem medium confidence— first stated 2021-06-29

Authors: Noga Alon, Michael Krivelevich

Status solved high confidence

Das, Draganić, and Steiner (arXiv:2111.05723, JCTB 2023) resolved the asymptotic behavior of f(H,q) by proving f(H,q) ≤ (21/2)qn + 8n + 14q for subcubic H on n vertices, and showing this bound is optimal up to a constant multiplicative factor. This settles the open problem: the asymptotic order of f(H,q) is linear in qn. A 2025 follow-up by Hou and Wang (arXiv:2510.05697) studies the related function s_q(H) in complete-graph subdivisions and achieves further improvements for special cases.

Cited literature (2)

proof Tight bounds for divisible subdivisions (2021)

Shagnik Das, Nemanja Draganić, Raphael Steiner · Journal of Combinatorial Theory, Series B · arXiv:2111.05723

Proves f(H,q) ≤ (21/2)qn + 8n + 14q for subcubic H on n vertices and shows this is optimal up to a constant factor, resolving the asymptotic behavior of f(H,q) posed in arXiv:2012.05112.
partial Divisible subdivisions of graphs in subdivisions of complete graphs (2025)

Xinmin Hou, Xiangyang Wang · arXiv preprint · arXiv:2510.05697

Studies the related function s_q(H) (minimum complete-graph order for a q-divisible subdivision of H), proving improved upper bounds and resolving the case q=2 completely for 5-degenerate graphs and trees.

Reviewer notes. The key resolution is arXiv:2111.05723 (Das–Draganić–Steiner), which appeared on arXiv in November 2021 (after the June 2021 journal publication of the source paper) and was published in JCTB in 2023. The bound f(H,q) = Θ(qn) is tight up to constants, so the asymptotic question is answered. The 2025 paper (arXiv:2510.05697) addresses a variant with complete-graph subdivisions rather than K_f-minors.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Determine or estimate the asymptotic behavior of the best possible bound for $f(H, q)$ such that every $K_f$-minor contains a subdivision of $H$ in which every edge is replaced by a path whose length is divisible by $q$.

Context

Theorem 1 guarantees a finite $f = f(H,q)$ for every graph $H$ of maximum degree at most 3 and every positive integer $q$, but the proof makes essentially no attempt to optimize $f$. The authors note in the introduction and again in the concluding remarks that the problem of determining the asymptotic behavior of $f(H,q)$ remains open, and that Ramsey constructions from the literature give some improvement but still yield bounds that are surely far from optimal.

Notes. Stated twice: once after the remark following Theorem 1 ('the problem of determining its asymptotic behavior remains open') and once in the concluding remarks. PDF source — math notation appears clean.

Source paper

Divisible subdivisions
Noga Alon, Michael Krivelevich · 2021-06-29
https://arxiv.org/abs/2012.05112 PDF source