Linearity of g(q) in divisible subdivisions

Informal Conjecture (linearity of g(q)) · arXiv:2012.05112

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

Authors: Noga Alon, Michael Krivelevich

Status solved high confidence

Das, Draganić, and Steiner (arXiv:2111.05723, 2021) proved that for any subcubic $n$-vertex graph $H$ and integer $q \geq 2$, the Alon–Krivelevich function satisfies $f(H,q) \leq \frac{21}{2}qn + 8n + 14q$, which is linear in $q$ and optimal up to a constant factor. Since cycles are subcubic, this directly establishes $g(q) = O(q)$, confirming Conjecture (linearity of $g(q)$) from arXiv:2012.05112 and removing the $\log q$ factor that Alon and Krivelevich attributed to the probabilistic method. The paper was subsequently published in the Journal of Combinatorial Theory, Series B (2024).

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 all subcubic H, establishing g(q) = O(q) and confirming the conjecture that the O(q log q) bound is not tight.
partial Divisible subdivisions of graphs in subdivisions of complete graphs (2025)

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

Improves the linear bounds of Das–Draganić–Steiner for specific cases (trees, cycles, 5-degenerate graphs) and works toward the exact value s_q(H) = m(q-1)+n.

Reviewer notes. The conjecture is resolved by arXiv:2111.05723. The key insight is that a subdivision of C_3 with all edge-paths of length divisible by q yields a cycle of length divisible by q, so f(C_3,q) = O(q) implies g(q) = O(q). The 2025 follow-up (arXiv:2510.05697) refines the constant factors and addresses exact values in special cases.

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

Informal. It seems plausible to believe that the first lemma is not tight and that the function $g(q)$ in Theorem 2 is linear in $q$ for any integer $q$.

Context

Theorem 2 establishes $g(q) = O(q \log q)$, and for prime $q$ the bound improves to $g(q) < 4q$. The authors note in the concluding remarks that Lemma 3.1 (which gives $\lceil 2q \ln q \rceil$ vertices) is likely not tight, and conjecture informally that the logarithmic factor is an artifact of the probabilistic method used.

Notes. Expressed via 'It seems plausible to believe'; clearly conjectural but no labelled environment. 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