betaFeedback

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 K6K_6 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 GG consider the polynomial ring SS whose variables are indexed by the vertices of GG. The edge ideal IGI_G is generated by the monomials xuxvx_u x_v for all edges uvuv of GG. For an ideal II, the central invariants in commutative algebra encoding the algebraic geometric information are the betti numbers βi,j(S/I)\beta_{i,j}(S/I), which are indexed by a pair i,ji,j of positive integers. The existence of geometric structure is certified by βi,j(S/I)>0\beta_{i,j}(S/I) > 0.

Theorem (The Ramsey Theorem for Edge Ideals). For any betti number indices i,ji,j, and number of colors mm, there is a graph FF such that for every mm-coloring of the edges of FF, there is a color ll such that

βi,j(S/IFl)>0,\beta_{i,j}(S/I_{F_l}) > 0,

where FlF_l is the subgraph of FF whose edges are in color ll. Moreover, the number of vertices of FF is at most jm2jm^2.

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 GG is denoted by V(G)V(G) and the edge set by E(G)E(G). A subgraph H⊆GH \subseteq G is a selection of vertices of GG and edges among them from GG. A subgraph is induced if all possible edges among the selected vertices are included. The induced subgraph on W⊆V(G)W \subseteq V(G) is denoted G[W]G[W]. Special classes of graphs as cycles CnC_n, paths PnP_n and complete graphs KnK_n are indexed by their number of vertices nn. The disjoint union of two graphs GG and HH is denoted G⊔HG \sqcup H. A subset of vertices W⊂V(G)W \subset V(G) is independent in GG if there are no edges in G[W]G[W]. For further basic graph theory, see [8].

Topological combinatorics

A simplicial complex Δ\Delta on a vertex set VV is a set of subsets of VV such that if τ∈Δ\tau\in\Delta and σ⊆τ\sigma\subseteq\tau, then σ∈Δ\sigma\in\Delta. The vertex set of all simplicial complexes in this paper are finite. The reduced homology of a simplicial complex Δ\Delta in dimension dd over a field k\mathsf{k} is denoted H~d(Δ;k)\widetilde{H}_d(\Delta;\mathsf{k}). Whenever the specific field k\mathsf{k} is not relevant, it is dropped. The join of two simplicial complexes Δ\Delta and Γ\Gamma on disjoint vertex sets is Δ∗Γ={δ∪γ∣δ∈Δ and γ∈Γ}\Delta* \Gamma= \{\delta\cup\gamma\mid\delta\in\Delta\text{ and } \gamma\in\Gamma\}. For further basic algebraic topology, see Matoušek [29], Munkres [31] or Spanier [34].

Definition 1. The independence complex of a graph GG, denoted by Ind⁡(G)\operatorname{Ind}(G), is the simplicial complex of the independent sets of GG.

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 GG, the edge ideal I(G)I(G) in the ring S=k[xv∣v∈V(G)]S = \mathbb{k}[x_v \mid v \in V(G)] is generated by the monomials xuxvx_u x_v for all edges uvuv of $G.

For an arbitrary ideal II in a ring SS, 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 nn variables, Hilbert’s Syzygy Theorem from 1890 states that the length is finite and at most nn. 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 βi,j(S/I)\beta_{i,j}(S/I). Those numbers are intrinsically linked to geometrical phenomena of the scheme cut out by II 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 GG, set

βi,j(S/I(G))=∑W⊆V(G)∣W∣=jdim⁡kH~j−i−1(Ind⁡(G[W]);k)\beta_{i,j}(S/I(G)) = \sum_{\substack{W \subseteq V(G) \\ |W|=j}} \dim_{\mathbb{k}} \widetilde{H}_{j-i-1}(\operatorname{Ind}(G[W]);\mathbb{k})

for any positive integers ii and jj such that j/2≤i≤j−1j/2 \leq i \leq j-1.

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 GG and HH, denoted by R(G,H)R(G,H), is the minimum positive integer NN such that every 2-coloring of the edges of the complete graph KNK_N contains either a red copy of GG or a blue copy of HH.

