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.
Method
The argument uses minimal counterexamples at a slightly superlinear threshold, hereditary sparsity, expansion, Hall’s theorem, Chernoff bounds, and elementary calculus.
Results
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).
Takeaways & 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.
Takeaways & Limitations
The present implementation cannot make the weight bounded, and the linear bound appears to require a genuinely new idea.
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.
- Definitions: 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.
- 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.
- 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.
- Main result: 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.
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.
- 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.
- 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.
- 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.
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).
- Minimum-degree and cycle tools: 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.
- 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.
- 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.
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.
- 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.
- 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.
- 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.
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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).
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.
- 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.
- Limits of the method: 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.
- 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.