Cone graph crossing f_s(k) k^(3/4) asymptotic
Conjecture on $f_s(k)$ asymptotics · arXiv:1608.07680
Status open medium confidence
The conjecture that $f_s(k) = k + \sqrt{2}\,k^{3/4}(1+o(1))$ for simple graphs appears to remain open as of 2026. The original paper (published in SIAM J. Discrete Math. 32, 2018) established $f_s(k) = k + o(k)$. A 2021 follow-up by Ding and Huang computed additional specific small values of the related function $\varphi_s(k) = f_s(k) - k$ (proving $\varphi_s(6) = 5$ and $\varphi_s(7) = 6$), but did not resolve the asymptotic conjecture. No paper resolving the full asymptotic formula was found.
Cited literature (1)
-
Proves $\varphi_s(6)=5$ and $\varphi_s(7)=6$ (additional specific values of the cone crossing-number gap function), extending the table of known values from the original paper but leaving the asymptotic conjecture open.
Reviewer notes. Full text of the Ding-Huang 2021 paper was behind a paywall; its basic facts (title, authors, journal, DOI, and the results on $\varphi_s(6)$ and $\varphi_s(7)$) were confirmed by multiple independent search-result snippets. The conjecture concerns the precise asymptotic $k + \sqrt{2}\,k^{3/4}(1+o(1))$ for simple graphs; the established bound $f_s(k) = k + o(k)$ is consistent with it but far weaker. No resolution of the full asymptotic statement was found in the indexed literature.
Context
Section 5 proves $f_s(k) = k + o(k)$ for simple graphs, improving on the upper bound $f_s(k) \leq 2k$ suggested by small cases ($f_s(1)=3,\, f_s(2)=5,\, f_s(3)=6,\, f_s(4)=8,\, f_s(5)=10$). The authors provide additional justification for this more precise asymptotic conjecture on the simple-graph version of $f$.
Notes. Stated as an informal conjecture in running prose without a labelled theorem environment; PDF source — math notation ($\sqrt{2}\,k^{3/4}$) may be partially garbled.
Source paper
The crossing number of the cone of a graph
Carlos A. Alfaro, Alan Arroyo, Marek Derunár, Bojan Mohar · 2016-08-27
https://arxiv.org/abs/1608.07680
PDF source