The existence of R(G,H)R(G,H) 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 r≥2r \ge2 colors. If one try to avoid KrK_r in each color, then the multicolor Ramsey number is at most e−δkrrke^{-\delta_k r}r^k for some constant δ>0\delta> 0 depending on kk, and sufficiently large kk, as proved by Balister et al [2].

The induced Ramsey number of two graphs GG and HH, denoted by IR(G,H)IR(G,H), is the minimum positive integer NN for which there exists a graph FF on NN vertices such that every 2-coloring of the edges of FF contains either a red induced copy of GG or a blue induced copy of HH. In Ramsey theory it is then common to state that FF arrows GG and HH,

F→(G,H),F \to(G,H),

a notation we will lean on later.

The existence of IR(G,H)IR(G,H) for all finite graphs GG and HH 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 IR(G,H)≤∣V(H)∣60∣V(G)∣2+3IR(G,H) \le|V(H)|^{60|V(G)|^2+3}.

The weak induced Ramsey number of two graphs GG and HH, denoted by IRw(G,H)IR_w(G,H), is the minimum positive integer NN for which there exists a graph FF on NN vertices such that for every 2-coloring of the edges of FF (partitioning the edges into a red subgraph FrF_r and a blue subgraph FbF_b), there is either an induced copy of GG in FrF_r or an induced copy of HH in FbF_b.

The weak induced Ramsey number IRw(G,H)IR_w(G,H) 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 G\mathcal{G} and H\mathcal{H}, the Ramsey number R(G,H)≤NR(\mathcal{G},\mathcal{H}) \le N whenever a two coloring of KNK_N contains a red G∈GG \in\mathcal{G} or a blue H∈HH \in\mathcal{H}. 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 i1,…,imi_1,\ldots,i_m and j1,…,jmj_1,\ldots,j_m be positive integers satisfying ji/2≤ii≤ji−1j_i/2 \le i_i \le j_i-1; kk a field and FF a graph. If there for every mm-edge coloring of FF (partitioning it into the graphs

F1,F2,…,FmF_1,F_2,\ldots,F_m is an ll such that βil,jlk(S/I(Fl))>0\beta^{\mathbf{k}}_{i_l,j_l}(S/I(F_l))>0, then

F→β(i1,j1;i2,j2;…;im,jm;k).F \xrightarrow{\beta} (i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k}).

The existence of an FF 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 i1,…,imi_1,\ldots,i_m and j1,…,jmj_1,\ldots,j_m satisfying jl/2≤il≤jl−1j_l/2 \le i_l \le j_l-1 and a field k\mathbf{k}, there is a graph FF such that

F→β(i1,j1;i2,j2;…;im,jm;k).F \xrightarrow{\beta} (i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k}).

Proof. For an mm-edge coloring of FF, we need to ensure that for every mm-edge coloring, βil,jlk(S/I(Fl))>0\beta^{\mathbf{k}}_{i_l,j_l}(S/I(F_l))>0 for some ll. By Definition 3, this equates to that dim⁡kH~jl−il−1(Ind⁡(Fl[W]);k)>0\dim_{\mathbf{k}}\widetilde{H}_{j_l-i_l-1}(\operatorname{Ind}(F_l[W]);\mathbf{k})>0 for some W⊆V(F)W\subseteq V(F) on jlj_l vertices. For each ll, pick a graph GlG_l on jlj_l vertices such that dim⁡kH~jl−il−1(Ind⁡(Gl);k)>0\dim_{\mathbf{k}}\widetilde{H}_{j_l-i_l-1}(\operatorname{Ind}(G_l);\mathbf{k})>0. By the weak induced Ramsey theorem, there is a graph FF such that any mm-edge coloring of it will have an induced monochromatic GlG_l for some color ll.

Definition 5 (Ramsey number notation for betti numbers). Let i1,…,imi_1,\ldots,i_m and j1,…,jmj_1,\ldots,j_m be positive integers satisfying jl/2≤il≤jl−1j_l/2 \le i_l \le j_l-1 and k\mathbf{k} a field. The Ramsey number

