pith. sign in

arxiv: 1906.09185 · v2 · pith:HMITZHIQnew · submitted 2019-06-21 · 🧮 math.CO · cs.DM

The size Ramsey number of graphs with bounded treewidth

Nina Kamcev , Anita Liebenau , David R. Wood , Liana Yepremyan This is my paper

Pith reviewed 2026-05-25 18:51 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords ramsey numbersize ramsey numbertreewidthbounded degreesparse graphsdegeneracy
0
0 comments X

The pith

If H has bounded maximum degree and treewidth, there exists a graph G with O(|V(H)|) edges that is Ramsey for H, yet the treewidth of any such G cannot be bounded by any function of the treewidth of H alone.

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

The paper establishes that bounded maximum degree together with bounded treewidth in a graph H guarantees a Ramsey graph G whose number of edges is linear in the number of vertices of H. This enlarges the known class of graphs admitting such sparse Ramsey graphs beyond those with bounded bandwidth. At the same time, the paper proves that no function of the treewidth of H can upper-bound the treewidth of every Ramsey graph for H, and that this negative statement remains true when H is restricted to trees. The two directions together separate the edge count achievable under a degree bound from any structural bound measured by treewidth or degeneracy.

Core claim

If the maximum degree and treewidth of H are bounded, then there is a graph G with O(|V(H)|) edges that is Ramsey for H. On the other hand, the treewidth of a graph G that is Ramsey for H cannot be bounded in terms of the treewidth of H alone, even if H is a tree; the same holds when treewidth is replaced by degeneracy.

What carries the argument

A graph G with O(|V(H)|) edges such that every 2-edge-coloring of G contains a monochromatic copy of H, when H has bounded maximum degree and bounded treewidth.

If this is right

  • The size Ramsey number of H is at most linear in |V(H)| whenever both maximum degree and treewidth of H are bounded.
  • The same linear bound holds for every graph of bounded bandwidth, since bounded bandwidth implies bounded degree and bounded treewidth.
  • For every tree H the treewidth of every Ramsey graph for H grows unboundedly with |V(H)|.
  • For every tree H the degeneracy of every Ramsey graph for H likewise grows unboundedly with |V(H)|.

Where Pith is reading between the lines

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

  • The degree bound appears essential for obtaining a linear number of edges; without it the treewidth lower bound already forces super-linear growth in many structural measures.
  • The separation between edge sparsity and treewidth sparsity suggests that other width parameters such as pathwidth or treedepth may behave like treewidth in the negative direction.

Load-bearing premise

The positive linear-edge result requires the additional assumption that H has bounded maximum degree.

What would settle it

Exhibit a sequence of graphs H_n each with bounded maximum degree and bounded treewidth such that every Ramsey graph for H_n has more than c|V(H_n)| edges for every constant c, or exhibit a tree T such that every Ramsey graph for T has treewidth bounded by a constant independent of |V(T)|.

Figures

Figures reproduced from arXiv: 1906.09185 by Anita Liebenau, David R. Wood, Liana Yepremyan, Nina Kamcev.

Figure 1
Figure 1. Figure 1: (a) tree T, (b) truncation T 0 , (c) the corresponding bags, (d) embedding of T Kk where [xi ] means {xi} × Kk Note that (P2) implies that at most (d + 1)k vertices are embedded in Vg(x0) , and every other Vg(x) (with x 6= x0) will contain at most (d + d 2 )k embedded vertices by (P3). Moreover, (P4) will be satisfied for edges of f(T Kk) embedded inside one partition class Vj . To guarantee that those edg… view at source ↗
read the original abstract

A graph $G$ is Ramsey for a graph $H$ if every 2-colouring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a `sparse' graph $G$ that is Ramsey for $H$? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of $H$ are bounded, then there is a graph $G$ with $O(|V(H)|)$ edges that is Ramsey for $H$. This was previously only known for the smaller class of graphs $H$ with bounded bandwidth. On the other hand, we prove that the treewidth of a graph $G$ that is Ramsey for $H$ cannot be bounded in terms of the treewidth of $H$ alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and $H$ is a tree.

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 paper proves two results on size Ramsey numbers for graphs H of bounded treewidth. If both the maximum degree and treewidth of H are bounded, there exists a graph G with O(|V(H)|) edges that is Ramsey for H (extending the known case of bounded bandwidth). Separately, for any tree H the treewidth of any G that is Ramsey for H cannot be bounded by any function of tw(H); the same holds when treewidth is replaced by degeneracy.

Significance. If the results hold, the positive theorem enlarges the class of H for which linear-size Ramsey graphs are known to exist, while the negative theorem shows that treewidth (or degeneracy) of H is insufficient to control the treewidth or degeneracy of Ramsey graphs G, even when H is a tree. The separation between the two statements, with the degree bound stated explicitly for the positive direction, clarifies the parameters that matter for sparse Ramsey graphs.

minor comments (2)
  1. [Abstract] The abstract and introduction state the two theorems cleanly, but the dependence of the O(|V(H)|) bound on the degree and treewidth parameters of H is not made explicit in the statement; adding this would strengthen the claim.
  2. [Introduction] Standard 2-edge-coloring definition of the Ramsey property is used throughout; confirm that all citations to prior bandwidth results (e.g., the work being extended) appear in the introduction and are referenced consistently in the proofs.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our results and for recommending minor revision. No major comments were raised, so we will proceed with any minor editorial adjustments in the revised version.

Circularity Check

0 steps flagged

No circularity; pure existence/non-existence theorems on standard definitions

full rationale

The paper states two conditional theorems using the standard 2-edge-coloring definition of the Ramsey property and the standard definitions of treewidth, degeneracy, and maximum degree. The positive result proves existence of a linear-size Ramsey graph G under the joint bounded-degree + bounded-treewidth hypothesis on H; the negative result proves that no function of tw(H) alone can bound tw(G) (or degeneracy) for Ramsey graphs G, even when H is a tree. Both directions rest on combinatorial constructions and lower-bound arguments that invoke only external, non-self-referential graph-theoretic facts. No equations, fitted parameters, self-definitional loops, or load-bearing self-citations appear; the derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies entirely on standard definitions and properties of treewidth, degeneracy, and the Ramsey property; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • standard math Treewidth and degeneracy are well-defined graph parameters satisfying their standard monotonicity and minor-closed properties.
    Invoked implicitly when stating that bounded treewidth of H implies existence of sparse G and when proving unbounded treewidth of G for trees.
  • standard math The Ramsey property is defined via 2-edge-colorings and monochromatic subgraphs.
    Central to both the positive construction and the negative lower-bound argument.

pith-pipeline@v0.9.0 · 5709 in / 1490 out tokens · 32120 ms · 2026-05-25T18:51:36.979812+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

43 extracted references · 43 canonical work pages · 2 internal anchors

  1. [1]

    Allen, G

    P. Allen, G. Brightwell, and J. Skokan. Ramsey goodness and otherwise.Combinatorica, 33(2):125–160, 2013

    work page 2013

  2. [2]

    Alon and F

    N. Alon and F. R. Chung. Explicit construction of linear sized tolerant networks.Discrete Mathematics, 72(1-3):15–19, 1988

    work page 1988

  3. [3]

    J. Beck. On size Ramsey number of paths, trees, and circuits. I.J. Graph Theory, 7(1):115–129, 1983

    work page 1983

  4. [4]

    J. Beck. On size Ramsey number of paths, trees and circuits. II. InMathematics of Ramsey theory, pages 34–45. Springer, 1990

    work page 1990

  5. [5]

    Berger, Y

    S. Berger, Y. Kohayakawa, G. S. Maesaka, T. Martins, W. Mendonça, G. O. Mota, and O. Parczyk. The size-Ramsey number of powers of bounded degree trees. arXiv:1907.03466

    work page arXiv 1907

  6. [6]

    H. L. Bodlaender. A partialk-arboretum of graphs with bounded treewidth.Theoret. Comput. Sci., 209(1-2):1–45, 1998

    work page 1998

  7. [7]

    Bollobás

    B. Bollobás. Random graphs, volume 73 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, second edition, 2001

    work page 2001

  8. [8]

    S. A. Burr, P. Erdős, and L. Lovász. On graphs of Ramsey type.Ars Combinatoria, 1(1):167–190, 1976

    work page 1976

  9. [9]

    Clemens, M

    D. Clemens, M. Jenssen, Y. Kohayakawa, N. Morrison, G. O. Mota, D. Reding, and B. Roberts. The size–Ramsey number of powers of paths.J. Graph Theory, 91(3):290–299, 2019

    work page 2019

  10. [10]

    Clemens, M

    D. Clemens, M. Miralaie, D. Reding, M. Schacht, and A. Taraz. On the size-Ramsey number of grid graphs. arXiv:1906.06915

    work page arXiv 1906

  11. [11]

    D. Conlon. Question suggested for the ATI–HIMR Focused Research Workshop: Large– scale structures in random graphs, Alan Turing Institute, December, 2016

    work page 2016

  12. [12]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov. Short proofs of some extremal results.Combinatorics, Probability and Computing, 23(1):8–28, 2014

    work page 2014

  13. [13]

    Dellamonica Jr

    D. Dellamonica Jr. The size-Ramsey number of trees.Random Structures & Algorithms, 40(1):49–73, 2012

    work page 2012

  14. [14]

    Ding and B

    G. Ding and B. Oporowski. Some results on tree decomposition of graphs.J. Graph Theory, 20(4):481–499, 1995

    work page 1995

  15. [15]

    G. Ding, B. Oporowski, D. P. Sanders, and D. Vertigan. Partitioning graphs of bounded tree-width. Combinatorica, 18(1):1–12, 1998

    work page 1998

  16. [16]

    Dudek and P

    A. Dudek and P. Prałat. An alternative proof of the linearity of the size-Ramsey number of paths. Combinatorics, Probability and Computing, 24(3):551–555, 2015

    work page 2015

  17. [17]

    P. Erdős. On the combinatorial problems which I would most like to see solved.Combi- natorica, 1(1):25–42, 1981

    work page 1981

  18. [18]

    Erdős, R

    P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. The size Ramsey number. Periodica Mathematica Hungarica, 9(1-2):145–161, 1978

    work page 1978

  19. [19]

    Erdős and L

    P. Erdős and L. Lovász. Problems and results on3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, volume 10 ofColloq. Math. Soc. János 12 Bolyai, pages 609–627. North-Holland, 1975

    work page 1975

  20. [20]

    J. Folkman. Graphs with monochromatic complete subgraphs in every edge coloring. SIAM J. Appl. Math., 18:19–24, 1970

    work page 1970

  21. [21]

    J. Fox, A. Grinshpun, A. Liebenau, Y. Person, and T. Szabó. What is Ramsey–equivalent to a clique?J. Combinatorial Theory Ser. B, 109:120–133, 2014

    work page 2014

  22. [22]

    Fox and K

    J. Fox and K. Lin. The minimum degree of Ramsey–minimal graphs.J. Graph Theory, 54(2):167–177, 2007

    work page 2007

  23. [23]

    Friedman

    J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. Memoirs of the American Mathematical Society, 910, 2008

    work page 2008

  24. [24]

    Friedman and N

    J. Friedman and N. Pippenger. Expanding graphs contain all small trees.Combinatorica, 7(1):71–76, 1987

    work page 1987

  25. [25]

    J. Han, M. Jenssen, Y. Kohayakawa, G. O. Mota, and B. Roberts. The multicolour size–Ramsey number of powers of paths.arXiv preprint arXiv:1811.00844, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  26. [26]

    D. J. Harvey and D. R. Wood. Parameters tied to treewidth.J. Graph Theory, 84(4):364– 385, 2017

    work page 2017

  27. [27]

    P. E. Haxell and Y. Kohayakawa. The size-Ramsey number of trees.Israel J. Mathematics, 89(1-3):261–274, 1995

    work page 1995

  28. [28]

    P. E. Haxell, Y. Kohayakawa, and T. Łuczak. The induced size-Ramsey number of cycles. Combinatorics, Probability and Computing, 4(3):217–239, 1995

    work page 1995

  29. [29]

    P. Horn, K. G. Milans, and V. Rödl. Degree Ramsey numbers of closed blowups of trees. Electron. J. Combin., 21(2):Paper 2.5, 6, 2014

    work page 2014

  30. [30]

    Jiang, K

    T. Jiang, K. G. Milans, and D. B. West. Degree Ramsey numbers for cycles and blowups of trees. European J. Combin., 34(2):414–423, 2013

    work page 2013

  31. [31]

    X. Ke. The size Ramsey number of trees with bounded degree.Random Structures & Algorithms, 4(1):85–97, 1993

    work page 1993

  32. [32]

    Kövari, V

    T. Kövari, V. T. Sós, and P. Turán. On a problem of K. Zarankiewicz.Colloquium Math., 3:50–57, 1954

    work page 1954

  33. [33]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. Pseudo-random graphs. In More sets, graphs and numbers, pages 199–262. Springer, 2006

    work page 2006

  34. [34]

    Mütze and U

    T. Mütze and U. Peter. On globally sparse Ramsey graphs. Discrete Mathematics, 313(22):2626–2637, 2013

    work page 2013

  35. [35]

    Nešetřil and V

    J. Nešetřil and V. Rödl. The Ramsey property for graphs with forbidden complete subgraphs. J. Combinatorial Theory Ser. B, 20(3):243–249, 1976

    work page 1976

  36. [36]

    Ramsey goodness of cycles

    A. Pokrovskiy and B. Sudakov. Ramsey goodness of cycles. arXiv:1807.02313

    work page internal anchor Pith review Pith/arXiv arXiv

  37. [37]

    Pokrovskiy and B

    A. Pokrovskiy and B. Sudakov. Ramsey goodness of paths.Journal of Combinatorial Theory, Series B, 122:384 – 390, 2017

    work page 2017

  38. [38]

    B. A. Reed. Algorithmic aspects of tree width. InRecent advances in algorithms and combinatorics, volume 11 ofCMS Books Math./Ouvrages Math. SMC, pages 85–107. Springer, New York, 2003

    work page 2003

  39. [39]

    Rödl and E

    V. Rödl and E. Szemerédi. On size Ramsey numbers of graphs with bounded degree. Combinatorica, 20(2):257–262, 2000

    work page 2000

  40. [40]

    J. Rollin. Personal communication

    work page

  41. [41]

    Szabó, P

    T. Szabó, P. Zumstein, and S. Zürcher. On the minimum degree of minimal Ramsey graphs. J. Graph Theory, 64(2):150–164, 2010

    work page 2010

  42. [42]

    D. R. Wood. On tree-partition-width.European J. Combin., 30(5):1245–1253, 2009. 13

    work page 2009

  43. [43]

    X. Zhu. Chromatic Ramsey numbers.Discrete Math., 190(1-3):215–222, 1998. 14

    work page 1998