pith. sign in

arxiv: 2403.10515 · v2 · submitted 2024-03-15 · 🧮 math.CO

Packing the largest trees in the tree packing conjecture

Barnab\'as Janzer , Richard Montgomery This is my paper

Pith reviewed 2026-05-24 02:27 UTC · model grok-4.3

classification 🧮 math.CO
keywords tree packing conjectureBollobás conjectureGyőriás conjecturegraph packingcomplete graphstree embeddings
0
0 comments X

The pith

A linear number of the largest trees from any sequence of sizes 1 to n pack into K_n for large n.

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

The Győriás tree packing conjecture asserts that any trees T1 to Tn with |Ti| equal to i pack into the complete graph Kn. Bollobás conjectured that the largest k of them pack for any fixed k once n exceeds some threshold. Only the cases k at most 5 were known. The paper establishes the full Bollobás conjecture and strengthens it to a linear number of the largest trees. A positive constant c exists so that the largest cn trees always pack when n is large enough relative to c.

Core claim

Bollobás's conjecture holds: for every fixed k the largest k trees in any sequence T1,...,Tn with |Ti|=i pack into Kn once n is large enough. Moreover there is a positive constant c such that the largest cn trees pack into Kn for all sufficiently large n.

What carries the argument

Packing the largest cn trees into Kn for a positive constant c, extending the fixed-k case of Bollobás's conjecture.

If this is right

  • The largest k trees pack for every fixed k once n is large enough.
  • The result covers any sequence whose trees have consecutive integer sizes from n down to 1.
  • A linear-size collection of trees whose total vertex count is quadratic in n embeds edge-disjointly into Kn.
  • Only the smaller trees in the sequence remain after the large ones are packed.

Where Pith is reading between the lines

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

  • The remaining smaller trees might be packable in the leftover graph after the large ones are placed.
  • The same argument may adapt to host graphs that are dense but not complete.
  • Quantitative versions could give explicit lower bounds on the linear coefficient c.

Load-bearing premise

n must exceed a threshold that grows with the linear coefficient c.

What would settle it

A sequence of trees T1 to Tn with |Ti|=i such that the largest cn trees fail to pack into Kn for some fixed c greater than zero and for arbitrarily large n.

Figures

Figures reproduced from arXiv: 2403.10515 by Barnab\'as Janzer, Richard Montgomery.