Rβ(i1,j1;i2,j2;…;im,jm;k)R_{\beta}(i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k})

is the smallest positive integer such that there is a graph FF on that number of vertices satisfying

F→β(i1,j1;i2,j2;…;im,jm;k).F \xrightarrow{\beta} (i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k}).

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 i,j,mi,j,m be positive integers satisfying j/2≤i≤j−1j/2 \le i \le j-1 and k\mathbf{k} a field. Set

Rβm(i,j;k)=Rβ(i1,j1;i2,j2;…;im,jm;k)R_{\beta}^{m}(i,j;\mathbf{k})=R_{\beta}(i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k})

where il=ii_l=i and jl=jj_l=j.

Betti numbers do sometimes depend on the choice of the field k\mathbf{k}, but it is unclear if there are non-trivial examples when Ramsey theory does. Any arguments in this paper will be independent of k\mathbf{k} and the notation for how to drop the field has to be agreed upon.

Definition 7 (Field independent notations). Let i1,…,imi_1,\ldots,i_m and j1,…,jmj_1,\ldots,j_m be positive integers satisfying jl/2≤il≤jl−1j_l/2 \le i_l \le j_l-1. If F→β(i1,j1;i2,j2;…;im,jm;k)F\xrightarrow{\beta}(i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k}) for any field k\mathbf{k}, then F→β(i1,j1;i2,j2;…;im,jm)F\xrightarrow{\beta}(i_1,j_1;i_2,j_2;\ldots;i_m,j_m). Set Rβ(i1,j1;i2,j2;…;im,jm)=max⁡kRβ(i1,j1;i2,j2;…;im,jm;k)R_{\beta}(i_1,j_1;i_2,j_2;\ldots;i_m,j_m)=\max_{\mathbf{k}}R_{\beta}(i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k}). Analogously for Rβm(i,j)R_{\beta}^{m}(i,j).

That the max⁡k\max_k in the definition is well defined follows from Theorem 5 or by selecting the GlG_l 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 GG is dim⁡KH~0(Ind⁡(G);k)+1\dim_{\mathbb{K}} \widetilde{H}_0(\operatorname{Ind}(G); \mathbb{k})+1.

Lemma 3. If dim⁡kH~ds(Δs;k)>0\dim_{\mathbb{k}} \widetilde{H}_{d_s}(\Delta_s;\mathbb{k})>0 for s=1,2,…,ts=1,2,\ldots,t then

dim⁡kH~d1+d2+⋯+dt+t−1(Δ1∗Δ2∗⋯∗Δt;k)>0.\dim_{\mathbb{k}} \widetilde{H}_{d_1+d_2+\cdots+d_t+t-1}(\Delta_1 * \Delta_2 * \cdots* \Delta_t;\mathbb{k})>0.

Combining these lemmas yields the technical workhorse required for our main theorem:

Lemma 4. If G=H1⨆H2⨆⋯⨆HtG=H_1\bigsqcup H_2\bigsqcup\cdots\bigsqcup H_t, and for each graph HsH_s

  • there are at least two vertices in HsH_s and

  • one of the vertices of HsH_s is adjacent to all the other vertices,

then dim⁡kH~t−1(Ind⁡(G);k)>0\dim_{\mathbb{k}}\widetilde{H}_{t-1}(\operatorname{Ind}(G);\mathbb{k})>0.

Proof. By Lemma 2 we have that dim⁡kH~0(Ind⁡(Hs);k)>0\dim_{\mathbb{k}}\widetilde{H}_0(\operatorname{Ind}(H_s);\mathbb{k})>0 for each ss, as the vertex in HsH_s adjacent to all others is isolated in the complement of HsH_s 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 i1,…,imi_1,\ldots,i_m and j1,…,jmj_1,\ldots,j_m be positive integers satisfying jl/2≤il≤jl−1j_l/2\leq i_l\leq j_l-1. If N=2+∑l=1m(⌈jljl−il⌉−2)N=2+\sum_{l=1}^{m}\left(\left\lceil\frac{j_l}{j_l-i_l}\right\rceil-2\right) and M=1+∑l=1m(jl−il−1)M=1+\sum_{l=1}^{m}(j_l-i_l-1) then

