pith. sign in

arxiv: 1906.11558 · v1 · pith:6OMVN4R6new · submitted 2019-06-27 · 🧮 math.CO

Perfectly packing graphs with bounded degeneracy and many leaves

Peter Allen , Julia B\"ottcher , Dennis Clemens , Anusch Taraz This is my paper

Pith reviewed 2026-05-25 15:03 UTC · model grok-4.3

classification 🧮 math.CO
keywords graph packingdegenerate graphsquasirandom graphsRingel's conjecturetree packingdegeneracyleaves
0
0 comments X

The pith

Degenerate graphs with max degree o(n/log n) pack perfectly into dense quasirandom graphs when a linear number are small or have many leaves.

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

The paper proves that any sequence of degenerate graphs on at most n vertices, each with maximum degree o(n/log n), can be packed edge-disjointly to cover all edges of a complete graph or dense quasirandom n-vertex graph, provided that Ω(n) of the graphs are either at most (1-Ω(1))n vertices or have Ω(n) leaves. This directly implies that Ringel's conjecture on tree decompositions of complete graphs and the Győri–Lovász tree packing conjecture both hold for all but an exponentially small fraction of trees or sequences of trees. A sympathetic reader cares because these conjectures ask when a complete graph can be decomposed into given smaller graphs, and the new result removes almost all exceptional cases under the stated degeneracy and degree hypotheses.

Core claim

We prove that one can perfectly pack degenerate graphs into complete or dense n-vertex quasirandom graphs, provided that all the degenerate graphs have maximum degree o(n/log n), and in addition Ω(n) of them have at most (1-Ω(1))n vertices and Ω(n) leaves. This proves Ringel's conjecture and the Győri–Lovász Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively).

What carries the argument

The linear number of small or high-leaf degenerate graphs, which supplies enough flexibility to complete the packing into the quasirandom host while respecting the o(n/log n) degree bound.

If this is right

  • Ringel's conjecture holds for every tree except an exponentially small fraction of n-vertex trees.
  • The Győri–Lovász conjecture holds for every sequence of trees except an exponentially small fraction.
  • The same packing works inside any dense quasirandom host, not only the complete graph.
  • Degeneracy plus the o(n/log n) degree bound is compatible with perfect packing once the leaf or size condition is met.

Where Pith is reading between the lines

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

  • The leaf condition may be close to necessary, as graphs without many leaves could create local obstructions that quasirandom hosts cannot absorb.
  • The result suggests that similar packing statements might hold for hosts that are only approximately quasirandom or slightly sparser than linear density.
  • One could test whether the exponential-error term can be improved to a polynomial fraction by refining the leaf-count threshold.

Load-bearing premise

The host graph is dense and quasirandom while the packed graphs include a linear number that are either small or have many leaves.

What would settle it

A sequence of degenerate graphs each with maximum degree o(n/log n) but only o(n) small or high-leaf instances that fails to pack perfectly into some dense quasirandom n-vertex graph.

read the original abstract

We prove that one can perfectly pack degenerate graphs into complete or dense $n$-vertex quasirandom graphs, provided that all the degenerate graphs have maximum degree $o(\frac{n}{\log n})$, and in addition $\Omega(n)$ of them have at most $(1-\Omega(1))n$ vertices and $\Omega(n)$ leaves. This proves Ringel's conjecture and the Gy\'arf\'as Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively).

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

0 major / 2 minor

Summary. The manuscript proves that one can perfectly pack degenerate graphs into complete or dense n-vertex quasirandom graphs when every graph has maximum degree o(n/log n) and, additionally, Ω(n) of the graphs are either of order at most (1-Ω(1))n or possess Ω(n) leaves. The result is used to establish Ringel's conjecture and the Győri Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees).

Significance. If the central packing theorem holds, the work supplies a near-complete resolution of two classical conjectures by handling the generic case via degeneracy-bounded embedding lemmas combined with quasirandom host properties and a separate counting argument that most trees satisfy the linear-size or linear-leaf condition. The explicit error terms that remain o(1) under the stated hypotheses constitute a concrete technical contribution.

