pith. sign in

arxiv: 2605.22232 · v1 · pith:P2WMEOKInew · submitted 2026-05-21 · 🧮 math.CO

Polylogarithmic Bounds for Nested Cycles without Geometric Crossings

Yue Xu , Jiasheng Zeng , Xiao-Dong Zhang This is my paper

Pith reviewed 2026-05-22 04:59 UTC · model grok-4.3

classification 🧮 math.CO
keywords nested cyclesnoncrossing cyclesedge-disjoint cyclesextremal graph theoryErdős problemsgeometric crossingspolylogarithmic boundscycle nesting
0
0 comments X

The pith

A graph with C n (log n)^{k-1} (log log n)^{k-3} edges contains k edge-disjoint noncrossing nested cycles for any fixed k at least 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends an Erdős problem on nested cycles to the geometric setting where nesting must respect noncrossing cyclic orders. It establishes a quantitative threshold showing that a specific polylogarithmic edge count forces the existence of k pairwise edge-disjoint nested cycles without geometric crossings in sufficiently large graphs. This bound improves on earlier constant-degree results for the two-cycle case by handling arbitrary fixed numbers of layers. A reader would care because it gives a concrete density condition under which this structured collection of cycles is guaranteed to appear. The argument proceeds by iteratively constructing the layers via expanders and a controlled wrapping step.

Core claim

For every fixed k ≥ 3, every sufficiently large n-vertex graph with at least C_k n (log n)^{k-1} (log log n)^{k-3} edges contains k pairwise edge-disjoint nested cycles without geometric crossings. The proof combines the robust sublinear expander framework with a controlled wrapping lemma that permits the layers to be built successively with controlled length.

What carries the argument

The controlled wrapping lemma that permits the layers to be built successively with controlled length

If this is right

  • The extremal number of edges needed to force k noncrossing nested cycles is at most polylogarithmic in n.
  • Constant average degree suffices for two such cycles, while higher fixed layers require the stated polylog growth.
  • The geometric noncrossing condition in cyclic orders is compatible with the edge threshold given by the bound.
  • The successive layer construction works uniformly for any fixed depth k.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same expander-plus-wrapping approach may yield bounds for other prescribed nested or layered substructures.
  • Tighter bounds or matching lower constructions could emerge from refinements to the controlled wrapping step.
  • The result suggests algorithmic methods for locating such cycle collections once the edge count is met.
  • Connections to other geometric or order-constrained extremal problems become testable via similar density thresholds.

Load-bearing premise

The controlled wrapping lemma permits the layers to be built successively with controlled length as stated in the proof outline.

What would settle it

A graph on arbitrarily large n vertices that has more than C_k n (log n)^{k-1} (log log n)^{k-3} edges yet contains no k pairwise edge-disjoint noncrossing nested cycles would disprove the claim.

Figures

Figures reproduced from arXiv: 2605.22232 by Jiasheng Zeng, Xiao-Dong Zhang, Yue Xu.