(KNM)→β(i1,j1;i2,j2;…;im,jm).\binom{K_N}{M}\xrightarrow{\beta}(i_1,j_1;i_2,j_2;\ldots;i_m,j_m).

Proof. Fix an mm-edge coloring of (KNM)\binom{K_N}{M} and a designated vertex of each KNK_N. Now consider the coloring of each KNK_N one by one.

There are N−1=1+∑l=1m(⌈jljl−il⌉−2)N-1=1+\sum_{l=1}^{m}\left(\left\lceil\frac{j_l}{j_l-i_l}\right\rceil-2\right) edges from the designated vertex to the rest of KNK_N. By the pigeonhole principle, there has to be a color ll with at least

1+(⌈jljl−il⌉−2)=⌈jljl−il⌉−11+\left(\left\lceil\frac{j_l}{j_l-i_l}\right\rceil-2\right)=\left\lceil\frac{j_l}{j_l-i_l}\right\rceil-1

edges from the designated vertex in color ll. In that case, we say that the color ll dominates that KNK_N.

Every KNK_N is dominated by a color, and there is a disjoint union of M=1+∑l=1m(jl−il−1)M = 1 + \sum_{l=1}^{m}(j_l-i_l-1) of them in ⨆MKN\bigsqcup_M K_N. By the pigeonhole principle, there is a color ll that dominates at least

1+(jl−il−1)=jl−il1+(j_l-i_l-1)=j_l-i_l

of them.

Fix the two non-negative integers n0n_0 and n1n_1 such that n0+n1=jl−iln_0+n_1=j_l-i_l and

n0⌈jljl−il⌉+n1⌊jljl−il⌋=jl.n_0\left\lceil\frac{j_l}{j_l-i_l}\right\rceil+n_1\left\lfloor\frac{j_l}{j_l-i_l}\right\rfloor=j_l.

For n0n_0 of the KNK_N dominated by the color ll, select subsets W1,W2,…,Wn0W_1,W_2,\ldots,W_{n_0} of cardinality ⌈jljl−il⌉\left\lceil\frac{j_l}{j_l-i_l}\right\rceil of their vertex sets such that

  • the designated vertex is in each WsW_s and

  • all the edges from the designated vertex within each WsW_s is in color ll.

Then select Wn0+1,Wn0+2,…,Wjl−ilW_{n_0+1},W_{n_0+2},\ldots,W_{j_l-i_l} analogously but each of cardinality ⌊jljl−il⌋\left\lfloor\frac{j_l}{j_l-i_l}\right\rfloor.

Let FlF_l be the subgraph of FF defined by the ll-colored edges. The cardinality of W1∪W2∪…∪Wjl−ilW_1\cup W_2\cup\ldots\cup W_{j_l-i_l} is jlj_l and by Lemma 4

dim⁡kH~jl−il−1(Ind⁡(Fl[W1∪W2∪…∪Wjl−il]);k)>0.\dim_k\widetilde{H}_{j_l-i_l-1}\left(\operatorname{Ind}\left(F_l[W_1\cup W_2\cup\ldots\cup W_{j_l-i_l}]\right);k\right)>0.

By Definition 3 we have that βil,jl(S/I(Fl))>0\beta_{i_l,j_l}(S/I(F_l))>0 and

⨆MKN→ β (i1,j1;i2,j2;…;im,jm).\bigsqcup_M K_N \xrightarrow{\ \beta\ } (i_1,j_1;i_2,j_2;\ldots;i_m,j_m).

Corollary 6. For positive integers i1,…,imi_1,\ldots,i_m and j1,…,jmj_1,\ldots,j_m satisfying jl/2≤il≤jl−1,j_l/2\le i_l\le j_l-1,

Rβ(i1,j1;i2,j2;…;im,jm)≤(1+∑l=1m(jl−il−1))(2+∑l=1m(⌈jljl−il⌉−2)).R_\beta(i_1,j_1;i_2,j_2;\ldots;i_m,j_m)\le\left(1+\sum_{l=1}^{m}(j_l-i_l-1)\right)\left(2+\sum_{l=1}^{m}\left(\left\lceil\frac{j_l}{j_l-i_l}\right\rceil-2\right)\right).