minor comments (2)
  1. The abstract states the main theorem with explicit conditions but does not indicate the precise section in which the degeneracy-bounded embedding lemma is proved; a forward reference would improve readability.
  2. The counting argument that most trees satisfy the Ω(n)-leaf or linear-size condition is invoked to absorb remaining volume; the manuscript should clarify whether this counting is carried out inside the main proof or as a separate lemma.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript is a direct existence proof in extremal graph theory. It combines standard degeneracy-bounded embedding lemmas with quasirandom host-graph properties and an explicit counting argument on the fraction of trees satisfying the linear-size or linear-leaf hypotheses. All error terms are controlled by the stated o(n/log n) degree bound and the Ω(n) high-leaf/small-graph conditions; neither quantity is fitted to the target packing nor defined in terms of the final result. No self-citation is invoked as a uniqueness theorem or load-bearing premise, and no equation or parameter is renamed as a prediction. The derivation therefore remains self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper is a pure existence proof in extremal graph theory and relies only on standard definitions and lemmas from the field.

axioms (1)
  • standard math Standard definitions and basic lemmas of graph degeneracy, quasirandom graphs, and perfect packing.
    Invoked throughout any such packing argument; no ad-hoc axioms introduced in the abstract.

pith-pipeline@v0.9.0 · 5607 in / 1234 out tokens · 24486 ms · 2026-05-25T15:03:06.327209+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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A rainbow blow-up lemma for almost optimally bounded edge-colourings

    math.CO 2019-07 unverdicted novelty 7.0

    Proves a rainbow blow-up lemma for almost optimally bounded edge-colorings, implying existence of rainbow copies of any bounded-degree spanning subgraph in a quasirandom host graph under an asymptotically best-possibl...

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · cited by 1 Pith paper · 4 internal anchors

  1. [1]

    Allen, J

    P. Allen, J. Böttcher, J. Hladký, and D. Piguet, Packing degenerate graphs , arXiv:1711.04869

    work page arXiv

  2. [2]

    Böttcher, J

    J. Böttcher, J. Hladký, D. Piguet, and A. Taraz, An approximate version of the tree packing conjecture , Israel J. Math. 211 (2016), no. 1, 391–446

    work page 2016

  3. [3]

    A. Z. Broder, How hard is it to marry at random? (on the approximation of the permanent), Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computin g (New York, NY, USA), STOC ’86, ACM, 1986, pp. 50–58

    work page 1986

  4. [4]

    Dor and M

    D. Dor and M. Tarsi, Graph decomposition is NP-complete: a complete proof of Hol yer’s conjecture , SIAM J. Comput. 26 (1997), no. 4, 1166–1187

    work page 1997

  5. [5]

    R. A. Duke, H. Lefmann, and V. Rödl, A fast approximation algorithm for computing the frequenci es of subgraphs in a given graph , SIAM J. Comput. 24 (1995), no. 3, 598–620

    work page 1995

  6. [6]

    Ferber, C

    A. Ferber, C. Lee, and F. Mousset, Packing spanning graphs from separable families , Israel J. Math. 219 (2017), no. 2, 959–982

    work page 2017

  7. [7]

    Packing trees of unbounded degrees in random graphs

    A. Ferber and W. Samotij, Packing trees of unbounded degrees in random graphs , arXiv:1607.07342

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    D. A. Freedman, On tail probabilities for martingales , Ann. Probability 3 (1975), 100–118

    work page 1975

  9. [9]

    J. A. Gallian, A dynamic survey of graph labeling , Electron. J. Combin. 5 (1998), Dynamic Survey 6, 43

    work page 1998

  10. [10]

    Glock, D

    S. Glock, D. Kühn, A. Lo, and D. Osthus, The existence of designs via iterative absorption , arXiv:1611.06827

    work page arXiv

  11. [11]

    , Hypergraph F -designs for arbitrary F , arXiv:1706.01800

    work page arXiv

  12. [12]

    Gyárfás and J

    A. Gyárfás and J. Lehel, Packing trees of different order into Kn, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Colloq. Math. Soc. János Bolyai , vol. 18, North-Holland, Amsterdam, 1978, pp. 463–469

    work page 1976

  13. [13]

    Janson, T

    S. Janson, T. Łuczak, and A. Ruciński, Random graphs, Wiley-Interscience, 2000. PERFECTLY PACKING GRAPHS WITH BOUNDED DEGENERACY AND MANY L EA VES 51

    work page 2000

  14. [14]

    Jerrum and A

    M. Jerrum and A. Sinclair, Approximating the permanent , SIAM Journal on Computing 18 (1989), no. 6, 1149–1178

    work page 1989

  15. [15]

    F. Joos, J. Kim, D. Kühn, and D. Osthus, Optimal packings of bounded degree trees , J. European Math. Soc., to appear

    work page

  16. [16]

    Keevash, The existence of designs , arXiv:1401.3665

    P. Keevash, The existence of designs , arXiv:1401.3665

    work page arXiv

  17. [17]

    , The existence of designs ii , arXiv:1802.05900

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    J. Kim, D. Kühn, D. Osthus, and M. Tyomkyn, A blow-up lemma for approximate decompositions , arXiv:1604.07282

    work page internal anchor Pith review Pith/arXiv arXiv

  19. [19]

    T. P. Kirkman, On a problem in combinations , Cambridge and Dublin Math. J. 2 (1847), 191–204

    work page

  20. [20]

    F. Knox, D. Kühn, and D. Osthus, Edge-disjoint Hamilton cycles in random graphs , Random Structures Algorithms 46 (2015), no. 3, 397–445

    work page 2015

  21. [21]

    Lucas, Récréations mathématiques, 2ième éd., nouveau tirage, Librairie Scientifique et Techn ique Albert Blanchard, Paris, 1960

    E. Lucas, Récréations mathématiques, 2ième éd., nouveau tirage, Librairie Scientifique et Techn ique Albert Blanchard, Paris, 1960

    work page 1960

  22. [22]

    Messuti, V

    S. Messuti, V. Rödl, and M. Schacht, Packing minor-closed families of graphs into complete grap hs, J. Combin. Theory Ser. B 119 (2016), 245–265

    work page 2016

  23. [23]

    Embedding rainbow trees with applications to graph labelling and decomposition

    R. Montgomery, A. Pokrovskiy, and B. Sudakov, Embedding rainbow trees with applications to graph labelling and decomposition , arXiv:1803.03316

    work page internal anchor Pith review Pith/arXiv arXiv

  24. [24]

    J. Plücker, System der analytischen Geometrie, auf neue Betractungswe isen gegründet, und insbesondere eine ausführliche Theorie der Curven dritter Ordnung entha lend, Duncker und Humboldt, Berlin, 1835

    work page

  25. [25]

    D. K. Ray-Chaudhuri and R. M. Wilson, Solution of Kirkman ’s schoolgirl problem , Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles , Calif., 1968), Amer. Math. Soc., Providence, R.I., 1971, pp. 187–203

    work page 1968

  26. [26]

    Ringel, Problem 25, Theory of Graphs and its Applications (Proc

    G. Ringel, Problem 25, Theory of Graphs and its Applications (Proc. Int. Symp. Smo lenice 1963), Czech. Acad. Sci., Prague, 1963

    work page 1963

  27. [27]

    Rödl, On a packing and covering problem , European J

    V. Rödl, On a packing and covering problem , European J. Combin. 6 (1985), no. 1, 69–78

    work page 1985

  28. [28]

    Steiner, Combinatorische aufgabe , Journal für die reine und angewandte Mathematik 45 (1853), 181– 182

    J. Steiner, Combinatorische aufgabe , Journal für die reine und angewandte Mathematik 45 (1853), 181– 182

    work page

  29. [29]

    R. M. Wilson, An existence theory for pairwise balanced designs. III. Pro of of the existence conjectures , J. Combinatorial Theory Ser. A 18 (1975), 71–79. (P A) London School of Economics, Depar tment of Ma thema tics , Houghton Street, London WC2A 2AE, UK E-mail address : p.d.allen@lse.ac.uk (JB) London School of Economics, Depar tment of Ma thema tics...

    work page 1975