Figure 1
Figure 1. Figure 1: Controlled wrapping in one inductive step. In the iteration, the current cycle is denoted [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
read the original abstract

A problem of Erd\H{o}s asks for extremal conditions forcing edge-disjoint cycles with a prescribed nested structure. In the geometric version, the nesting is required to be noncrossing with respect to the cyclic orders. Fern\'andez, Kim, Kim and Liu proved that constant average degree forces two such cycles. We prove a polylogarithmic bound for the natural multi-layer version: for every fixed $k\ge 3$, every sufficiently large $n$-vertex graph with at least \[ C_k n(\log n)^{k-1}(\log\log n)^{k-3} \] edges contains $k$ pairwise edge-disjoint nested cycles without geometric crossings. The proof combines the robust sublinear expander framework of Alon, Buci\'c, Sauermann, Zakharov and Zamir with a controlled wrapping lemma that permits the layers to be built successively with controlled length.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper proves that for every fixed integer k ≥ 3, every sufficiently large n-vertex graph with at least C_k n (log n)^{k-1} (log log n)^{k-3} edges contains k pairwise edge-disjoint nested cycles without geometric crossings. The argument combines the robust sublinear expander framework of Alon et al. with a new controlled wrapping lemma that is used to construct the layers successively while maintaining edge-disjointness and non-crossing geometry.

Significance. If the central claim holds, the result supplies the first polylogarithmic extremal threshold for the multi-layer version of the geometric nested-cycle problem, improving on the constant-average-degree guarantee known for k=2. The explicit dependence on k in the exponents and the use of a controlled wrapping lemma to preserve expansion parameters across layers constitute a concrete technical advance that could be reusable for other iterated embedding problems in sparse graphs.

major comments (1)
  1. [Proof outline / controlled wrapping lemma] The proof sketch invokes the controlled wrapping lemma repeatedly to add k-1 layers after the initial expander cycle. However, no explicit multiplicative bound is given on the length or neighborhood-size inflation incurred by each successive application, nor is it shown that the robust-expansion parameters remain sufficient after k-2 prior wrappings. This analysis is load-bearing for the precise exponent k-3 on the (log log n) term in the claimed edge threshold.
minor comments (1)
  1. [Theorem 1.1] The statement of the main theorem should explicitly record that C_k depends on k but is independent of n.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying a point in the proof outline that merits additional detail. We address the comment below and will revise the manuscript to incorporate the requested analysis.

read point-by-point responses

  1. Referee: The proof sketch invokes the controlled wrapping lemma repeatedly to add k-1 layers after the initial expander cycle. However, no explicit multiplicative bound is given on the length or neighborhood-size inflation incurred by each successive application, nor is it shown that the robust-expansion parameters remain sufficient after k-2 prior wrappings. This analysis is load-bearing for the precise exponent k-3 on the (log log n) term in the claimed edge threshold.

    Authors: We appreciate the referee highlighting this aspect of the argument. The controlled wrapping lemma (Lemma 3.2) is formulated to ensure that each application inflates neighborhood sizes by a factor that is at most polylogarithmic in the current parameters, specifically bounded by O(log log n) in the relevant expansion regime. The proof proceeds by induction on the number of layers, with the robust sublinear expansion parameters from Alon et al. adjusted at each step to absorb the inflation while retaining sufficient expansion for the next cycle extraction. However, we acknowledge that the current manuscript presents this only at the level of a sketch and does not include the explicit multiplicative bounds or the verification that the parameters remain adequate after k-2 successive wrappings. We agree that this tracking is necessary to rigorously justify the precise exponent k-3. In the revised version we will insert a new subsection (or expanded proof of the main theorem) that records the parameter evolution explicitly, including the precise inflation factor per wrapping and the inductive argument confirming that the expander properties survive the required number of iterations. This addition will also make transparent how the accumulated factors produce the (log log n)^{k-3} term in the edge threshold. revision: yes

Circularity Check

0 steps flagged

No circularity: result derived from external expander framework plus new lemma

full rationale

The derivation combines the robust sublinear expander framework of Alon et al. (external, non-overlapping authors) with a controlled wrapping lemma introduced in the present paper to build successive nested layers. No equation reduces a claimed prediction to a fitted parameter or self-defined quantity by construction, and the polylogarithmic edge threshold is obtained from the composition of these tools rather than from renaming or self-citation load-bearing. The argument is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Based on abstract only; the proof rests on the robust sublinear expander framework (external) and the new controlled wrapping lemma (introduced here). C_k is an existential constant whose size is not computed.

free parameters (1)
  • C_k
    Sufficiently large constant depending on k that makes the edge lower bound work; its value is not derived explicitly.
axioms (1)
  • domain assumption Robust sublinear expander framework of Alon, Bucić, Sauermann, Zakharov and Zamir applies to the setting of nested cycle packing.
    Invoked directly in the proof combination described in the abstract.

pith-pipeline@v0.9.0 · 5684 in / 1286 out tokens · 49566 ms · 2026-05-22T04:59:30.985010+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Problems and results in graph theory and combinatorial analysis , booktitle =

    Erd. Problems and results in graph theory and combinatorial analysis , booktitle =

    work page

  2. [2]

    Nested cycles in graphs , booktitle =

    Bollob. Nested cycles in graphs , booktitle =

    work page

  3. [3]

    Proof of a conjecture of

    Chen, Guantao and Erd. Proof of a conjecture of. Journal of Combinatorial Theory, Series B , volume =

    work page

  4. [4]

    On the maximal number of independent circuits in a graph , journal =

    Corr. On the maximal number of independent circuits in a graph , journal =

    work page

  5. [5]

    Equicardinal disjoint cycles in sparse graphs , journal =

    H. Equicardinal disjoint cycles in sparse graphs , journal =

    work page

  6. [6]

    Journal of Combinatorial Theory, Series B , volume =

    Egawa, Yoshimi , title =. Journal of Combinatorial Theory, Series B , volume =

    work page

  7. [7]

    Partition of graphs with condition on the connectivity and minimum degree , journal =

    Hajnal, P. Partition of graphs with condition on the connectivity and minimum degree , journal =

    work page

  8. [8]

    Journal of Graph Theory , volume =

    Thomassen, Carsten , title =. Journal of Graph Theory , volume =

    work page

  9. [9]

    Journal of Graph Theory , volume =

    Stiebitz, Michael , title =. Journal of Graph Theory , volume =

    work page

  10. [10]

    Partitions of graphs with high minimum degree or connectivity , journal =

    K. Partitions of graphs with high minimum degree or connectivity , journal =

    work page

  11. [11]

    A note on vertex-disjoint cycles , journal =

    Verstra. A note on vertex-disjoint cycles , journal =

    work page

  12. [12]

    Nested cycles with no geometric crossings , journal =

    Fern. Nested cycles with no geometric crossings , journal =. 2022 , eprint =

    work page 2022

  13. [13]

    Topological cliques in graphs

    Koml. Topological cliques in graphs. Combinatorics, Probability and Computing , volume =

    work page

  14. [14]

    International Mathematics Research Notices , volume =

    Haslegrave, John and Kim, Jaehoon and Liu, Hong , title =. International Mathematics Research Notices , volume =

    work page

  15. [15]

    Proceedings of the London Mathematical Society , volume =

    Kim, Jaehoon and Liu, Hong and Sharifzadeh, Maryam and Staden, Katherine , title =. Proceedings of the London Mathematical Society , volume =

    work page

  16. [16]

    Journal of the London Mathematical Society , volume =

    Liu, Hong and Montgomery, Richard , title =. Journal of the London Mathematical Society , volume =

    work page

  17. [17]

    Highly linked graphs , journal =

    Bollob. Highly linked graphs , journal =

    work page

  18. [18]

    Essentially tight bounds for rainbow cycles in proper edge-colourings , journal =

    Alon, Noga and Buci. Essentially tight bounds for rainbow cycles in proper edge-colourings , journal =. 2025 , doi =

    work page 2025

  19. [19]

    Dense graphs without 3-regular subgraphs , journal =

    Pyber, L. Dense graphs without 3-regular subgraphs , journal =

    work page

  20. [20]

    Advances in Mathematics , volume =

    Chakraborti, Debsoumya and Janzer, Oliver and Methuku, Abhishek and Montgomery, Richard , title =. Advances in Mathematics , volume =. 2025 , eprint =

    work page 2025

  21. [21]

    Forum of Mathematics, Pi , volume =

    Janzer, Oliver and Sudakov, Benny , title =. Forum of Mathematics, Pi , volume =

    work page

  22. [22]

    Cycles with many chords , journal =

    Dragani. Cycles with many chords , journal =. 2024 , doi =

    work page 2024

  23. [23]

    The extremal number of cycles with all diagonals , journal =

    Brada. The extremal number of cycles with all diagonals , journal =. 2024 , doi =

    work page 2024