Corollary 7. For any positive integers i,j,mi,j,m satisfying j/2≤i≤j−1,j/2\le i\le j-1,

Rβm(i,j)≤(1+m(j−i−1))(2(1−m)+m⌈jj−i⌉).R_\beta^m(i,j)\le(1+m(j-i-1))\left(2(1-m)+m\left\lceil\frac{j}{j-i}\right\rceil\right).

We require the following elementary result:

Proposition 8. If i,j,mi,j,m are positive integers satisfying j/2≤i≤j−1j/2\le i\le j-1 and m≥2m\ge2, then

(1+m(j−i−1))(2(1−m)+m⌈jj−i⌉)≤jm2(1+m(j-i-1))\left(2(1-m)+m\left\lceil\frac{j}{j-i}\right\rceil\right)\le jm^2

Proof.

(1+m(j−i−1))(2(1−m)+m⌈jj−i⌉)≤m(j−i)(2−2m+m(jj−i+1))=m(j−i)(2−m+mjj−i)≤m(j−i)mjj−i=jm2\begin{aligned} (1+m(j-i-1))\left(2(1-m)+m\left\lceil\frac{j}{j-i}\right\rceil\right) &\le m(j-i)\left(2-2m+m\left(\frac{j}{j-i}+1\right)\right)\\ &=m(j-i)\left(2-m+m\frac{j}{j-i}\right)\\ &\le m(j-i)m^{\frac{j}{j-i}}\\ &=jm^2 \end{aligned}

Corollary 9. If i,j,mi,j,m are positive integers satisfying j/2≤i≤j−1j/2\le i\le j-1 and m≥2m\ge2, then Rβm(i,j)≤jm2R_{\beta}^{m}(i,j)\le jm^2.

For certain combination of the indices ii and jj there are linear bounds in mm. In commutative algebra the betti numbers are tabulated in a slightly particular way, and the corollaries are named from that.

Corollary 10 (linear strand). Rβm(i,i+1)≤(i−1)m+2R_{\beta}^{m}(i,i+1)\le(i-1)m+2.

Proof. Rβm(i,i+1)≤(1+m(i+1−i−1))(2(1−m)+m⌈i+1i+1−i⌉)=(i−1)m+2R_{\beta}^{m}(i,i+1)\le(1+m(i+1-i-1))\left(2(1-m)+m\left\lceil\frac{i+1}{i+1-i}\right\rceil\right)=(i-1)m+2.

Corollary 11 (diagonal). Rβm(i,2i)≤2(i−1)m+2R_{\beta}^{m}(i,2i)\le2(i-1)m+2.

Proof. Rβm(i,j)≤(1+m(2i−i−1))(2(1−m)+m⌈2i2i−i⌉)=2(i−1)m+2R_{\beta}^{m}(i,j)\le(1+m(2i-i-1))\left(2(1-m)+m\left\lceil\frac{2i}{2i-i}\right\rceil\right)=2(i-1)m+2.

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 r1,r2,…,rmr_1,r_2,\ldots,r_m be positive integers and r=r1+r2+⋯+rm−m+1r=r_1+r_2+\cdots+r_m-m+1. If

F→β(i1,j1;i2,j2;…;im,jm;k)F \xrightarrow{\beta} (i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k})

then

⋃rF→β(r1i1,r1j1;r2i2,r2j2;…;rmim,rmjm;k)\bigcup_{r} F \xrightarrow{\beta} (r_1i_1,r_1j_1;r_2i_2,r_2j_2;\ldots;r_mi_m,r_mj_m;\mathbf{k})

Proof. Fix an mm-edge coloring of ⋃rF\bigcup_r F. For each copy of FF it is assumed that F→β(i1,j1;i2,j2;…;im,jm;k)F \xrightarrow{\beta} (i_1,j_1;i_2,j_2;\ldots;i_m,j_m;\mathbf{k}) and there is a color ll certifying that by βil,jlkl(S/I(Fl))>0\beta_{i_l,j_l}^{k_l}(S/I(F_l))>0. To be more precise, there is a W⊆FW\subseteq F of cardinality jlj_l such that

