Minimum Degrees of Minimal Ramsey Graphs for Almost-Cliques

Andrey Grinshpun, Raj Raina, Rik SenguptaJ. Graph Theory 2017 · OpenReview

TL;DR

This paper investigates the minimum degree of "Ramsey H-minimal" graphs, which are the smallest graphs that guarantee a monochromatic copy of a target graph H when their edges are colored. The authors provide exact formulas for the minimum degree of graphs related to cliques and introduce a new class of "Ramsey simple" graphs, offering insights into the structure of these minimal Ramsey graphs.

What Problem Does This Paper Address?

Graph Ramsey theory deals with finding monochromatic substructures in edge-colored complete graphs. A graph $F$ is "Ramsey for $H$" if any 2-coloring of its edges contains a monochromatic copy of a target graph $H$. A graph $F$ is "Ramsey $H$-minimal" if it's Ramsey for $H$, but no proper subgraph of $F$ has this property. The minimum degree of a graph $F$ is denoted by $\delta(F)$.

The central problem this paper addresses is understanding the minimum possible degree, $s(H)$, over all Ramsey $H$-minimal graphs $F$ for a given graph $H$. This value, $s(H)$, is defined as $\min_{F \in M(H)} \delta(F)$, where $M(H)$ is the set of all Ramsey $H$-minimal graphs for $H$. Previous work established bounds like $s(H) \ge 2\delta(H) - 1$, but determining the exact value of $s(H)$ for specific classes of graphs, especially those that are not highly symmetric, remains challenging. This paper focuses on two main areas: calculating $s(H)$ for graphs that are "almost-cliques" (specifically, $H_{t,d}$, a $K_t$ with an additional vertex of degree $d$) and identifying new classes of graphs for which $s(H) = 2\delta(H) - 1$ (Ramsey simple graphs).

Methods

The paper employs a combination of theoretical tools from Ramsey theory and graph construction. Key methods include:

  • BEL Gadgets: The concept of "BEL gadgets" (named after Burr, Erdős, and Lovász) is crucial. These are graphs that allow for forcing specific color patterns within induced subgraphs, which is essential for constructing minimal Ramsey graphs. The paper proves that certain graphs, particularly $H_{t,d}$ for $2 \le d \le t$, possess BEL gadgets.
  • Graph Construction: The authors construct specific graphs to establish upper bounds on $s(H)$. For $H_{t,d}$, they build a graph $F'$ that is Ramsey for $H_{t,d}$ but whose subgraph $F' - v$ (after removing a vertex $v$) is not. This construction, along with the BEL gadget property, allows them to show $s(H_{t,d}) \le d^2$.
  • Ramsey Simple Graph Construction: To show that certain graphs are Ramsey simple (i.e., $s(H) = 2\delta(H) - 1$), they construct a graph $G$ with an independent set $S$ of size $2d-1$. Adding a vertex connected to $d$ vertices of $S$ creates a copy of $H$. This construction, combined with BEL gadgets and a specific vertex property (neighborhood is an independent set, and the graph minus the vertex and its neighborhood is connected), leads to the result $s(H) \le 2d-1$.
  • Inductive Arguments and Case Analysis: Many proofs involve inductive steps or careful case analysis, particularly when dealing with colorings and ensuring no monochromatic copies of $H$ are formed.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Surprising Minimum Degree for $H_{t,d}$: The paper reveals that $s(H_{t,d}) = d^2$ for $1 < d < t$. This is particularly surprising for $d=2$, where $s(H_{t,2}) = 4$, a value much smaller than the previously known $s(H_{t,1}) = t-1$. This suggests that even small increases in the degree of the "extra" vertex can drastically reduce the minimum degree required for Ramsey minimality.
  • New Class of Ramsey Simple Graphs: The paper identifies a new class of graphs that are Ramsey simple: $d$-regular, 3-connected, triangle-free graphs with a specific connectivity property (removing a vertex and its neighborhood leaves a connected graph). This extends the known families of Ramsey simple graphs and suggests that many triangle-free graphs might be Ramsey simple.
  • The Role of BEL Gadgets: The paper strongly emphasizes the utility of BEL gadgets. Their existence is a powerful tool for constructing minimal Ramsey graphs and proving upper bounds on $s(H)$. The paper also proves that $H_{t,2}$ possesses BEL gadgets, a non-trivial result.
  • Connecting Graph Properties to Ramsey Minimality: The work highlights how specific structural properties of a graph (like connectivity, regularity, and the nature of vertex neighborhoods) directly influence its minimum degree in the context of Ramsey theory.

Key Results

  • Exact Formula for $s(H_{t,d})$: For $1 < d < t$, $s(H_{t,d}) = d^2$. This complements known results for $d=0, 1, t$.
  • Ramsey Simplicity for Specific Graphs: A $d$-regular, 3-connected, triangle-free graph $H$ with a vertex $v$ such that $N(v)$ is an independent set and $H - v - N(v)$ is connected, satisfies $s(H) = 2\delta(H) - 1$.
  • $H_{t,2}$ has BEL Gadgets: The paper proves that $H_{t,2}$ possesses BEL gadgets for $2 \le d \le t$.

Limitations and Future Work

  • Conjectures: The paper leaves several conjectures open:
  • Whether all bipartite graphs without isolated vertices are Ramsey simple.
  • Whether all connected triangle-free graphs are Ramsey simple.
  • Whether all 2-connected graphs have BEL gadgets.
  • A bound for $s(H)$ for general connected graphs: $s(H) \le \delta(n-1)$.
  • Algorithmic Question: The paper poses the question of whether there exists an efficient algorithm to compute $s(H)$ for a given graph $H$.
  • Random Graphs: The paper asks if $s(G(n,p))$ can be described probabilistically in terms of graph parameters for random graphs.
  • Technical Constraints: While the conditions for Ramsey simplicity are noted as not overly restrictive, they are still specific technical requirements that might not hold for all graphs in the broader classes considered.

Summary updated

Abstract

For graphs F and H, we say F is Ramsey for H if every 2-coloring of the edges of F contains a monochromatic copy of H. The graph F is Ramsey H-minimal if F is Ramsey for H and there is no proper subg...
BibTeX
@article{grinshpun2017minimum,
  author = {Andrey Grinshpun and Raj Raina and Rik Sengupta},
  title = {{Minimum Degrees of Minimal Ramsey Graphs for Almost-Cliques}},
  journal = {J. Graph Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=bN0MJt0s_y},
}
Figure