Figure 1
Figure 1. Figure 1: Grids of vertices in Wi , i ∈ [7], corresponding to the sequences P1, S1, S2, P2, S3, S4, P3, P4, S5, S6, P5, S7, P6, P7, S8, S9, S10, S11 (left) and S1, P1, P2, P3, S2, S3, S4, P4, S5, S6, P5, S7, P6, S8, S9, P7, S10, S11 (right). v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 W1 W2 W3 W4 W5 W6 W7 2 1 1 3 4 5 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 W1 W2 W3 W4 W5 W6 W7 2 1 1 3 4 5 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The order of the vertices (mostly) covered by the embedding. Firstly, part of [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Steps I and II of the embedding when all the path-like trees are paths. The arrows indicate the embedded edge is connected to X = {vr+1, . . . , vn}. Pi : Pi+1 : Wi,j Pi : Pi+1 : Wi,i−1 Pi : Pi+1 : Wi,i Pi : Pi+1 : Wi,i+1 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Embedding part of Pi and Pi+1 together to cover Wi,j in the four cases j ≤ i − 2, j = i − 1, j = i and j = i + 1, while omitting only the vertices marked by a ×. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Embedding part of Pi and Pi+1 together to cover Wi,j when j ≤ i − 2, while omitting only the vertices marked by a ×, when the ‘artificial end’ of Pi used is not a path but a more complicated tree. Here the multiple arrows leading to the right make it more difficult to embed this artificial end, so additional vertices in Wi,j may be omitted, to be later covered by other leaves of the tree. this for all j ∈ … view at source ↗
read the original abstract

The famous tree packing conjecture of Gy\'arf\'as from 1976 says that any sequence of trees $T_1,\ldots,T_n$ such that $|T_i|=i$ for each $i\in [n]$ packs into the complete $n$-vertex graph $K_n$. Packing even just the largest trees in such a sequence has proven difficult, with Bollob\'as drawing attention to this in 1995 by conjecturing that, for each $k$, if $n$ is sufficiently large then the largest $k$ trees in any such sequence can be packed into $K_n$. This has only been shown for $k\leq 5$, by \.{Z}ak, despite many partial results and much related work on the full tree packing conjecture. We prove Bollob\'as's conjecture, by showing that, moreover, a linear number of the largest trees can be packed in the tree packing conjecture.

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 / 2 minor

Summary. The paper proves Bollobás's 1995 conjecture that for every fixed k the k largest trees from any sequence T_1 … T_n with |T_i|=i pack into K_n when n is sufficiently large; it strengthens the statement by showing that a linear number (in n) of the largest trees pack into K_n for n large enough.

Significance. Resolving Bollobás's conjecture constitutes a substantial advance on the 1976 Győri tree-packing conjecture. The linear strengthening goes beyond the fixed-k formulation originally conjectured and supplies an explicit quantitative improvement that had been open despite prior work for k≤5.

major comments (1)
  1. The abstract asserts that 'a linear number' of the largest trees pack, yet neither the coefficient of the linear term nor the dependence of the 'sufficiently large' threshold on that coefficient is stated. Because the existence of some positive linear density is the central new claim, the quantitative form of the threshold must be made explicit in the main theorem statement (presumably Theorem 1.1 or the statement in §1).
minor comments (2)
  1. Notation for the sequence of trees and the packing condition should be introduced once in §1 and used consistently; the current abstract uses both 'the tree packing conjecture' and 'the largest trees in such a sequence' without a single forward reference.
  2. The introduction should contain a short paragraph comparing the new linear bound with the best previously known fixed-k results (k≤5) and with any known lower bounds on the number of packable trees.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment of the paper and for highlighting the central claim. We respond to the single major comment below.

read point-by-point responses

  1. Referee: The abstract asserts that 'a linear number' of the largest trees pack, yet neither the coefficient of the linear term nor the dependence of the 'sufficiently large' threshold on that coefficient is stated. Because the existence of some positive linear density is the central new claim, the quantitative form of the threshold must be made explicit in the main theorem statement (presumably Theorem 1.1 or the statement in §1).

    Authors: We agree that the main theorem statement should make the linear density explicit rather than using only the phrase 'a linear number.' In the revised version we will restate Theorem 1.1 to read: there exists an absolute constant c>0 such that, for every n sufficiently large (depending on c), at least floor(c n) of the largest trees from any sequence T_1,...,T_n with |T_i|=i pack into K_n. The proof already yields such a c (albeit a small one obtained by tracking the constants through the embedding lemmas); we will add a brief remark after the theorem indicating how c arises from the argument. This addresses the referee's request for an explicit quantitative form without altering the result itself. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper is a direct combinatorial proof of an external conjecture (Bollobás 1995) by establishing the stronger statement that a linear number of largest trees pack into K_n for n large enough. The derivation chain consists of standard graph-theoretic packing arguments and does not reduce any claimed result to a fitted parameter, self-definition, or load-bearing self-citation; prior results (e.g., Zak for k≤5) are cited only as context and are not invoked to force the main theorem. The 'n sufficiently large' quantifier is an ordinary existence statement in the proof and does not create circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions and lemmas from graph theory; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions and basic properties of trees and complete graphs as used in combinatorial graph theory.
    The statement is phrased entirely in the language of these objects.

pith-pipeline@v0.9.0 · 5684 in / 1095 out tokens · 33994 ms · 2026-05-24T02:27:17.957628+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Allen, J

    P. Allen, J. B¨ ottcher, D. Clemens, J. Hladk´ y, D. Piguet, and A. Taraz. The tree packing conjecture for trees of almost linear maximum degree. arXiv preprint arXiv:2106.11720 , 2021

    work page arXiv 2021

  2. [2]

    Balogh and C

    J. Balogh and C. Palmer. On the tree packing conjecture. SIAM Journal on Discrete Mathematics , 27(4):1995–2006, 2013

    work page 1995

  3. [3]

    Bollob´ as

    B. Bollob´ as. Some remarks on packing trees. Discrete Mathematics, 46(2):203–204, 1983

    work page 1983

  4. [4]

    Bollob´ as.Modern Graph Theory

    B. Bollob´ as.Modern Graph Theory. Springer, 1998

    work page 1998

  5. [5]

    Bollob´ as

    B. Bollob´ as. Extremal graph theory. In Handbook of Combinatorics, vol. II . Elsevier, 1995

    work page 1995

  6. [6]

    B¨ ottcher, J

    J. B¨ ottcher, J. Hladk´ y, D. Piguet, and A. Taraz. An approximate version of the tree packing conjec- ture. Israel Journal of Mathematics , 211(1):391–446, 2016

    work page 2016

  7. [7]

    Ferber and W

    A. Ferber and W. Samotij. Packing trees of unbounded degrees in random graphs. Journal of the London Mathematical Society, 99(3):653–677, 2019

    work page 2019

  8. [8]

    P. C. Fishburn. Packing graphs with odd and even trees. Journal of Graph Theory , 7(3):369–383, 1983. 32

    work page 1983

  9. [9]

    Gy´ arf´ as and J

    A. Gy´ arf´ as and J. Lehel. Packing trees of different order into Kn. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), vol. I , Colloquia Mathematica Societatis J´ anos Bolyai 18, pages 463–469. North-Holland, Amsterdam, 1978

    work page 1976

  10. [10]

    Havet, B

    F. Havet, B. Reed, M. Stein, and D. R. Wood. A variant of the Erd˝ os-S´ os conjecture. Journal of Graph Theory, 94(1):131–158, 2020

    work page 2020

  11. [11]

    A. M. Hobbs, B. A. Bourgeois, and J. Kasiraj. Packing trees in complete graphs. Discrete mathe- matics, 67(1):27–42, 1987

    work page 1987

  12. [12]

    F. Joos, J. Kim, D. K¨ uhn, and D. Osthus. Optimal packings of bounded degree trees. Journal of the European Mathematical Society, 21(12):3573–3647, 2019

    work page 2019

  13. [13]

    Keevash and K

    P. Keevash and K. Staden. Ringel’s tree packing conjecture in quasirandom graphs. Journal of the European Mathematical Society, in press

    work page

  14. [14]

    Krivelevich

    M. Krivelevich. Embedding spanning trees in random graphs. SIAM Journal on Discrete Mathemat- ics, 24(4):1495–1500, 2010

    work page 2010

  15. [15]

    Montgomery, A

    R. Montgomery, A. Pokrovskiy, and B. Sudakov. A proof of Ringel’s conjecture. Geometric and Functional Analysis, 31(3):663–720, 2021

    work page 2021

  16. [16]

    H. J. Straight. Packing trees of different size into the complete graph. Annals of the New York Academy of Sciences, 328(1):190–192, 1979

    work page 1979

  17. [17]

    N. C. Wormald. The differential equation method for random graph processes and greedy algorithms. In Lectures on approximation and randomized algorithms , pages 73–155, 1999

    work page 1999

  18. [18]

    A. ˙Zak. Packing large trees of consecutive orders. Discrete Mathematics, 340(2):252–263, 2017

    work page 2017

  19. [19]

    Zaks and C

    S. Zaks and C. L. Liu. Decomposition of graphs into trees. In Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing , Congressus Numerantium XIX, pages 643–654, 1977. 33

    work page 1977