dim⁡kH~jl−il−1(Ind⁡(Fl[W]);k)>0.\dim_{\mathbf{k}}\widetilde{H}_{j_l-i_l-1}(\operatorname{Ind}(F_l[W]);\mathbf{k})>0.

In this situation, we declare that the color ll dominates that particular copy of FF.

Every copy of FF is dominated by some color. By the pigeonhole principle, there is a color ll dominating at least rlr_l copies of FF. Denote the sets certifying the color ll dominance by W1,W2,…,WrlW_1,W_2,\ldots,W_{r_l}. By definition

dim⁡kH~jl−il−1(Ind⁡(Fl[Ws]);k)>0\dim_k \widetilde{H}_{j_l-i_l-1}(\operatorname{Ind}(F_l[W_s]);k)>0

for each s=1,2,…,rls=1,2,\ldots,r_l. The independence complex of a disjoint union of graphs is the join of their independence complexes. By Lemma 3,

dim⁡kH~rljl−rlil−1(Ind⁡(Fl[W1⊔W2⊔⋯⊔Wrl]);k)>0.\dim_k \widetilde{H}_{r_lj_l-r_li_l-1}(\operatorname{Ind}(F_l[W_1\sqcup W_2\sqcup\cdots\sqcup W_{r_l}]);k)>0.

This shows that

βrlil,rljl(S/I(Fl))>0\beta_{r_li_l,r_lj_l}(S/I(F_l))>0

and

⋁rF→β(r1i1,r1j1;r2i2,r2j2;…;rmim,rmjm;k).\bigvee_{r}^{F}\xrightarrow{\beta}(r_1i_1,r_1j_1;r_2i_2,r_2j_2;\ldots;r_mi_m,r_mj_m;k).

Corollary 13. Let r=r1+⋯+rm−m+1r=r_1+\cdots+r_m-m+1.

Rβ(r1i1,r1j1;…;rmim,rmjm;k)≤rRβ(i1,j1;…;im,jm;k).R_{\beta}(r_1i_1,r_1j_1;\ldots;r_mi_m,r_mj_m;k)\le rR_{\beta}(i_1,j_1;\ldots;i_m,j_m;k).

Corollary 14.

Rβm(ri,rj;k)≤(m(r−1)+1)Rβ(i,j;k).R_{\beta}^{m}(ri,rj;k)\le(m(r-1)+1)R_{\beta}(i,j;k).

Explicit calculation example

It is usually possible to improve on Theorem 5 by explicit calculations. It states that

⋁3K4→β(3,5;3,5)\bigvee_{3}K_4\xrightarrow{\beta}(3,5;3,5)

as 2+2⌊55−3⌋−2=42+2\left\lfloor\frac{5}{5-3}\right\rfloor-2=4 and 1+2(5−3−1)=31+2(5-3-1)=3. While Theorem 5 provides a general upper bound, it can often be refined via explicit constructions. Although a systematic pruning of vertices from ⋁3K4\bigvee_{3}K_4 could theoretically sharpen the estimate, the resulting proofs would become cumbersome. Instead, direct explicit analysis yields a tighter bound:

Proposition 15. C5⊔K2→β(3,5;3,5)C_5\sqcup K_2\xrightarrow{\beta}(3,5;3,5) and Rβ(3,5;3,5)≤7R_{\beta}(3,5;3,5)\le7.

