Source-linked AI summary
An $n(\log n)^{o(1)}$ bound for nested cycles without geometric crossings
Jiangdong Ai, Gregory Gutin, Yiming Hao
TL;DR
The paper addresses whether every fixed number of nested cycles without geometric crossings can be forced with only a linear edge bound. It develops an elementary minimal-counterexample argument and proves a bound whose n-dependent loss is independent of the number of layers, while noting that a linear bound remains unresolved.
Problem
Whether f_k(n)=O_k(n) for every fixed k remains open; the paper targets this question beyond the two-cycle case.
Source: §5 · p. 13Method
The argument uses minimal counterexamples at a slightly superlinear threshold, hereditary sparsity, expansion, Hall’s theorem, Chernoff bounds, and elementary calculus.
Source: §1 · p. 3Results
For every fixed k≥3, a graph exceeding K_kΦ(n) contains k nested cycles without geometric crossings, implying f_k(n)≤n(log n)^o(1).
Source: §1 · p. 2Takeaways & Limitations
The n-dependent loss no longer grows with the number of layers, and the strengthened theorem controls the outermost cycle’s length to enable induction on k.
Source: §1 · p. 2The present implementation cannot make the weight bounded, and the linear bound appears to require a genuinely new idea.
Source: §5 · p. 13
Abstract
from arXiv · showhide
Cycles $C_1,\ldots,C_k$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V(C_k)\subseteq\cdots\subseteq V(C_1)$, and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let $f_k(n)$ be the least number of edges that forces such a family in every $n$-vertex graph. Answering a question of Erdős for two cycles, Gil Fernández, Kim, Kim and Liu proved that $f_2(n)=O(n)$ and asked whether $f_k(n)=O_k(n)$ for every fixed $k$. Xu, Zeng and Zhang recently obtained the first general bound, $f_k(n)=O_k\bigl(n(\log n)^{k-1}(\log\log n)^{k-3}\bigr)$ for every fixed $k\ge3$. We prove that, for every fixed $k\ge3$, \[f_k(n)=O_k\!\left(n\,\frac{(\log\log n)^2}{\log\log\log n}\right), \] so in particular $f_k(n)\le n(\log n)^{o(1)}$, where the $n$-dependent iterated-logarithmic factor has the same form for every fixed number of cycles.
1 Introduction
The paper defines nested cycles without geometric crossings and proves a layer-independent iterated-logarithmic edge threshold for every fixed number of cycles, using a simpler approach than prior expander-based methods.
Definitions
- A nested family consists of pairwise edge-disjoint cycles whose vertex sets are successively contained and whose consecutive cycles preserve cyclic order up to reversal.The order condition means that, when the outer cycle is drawn as a convex polygon, the inner cycle’s edges do not cross.Source: §1 · pp. 1–2
- The extremal function f_k(n) is the least edge count forcing such a family in every n-vertex graph.A unicyclic n-vertex graph gives f_k(n)>n for every k≥2, while no superlinear lower bound is known in the supplied discussion.Source: §1 · p. 2
Context
- Earlier work proved f_2(n)=O(n) and asked whether f_k(n)=O_k(n), while a recent general bound had a log n exponent growing with k.The present proof does not invoke sublinear-expander machinery or the two-cycle theorem; it uses Hall’s theorem, Chernoff bounds, and elementary calculus.Source: §1 · pp. 2–3
Main result
- For every fixed k≥3, graphs with more than K_kΦ(n)=K_knω(n) edges contain k nested cycles without geometric crossings.Here ω(n)=Λ(n)^2/Γ(n), with shifted logarithmic functions defined in the introduction.Source: §1 · p. 2
- The bound implies f_k(n)≤n(log n)^{o(1)}, with the n-dependent loss independent of the number of layers.The stronger theorem also controls the outermost cycle’s length, which enables induction on k.Source: §1 · pp. 2–3
Overview of the proof
The proof argues from a minimal counterexample, whose hereditary sparsity yields expansion and local structure; random layering and protected trees then assemble cycles in the required order.
Minimal counterexample
- Minimality of a counterexample supplies hereditary induced-subgraph sparsity, a large minimum degree, vertex expansion, and local sparsity at polylogarithmic scales.These properties replace the sublinear-expander machinery used in earlier approaches.Source: Overview of the proof · pp. 3–4
Connecting paths
- A connecting lemma joins two sufficiently large vertex sets by a short path while avoiding a prescribed small set.The path length is O(L(n)Λ(n)^2) when the relevant parameter is polylogarithmic.Source: Overview of the proof · p. 3
Layering and trees
- Random layering creates disjoint vertex sets and private trees whose surviving root-to-leaf paths support connections between prescribed consecutive vertices.Protecting the upper parts of unused trees ensures that each earlier path destroys only a small fraction of available paths.Source: Overview of the proof · pp. 3–4
Parameter choice
- The weight ω(n)=Λ(n)^2/Γ(n) balances the number of layers, tree depth, and the minimum-degree requirement needed by the construction.The layering needs minimum degree of order r^2 log r, while the trees require enough depth to exceed the vertices consumed by earlier connections.Source: Overview of the proof · p. 4
2 Preliminaries
The preliminaries establish elementary tools used throughout the proof: extracting minimum degree, finding short cycles, constructing disjoint representatives, and controlling binomial deviations.
Minimum-degree and cycle tools
- e(G)/|G| yields a nonempty subgraph with minimum degree at least e(G)/|G|.The proof repeatedly deletes vertices below this threshold; otherwise every edge would be counted once in a degree sum below e(G).Source: §2 · p. 4
- Minimum degree at least 3 guarantees a cycle of length at most 2 log2 |H| + 3.A breadth-first search tree would otherwise expand too rapidly, exceeding the graph’s order.Source: §2 · p. 4
Matching tool
- Multiplicity Hall’s theorem assigns each x in one bipartition ℓ pairwise disjoint neighbors when every subset has at least ℓ times as many neighbors.The proof obtains this by replacing each vertex of X with ℓ clones and applying Hall’s theorem.Source: §2 · p. 5
Probabilistic tool
- A binomial variable with mean µ satisfies Pr(X ≤ µ/2) ≤ e^-µ/8.This Chernoff estimate controls vertices whose random forward degree is unusually small.Source: §2 · p. 5
3 Weighted minimal graphs
Weighted minimal counterexamples inherit hereditary edge bounds that yield minimum degree, expansion, and short connections; random layering supplies disjoint layers with forward-degree structure.
Minimality
- A K-minimal n-vertex graph has more than KΦ(n) edges while every nonempty proper induced subgraph on m vertices has at most KΦ(m) edges.This hereditary inequality is the central consequence of choosing a counterexample minimal in order.Source: §3 · p. 6
Minimum degree and expansion
- δ(G) > Kω(n)/2 in every K-minimal graph.Deleting any vertex and comparing Φ(n)−Φ(n−1) with ω(n) converts the hereditary edge bound into minimum degree.Source: §3 · pp. 5–6
Connecting lemma
- Any two sets of size at least σ/4 can be joined in G−Z by a path of length at most R = ⌈132LΛ^2⌉ when |Z| ≤ σ/64.Ball growth first reaches size σΛ and then exceeds n/2, forcing the two grown balls to intersect.Source: §3 · pp. 6–7
Random layering
- Random coloring produces disjoint layers W0,...,Wr−1 with e(G[W0]) ≥ e(G)/8 and a forward-degree condition when δ(G) ≥ 32r^2 log r.The proof bounds unlucky vertices using the Chernoff inequality and then chooses a coloring with sufficiently many retained edges.Source: §3 · pp. 7–8
4 Proof of Theorem 1.3
Theorem 1.3 is proved inductively by embedding a short outer cycle around an inductively obtained inner family, using layered expansion, private trees, and short connecting paths.
Inductive setup
- The induction starts at k = 1 by extracting minimum degree and then a short cycle from any graph with e(G) > Φ(n).A single cycle serves as the base family for the strengthened theorem.Source: §4 · p. 8
Parameter choice
- The parameters r, h, and b are balanced so that r^2 log r is of order ω(n), producing the iterated-logarithmic threshold scale.The construction uses r layers, tree depth h, branching factor b, and leaf count s, with s ≤ n^1/2 and 8Qs < n.Source: §4 · p. 9
Minimal counterexample
- A minimum-order counterexample is Kk-minimal, so its induced subgraphs obey the hereditary threshold needed for all local Hall comparisons.The constants are chosen in an order that preserves these comparisons while raising the minimum-degree bound.Source: §4 · p. 10
Layered construction
- Layering yields disjoint sets with e(G[W0]) ≥ e(G)/8, and every vertex in successive layers has more than θ = Kkω(n)/(16r) forward neighbors.The induction hypothesis applied inside W0 produces the inner cycles C2,...,Ck.Source: §4 · p. 10
Private trees
- Hall’s theorem builds 2q pairwise vertex-disjoint complete b-ary private trees, each with s = b^h leaves at depth h.Hereditary edge bounds force the required multiplicity of neighbors at every tree level.Source: §4 · pp. 10–11
Outer cycle
- The constructed paths S1,...,Sq are simple, internally vertex-disjoint, avoid other inner-cycle vertices, and have length at most R + 2h + 2.Their union forms an outer cycle C1 that preserves the cyclic order of C2 and satisfies the required edge-disjointness and containment conditions.Source: §4 · pp. 11–12
Conclusion
- The resulting family contradicts minimality, completing the induction and proving Theorem 1.3.Applying Theorem 1.3 gives ω(n) = (1 + o(1))(log log n)^2/log log log n and the stated bound for fk(n).Source: §4 · p. 13
5 Concluding remarks
The method’s exponent is independent of the number of cycles, but its current implementation cannot achieve a linear bound. The main bottleneck is the layering degree requirement, while constants and thresholds are already very large.
Why the exponent does not depend on k
- The exponent of log n is independent of k because increasing the number of layers changes constants and outer-cycle length, not the density-threshold shape.The level-k induction uses the previous cycle’s polylogarithmic length and changes Kk and Ak, while Φ(n) retains the same form.Source: §5 · p. 13
Limits of the method
- The implementation cannot use bounded ω, so it does not yield the desired linear bound.The obstruction arises because the private-tree branching factor must remain large.Source: §5 · p. 13
- The question whether fk(n)=O_k(n) for every fixed k appears to require a genuinely new idea.The paper does not establish whether the proposed stronger layering lemma holds.Source: §5 · p. 13
Constants
- The constants are not optimized, and the threshold nk is already astronomically large for k=2 because b≥2 forces Λ(n) to be very large in terms of k.The outermost cycle’s length bound could improve, but it is not the argument’s bottleneck.Source: §5 · p. 13