WorksMathematics
Ramsey Theory for Edge Ideals
Abstract
We initiate the study of Ramsey theory for edge ideals. The edge ideal I_G is generated by the monomials x_ux_v for all edges uv of G. A central invariant measuring structure in algebraic geometry and commutative algebra are the betti number beta_{i,j}(S/I) for some ideal I in a ring S. We prove the Ramsey Theorem for Edge Ideals: For any betti number indices i,j, and any number of colors m, there is a graph F such that for every m-coloring of the edges of F, there is a color l such that beta_{i,j}(S/I_{F_l}) >0, where F_l is the subgraph of F whose edges are in color l. Moreover, the number of vertices of F is at most jm^2.
Introduction
Ramsey theory asserts that any sufficiently large graph, regardless of how its edges are partitioned or colored, must contain structured monochromatic substructures. A classical illustration of this principle is that any 2-coloring of the edges of the complete graph necessarily yields a monochromatic triangle. During the one hundred years of Ramsey theory, its deepest results are among the hallmarks of combinatorics in its interaction with other parts of mathematics, for example the existence of arbitrary long arithmetic progressions in the primes.
In this paper we initiate the exploration of synergies between Ramsey theory and commutative algebra, in particular edge ideals. For a graph consider the polynomial ring whose variables are indexed by the vertices of . The edge ideal is generated by the monomials for all edges of . For an ideal , the central invariants in commutative algebra encoding the algebraic geometric information are the betti numbers , which are indexed by a pair of positive integers. The existence of geometric structure is certified by .
Theorem (The Ramsey Theorem for Edge Ideals). For any betti number indices , and number of colors , there is a graph such that for every -coloring of the edges of , there is a color such that
where is the subgraph of whose edges are in color . Moreover, the number of vertices of is at most .
The exact formulation is in Theorem 5 and the upper bound in Corollary 9, which are both in § 4. In that section we also provide the foundational definitions for Ramsey theory for edge ideals, prove some further results and provide some examples. Before that, in § 2, we explain some useful tools from graph theory, topological combinatorics, and commutative algebra, as well as include plenty of references to papers and textbooks aimed at the interaction between methods within those areas. In § 3 we give a brief introduction to the typical questions asked in Ramsey theory to provide context, but that part is not necessary for § 4 and the main theorem of the paper, it is only informative.
Basic notions
Graph theory
All graphs are finite and undirected. The vertex set of a graph is denoted by and the edge set by . A subgraph is a selection of vertices of and edges among them from . A subgraph is induced if all possible edges among the selected vertices are included. The induced subgraph on is denoted . Special classes of graphs as cycles , paths and complete graphs are indexed by their number of vertices . The disjoint union of two graphs and is denoted . A subset of vertices is independent in if there are no edges in . For further basic graph theory, see [8].
Topological combinatorics
A simplicial complex on a vertex set is a set of subsets of such that if and , then . The vertex set of all simplicial complexes in this paper are finite. The reduced homology of a simplicial complex in dimension over a field is denoted . Whenever the specific field is not relevant, it is dropped. The join of two simplicial complexes and on disjoint vertex sets is . For further basic algebraic topology, see Matoušek [29], Munkres [31] or Spanier [34].
Definition 1. The independence complex of a graph , denoted by , is the simplicial complex of the independent sets of .
For further results on independence complexes of graphs, see for example Bayer et al [3], Chudnovsky et al [4], Ehrenborg and Hetyei [12], Engström [15, 16], Jonsson [24, 25] or Kim [26, 27].
Commutative algebra
We restrict our presentation of commutative algebra strictly to the tools required for our applications rather than developing the theory in full generality.
Definition 2. For a graph , the edge ideal in the ring is generated by the monomials for all edges of $G.
For an arbitrary ideal in a ring , one can encode the successive modules of syzygies—the linear dependencies among generators, the relations among those relations, and so forth. The collection of that data is a free resolution and its length is the number of times you need relations among relations among relations and so on. For a polynomial ring on variables, Hilbert’s Syzygy Theorem from 1890 states that the length is finite and at most . In a well defined sense, minimal resolutions are unique, see Eisenbud [13]. The dimensions of the pieces of the minimal resolution are encoded in the betti numbers . Those numbers are intrinsically linked to geometrical phenomena of the scheme cut out by and were introduced to capture intuitive reasoning about intersections between curves in a stringent manner, see Eisenbud [14]. For edge ideals there is a more direct way to compute their betti numbers, and we take that as its definition. By tensoring with the koszul resolution, or applying Hochster’s formula, as explained by Miller and Sturmfels [30], we have that:
Definition 3. For any graph , set
for any positive integers and such that .
Two important concepts of resolutions and betti numbers are linearity and regularity, which we will however not define. In a foundational paper on edge ideals, Fröberg [20] proved that the resolution is linear exactly when the graph is the complement of a chordal graph. Engström and Orlich [17] employed probabilistic techniques common in Ramsey theory to show that the regularity of edge ideals is determined for almost all graphs.
There is a vast literature on edge ideals and their relation to combinatorics, see for example Dochtermann and Engström [10], Dochtermann and Newman [11], Engström and Stamps [18], Ha and Van Tuyl [21], Herzog and Hibi [22], Van Tuyl and Villarreal [35] and the textbook by Herzog and Hibi [23].
Ramsey theory context
In this section we will briefly touch upon the world of Ramsey theory. None of the content of this section is necessary for the remainder of this paper. It’s purely here to contextualize and to explain the choice of notation, definitions, and theorems stated in the next section.
The classical (or ordinary) Ramsey number of two graphs and , denoted by , is the minimum positive integer such that every 2-coloring of the edges of the complete graph contains either a red copy of or a blue copy of .
The existence of for finite graphs was proved by Ramsey in 1928 [32]. For a basic introduction to Ramsey theory, see for example Chapter 9 in Diestel [8]. There are also Ramsey numbers for colors. If one try to avoid in each color, then the multicolor Ramsey number is at most for some constant depending on , and sufficiently large , as proved by Balister et al [2].
The induced Ramsey number of two graphs and , denoted by , is the minimum positive integer for which there exists a graph on vertices such that every 2-coloring of the edges of contains either a red induced copy of or a blue induced copy of . In Ramsey theory it is then common to state that arrows and ,
a notation we will lean on later.
The existence of for all finite graphs and was established independently by Deuber [7], Erdős, Hajnal, and Pósa [19], and Rödl [33]. Conlon, Fox, and Sudakov [5] established near-exponential upper bounds for induced Ramsey numbers, significantly improving upon previous tower-type estimates. The long-standing Kohayakawa–Prömel–Rödl conjecture [28] concerning polynomial bounds for off-diagonal cases was recently resolved in a preprint on the arXiv by Andrades, Campos, Filipe, and Kats [1] as .
The weak induced Ramsey number of two graphs and , denoted by , is the minimum positive integer for which there exists a graph on vertices such that for every 2-coloring of the edges of (partitioning the edges into a red subgraph and a blue subgraph ), there is either an induced copy of in or an induced copy of in .
The weak induced Ramsey number was introduced by Dudek, Grytczuk, and Ruciński [9] and further investigated in [6].
Another direction of generalization is Ramsey theory of properties of graphs or sets of graphs. Given two finite sets of graphs and , the Ramsey number whenever a two coloring of contains a red or a blue . Using the terminology of weak induced Ramsey theory for sets of graphs, the Ramsey numbers of Betti numbers are nothing else than defined by the sets of graphs with certain reduced homology as stated in Definition 3.
Ramsey theory for edge ideals
Definition 4 (Ramsey arrow notation for betti numbers). Let and be positive integers satisfying ; a field and a graph. If there for every -edge coloring of (partitioning it into the graphs
is an such that , then
The existence of an follows the weak induced Ramsey theorem mentioned in the previous section. In Theorem 5 we will prove a stronger theorem based on elementary considerations.
Theorem 1. For any positive integers and satisfying and a field , there is a graph such that
Proof. For an -edge coloring of , we need to ensure that for every -edge coloring, for some . By Definition 3, this equates to that for some on vertices. For each , pick a graph on vertices such that . By the weak induced Ramsey theorem, there is a graph such that any -edge coloring of it will have an induced monochromatic for some color .
Definition 5 (Ramsey number notation for betti numbers). Let and be positive integers satisfying and a field. The Ramsey number
is the smallest positive integer such that there is a graph on that number of vertices satisfying
In ordinary graph theory the hardest cases are when the number of colors grow while the other parameters are fixed, it’s called the diagonal case.
Definition 6 (Diagonal Ramsey number notation for betti numbers). Let be positive integers satisfying and a field. Set
where and .
Betti numbers do sometimes depend on the choice of the field , but it is unclear if there are non-trivial examples when Ramsey theory does. Any arguments in this paper will be independent of and the notation for how to drop the field has to be agreed upon.
Definition 7 (Field independent notations). Let and be positive integers satisfying . If for any field , then . Set . Analogously for .
That the in the definition is well defined follows from Theorem 5 or by selecting the in the proof of Theorem 1 as disjoint unions of complete graphs. We need two elementary lemmas from algebraic topology, the first one follows right off from definitions and the other one from the Künneth formula for joins.
Lemma 2. The number of connected components of the complement of a graph is .
Lemma 3. If for then
Combining these lemmas yields the technical workhorse required for our main theorem:
Lemma 4. If , and for each graph
there are at least two vertices in and
one of the vertices of is adjacent to all the other vertices,
then .
Proof. By Lemma 2 we have that for each , as the vertex in adjacent to all others is isolated in the complement of from the other vertices. The independence complex of the disjoint union of graphs is the join of their independence complexes. By Lemma 3 we are done. □
This is our main theorem.
Theorem 5. Let and be positive integers satisfying . If and then
Proof. Fix an -edge coloring of and a designated vertex of each . Now consider the coloring of each one by one.
There are edges from the designated vertex to the rest of . By the pigeonhole principle, there has to be a color with at least
edges from the designated vertex in color . In that case, we say that the color dominates that .
Every is dominated by a color, and there is a disjoint union of of them in . By the pigeonhole principle, there is a color that dominates at least
of them.
Fix the two non-negative integers and such that and
For of the dominated by the color , select subsets of cardinality of their vertex sets such that
the designated vertex is in each and
all the edges from the designated vertex within each is in color .
Then select analogously but each of cardinality .
Let be the subgraph of defined by the -colored edges. The cardinality of is and by Lemma 4
By Definition 3 we have that and
Corollary 6. For positive integers and satisfying
Corollary 7. For any positive integers satisfying
We require the following elementary result:
Proposition 8. If are positive integers satisfying and , then
Proof.
Corollary 9. If are positive integers satisfying and , then .
For certain combination of the indices and there are linear bounds in . In commutative algebra the betti numbers are tabulated in a slightly particular way, and the corollaries are named from that.
Corollary 10 (linear strand). .
Proof. .
Corollary 11 (diagonal). .
Proof. .
In Ramsey theory it is common that bounds for small Ramsey numbers lift to higher ones, but usually involving large factors. This is much more moderate.
Theorem 12. Let be positive integers and . If
then
Proof. Fix an -edge coloring of . For each copy of it is assumed that and there is a color certifying that by . To be more precise, there is a of cardinality such that
In this situation, we declare that the color dominates that particular copy of .
Every copy of is dominated by some color. By the pigeonhole principle, there is a color dominating at least copies of . Denote the sets certifying the color dominance by . By definition
for each . The independence complex of a disjoint union of graphs is the join of their independence complexes. By Lemma 3,
This shows that
and
Corollary 13. Let .
Corollary 14.
Explicit calculation example
It is usually possible to improve on Theorem 5 by explicit calculations. It states that
as and . While Theorem 5 provides a general upper bound, it can often be refined via explicit constructions. Although a systematic pruning of vertices from could theoretically sharpen the estimate, the resulting proofs would become cumbersome. Instead, direct explicit analysis yields a tighter bound:
Proposition 15. and .
Proof. Assume the contradiction, that there is a way to color the edges of in red and blue without an induced monochromatic subgraph on five vertices with homology in the first dimension.
We may assume that the edge coloring have more red than blue edges on the five cycle. There are four cases:
(1) The induced red subgraph is and $\dim \widetilde{H}_1(\operatorname{Ind}(C_5))=1,
(red pentagon) The induced red subgraph is and ,
(red pentagon) The induced red subgraph is and ,
(red pentagon) Both the induced red and blue subgraphs on five vertices have isolated vertices and thus no homology in its independence complexes.
The only possible coloring is (red pentagon). Note that it includes both a blue and a red induced . In the coloring of we have so far not considered the color of the edge , but we know that there has to be a in the of the same color. We have an induced monochromatic . But , which is a contradiction.
Returning to Theorem 5, as condensed in Corollary 6, we had that
for any positive integer . The result of Proposition 15 together with Theorem 12 as condensed in Corollary 13 proves the slightly stronger result
AI use
Only to edit language, not mathematics.
References
- [1]B. Andrades, M. Campos, R. Filipe, and A. Kats, A solution to the Kohayakawa–Prömel–Rödl conjecture, arXiv:2610.27478, 2026.
- [2]P. Balister, B. Bollobás, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, and M. Tiba, Upper bounds for multicolour Ramsey numbers, J. Amer. Math. Soc. 39 (2026), no. 3, 765–780.arxiv.org/abs/2410.17197
- [3]M. Bayer, R. Danner, T. Holleben, M. Kramer, and Y. Yang, Planar ternary graphs, flag spheres, and Delannoy polynomials, Electron. J. Combin. 33 (2026), no. 3, Paper P3.66.arxiv.org/abs/2509.21705
- [4]M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, Proof of the Kalai–Meshulam conjecture, Israel J. Math. 238 (2020), 639–661.arxiv.org/abs/1810.00065
- [5]D. Conlon, J. Fox, and B. Sudakov, On induced Ramsey numbers, J. Combin. Theory Ser. B 100 (2010), no. 5, 476–495.
- [6]M. Dębski, A. Dudek, J. Grytczuk, J. Ochnio, and A. Ruciński, Weak induced Ramsey numbers, Discrete Math. 346 (2023), no. 12, 113641.
- [7]W. Deuber, Generalizations of Ramsey’s theorem, in Infinite and Finite Sets (Colloq., Keszthely, 1973), Colloq. Math. Soc. János Bolyai, vol. 10, North-Holland, Amsterdam, 1975, pp. 323–332.
- [8]R. Diestel, Graph Theory, 6th ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Heidelberg, 2025.
- [9]A. Dudek, J. Grytczuk, and A. Ruciński, Ordered unavoidable substructures in matchings and random graphs, Adv. Comb. (2023), Paper No. 3, 27 pp.
- [10]A. Dochtermann and A. Engström, Algebraic properties of edge ideals via combinatorial topology, Electron. J. Combin. 16 (2009), no. 2, Research Paper 2, 24 pp.arxiv.org/abs/0810.4120
- [11]A. Dochtermann and A. Newman, Random subcomplexes and Betti numbers of random edge ideals, Int. Math. Res. Not. IMRN (2023), no. 10, 8832–8871.arxiv.org/abs/2104.12882
- [12]R. Ehrenborg and G. Hetyei, The topology of the independence complex, European J. Combin. 27 (2006), no. 6, 906–923.DOI
- [13]D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995.
- [14]D. Eisenbud, The Geometry of Syzygies: A Second Course in Commutative Algebra and Algebraic Geometry, Graduate Texts in Mathematics, vol. 229, Springer-Verlag, New York, 2005.DOI
- [15]A. Engström, Independence complexes of claw-free graphs, European J. Combin. 29 (2008), no. 1, 234–241.DOI
- [16]A. Engström, Complexes of directed trees and independence complexes, Discrete Math. 309 (2009), no. 10, 3299–3309.
- [17]A. Engström and M. Orlich, The regularity of almost all edge ideals, Adv. Math. 435 (2023), Paper No. 109355, 34 pp.arxiv.org/abs/2108.07304
- [18]A. Engström and M. T. Stamps, Betti diagrams from graphs, Algebra Number Theory 7 (2013), no. 7, 1725–1742.DOI
- [19]P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs, in Infinite and Finite Sets (Colloq., Keszthely, 1973), Colloq. Math. Soc. János Bolyai, vol. 10, North-Holland, Amsterdam, 1975, pp. 585–595.
- [20]R. Fröberg, On Stanley-Reisner rings, Topics in Algebra, Part 2 (Warsaw, 1988), pp. 57–70, Banach Center Publ., vol. 26, Part 2, PWN, Warsaw, 1990.DOI
- [21]H. T. Ha and A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, J. Algebraic Combin. 27 (2008), no. 2, 215–245.arxiv.org/abs/math/0606539
- [22]J. Herzog and T. Hibi, Componentwise linear ideals, Nagoya Math. J. 153 (1999), 141–153.DOI
- [23]J. Herzog and T. Hibi, Monomial Ideals, Graduate Texts in Mathematics, vol. 260, Springer-Verlag London, Ltd., London, 2011.
- [24]J. Jonsson, Simplicial Complexes of Graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, Heidelberg, 2008.DOI
- [25]J. Jonsson, Certain homology cycles of the independence complex of grids, Discrete Comput. Geom. 43 (2010), no. 4, 927–950.DOI
- [26]J. Kim, The homotopy type of the independence complex of graphs with no induced cycles of length divisible by 3, European J. Combin. 104 (2022), Paper No. 103534.
- [27]J. Kim, Topology of independence complexes and cycle structure of hypergraphs, Combinatorica 46 (2026), Paper No. 8.arxiv.org/abs/2408.14321
- [28]Y. Kohayakawa, H. J. Prömel, and V. Rödl, Induced Ramsey numbers, Combinatorica 18 (1998), no. 3, 373–404.DOI
- [29]J. Matoušek, Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, 2nd printing, Universitext, Springer-Verlag, Berlin, Heidelberg, 2008.
- [30]E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005.
- [31]J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984.
- [32]F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2) 30 (1930), 264–286.
- [33]V. Rödl, The Dimension of a Graph and Generalized Ramsey Theorems, Master’s thesis, Charles University, Prague, 1973.
- [34]E. H. Spanier, Algebraic Topology, McGraw-Hill Book Co., New York, 1966.DOI
- [35]A. Van Tuyl and R. H. Villarreal, Shellable graphs and sequentially Cohen-Macaulay bipartite graphs, J. Combin. Theory Ser. A 115 (2008), no. 5, 799–814.arxiv.org/abs/math/0701296