Proof. Assume the contradiction, that there is a way to color the edges of C5⊔K2C_5\sqcup K_2 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 C5C_5 and $\dim \widetilde{H}_1(\operatorname{Ind}(C_5))=1,

  • (red pentagon) The induced red subgraph is P5P_5 and dim⁡H~1(Ind⁡(P5))=1\dim\widetilde{H}_1(\operatorname{Ind}(P_5)) = 1,

  • (red pentagon) The induced red subgraph is K2⊔P3K_2 \sqcup P_3 and dim⁡H~1(Ind⁡(K2⊔P3))=1\dim\widetilde{H}_1(\operatorname{Ind}(K_2 \sqcup P_3)) = 1,

  • (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 P3P_3. In the coloring of C5⊔K2C_5 \sqcup K_2 we have so far not considered the color of the edge K2K_2, but we know that there has to be a P3P_3 in the C5C_5 of the same color. We have an induced monochromatic K2⊔P3K_2 \sqcup P_3. But dim⁡H~1(Ind⁡(K2⊔P3))=1\dim\widetilde{H}_1(\operatorname{Ind}(K_2 \sqcup P_3)) = 1, which is a contradiction.

Returning to Theorem 5, as condensed in Corollary 6, we had that

Rβ(3r,5r;3r,5r)≤(1+2(5r−3r−1))(2+2(⌈5r5r−3r⌉−2))=16r−4\begin{aligned} R_\beta(3r,5r;3r,5r) \leq\left(1+2(5r-3r-1)\right)\left(2+2\left(\left\lceil\frac{5r}{5r-3r}\right\rceil-2\right)\right) \\ &=16r-4 \end{aligned}

for any positive integer rr. The result of Proposition 15 together with Theorem 12 as condensed in Corollary 13 proves the slightly stronger result

Rβ(3r,5r;3r,5r)≤(2r−1)Rβ(3,5;3,5)=7(2r−1)=14r−7.R_\beta(3r,5r;3r,5r) \leq(2r-1)R_\beta(3,5;3,5)=7(2r-1)=14r-7.

AI use

Only to edit language, not mathematics.

References

  1. [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. [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. [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. [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. [5]D. Conlon, J. Fox, and B. Sudakov, On induced Ramsey numbers, J. Combin. Theory Ser. B 100 (2010), no. 5, 476–495.
  6. [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. [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. [8]R. Diestel, Graph Theory, 6th ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Heidelberg, 2025.
  9. [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. [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. [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. [12]R. Ehrenborg and G. Hetyei, The topology of the independence complex, European J. Combin. 27 (2006), no. 6, 906–923.DOI
  13. [13]D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995.
  14. [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. [15]A. Engström, Independence complexes of claw-free graphs, European J. Combin. 29 (2008), no. 1, 234–241.DOI
  16. [16]A. Engström, Complexes of directed trees and independence complexes, Discrete Math. 309 (2009), no. 10, 3299–3309.
  17. [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. [18]A. Engström and M. T. Stamps, Betti diagrams from graphs, Algebra Number Theory 7 (2013), no. 7, 1725–1742.DOI
  19. [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. [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. [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. [22]J. Herzog and T. Hibi, Componentwise linear ideals, Nagoya Math. J. 153 (1999), 141–153.DOI
  23. [23]J. Herzog and T. Hibi, Monomial Ideals, Graduate Texts in Mathematics, vol. 260, Springer-Verlag London, Ltd., London, 2011.
  24. [24]J. Jonsson, Simplicial Complexes of Graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, Heidelberg, 2008.DOI
  25. [25]J. Jonsson, Certain homology cycles of the independence complex of grids, Discrete Comput. Geom. 43 (2010), no. 4, 927–950.DOI
  26. [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. [27]J. Kim, Topology of independence complexes and cycle structure of hypergraphs, Combinatorica 46 (2026), Paper No. 8.arxiv.org/abs/2408.14321
  28. [28]Y. Kohayakawa, H. J. Prömel, and V. Rödl, Induced Ramsey numbers, Combinatorica 18 (1998), no. 3, 373–404.DOI
  29. [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. [30]E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005.
  31. [31]J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984.
  32. [32]F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2) 30 (1930), 264–286.
  33. [33]V. Rödl, The Dimension of a Graph and Generalized Ramsey Theorems, Master’s thesis, Charles University, Prague, 1973.
  34. [34]E. H. Spanier, Algebraic Topology, McGraw-Hill Book Co., New York, 1966.DOI
  35. [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

Paper details

vlnc:W_n8jdw9a5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents