A note on Ramsey numbers for minors

This paper establishes asymptotic bounds for the Ramsey number $R_h(k; \ell)$, which guarantees a monochromatic subgraph with Hadwiger number $k$ in any $\ell$-edge-coloring of a complete graph, showing that this value grows proportionally to $k\sqrt{\log k}$.

The Gist

Imagine you are hosting a massive party where every single guest shakes hands with every other guest. Now, imagine you have a box of colored markers, and you decide to color every single handshake either Red or Blue (or maybe more colors if the party gets really big).

The question mathematicians love to ask is: How big does the party need to be before you are guaranteed to find a specific pattern, no matter how you color the handshakes?

This is the heart of Ramsey Theory. Usually, the pattern we look for is a "perfect clique"—a group of friends where everyone knows everyone else, and all their handshakes are the same color.

The New Twist: "The Shrink-and-Delete Game"

In this paper, Maria Axenovich introduces a slightly different, more flexible game. Instead of looking for a perfect clique, she looks for a "Kk-minor."

Think of a "minor" like a Lego sculpture.

• You have a big, messy pile of Lego bricks (your graph).
• You are allowed to glue two bricks together (edge contraction) or throw a brick away (vertex deletion).
• If, after doing this, you can turn your messy pile into a perfect, solid cube of size $k$, then your original pile contained a "Kk-minor."

So, the question becomes: How big must the party be so that, no matter how you color the handshakes, one color will contain a group of people that can be "shrunk and cleaned up" to form a perfect $k$-person clique?

The Main Discovery: The "Party Size" Formula

The paper calculates the exact size of this party (let's call it $n$) needed to guarantee this happens.

1. The Two-Color Scenario (Red vs. Blue)

If you only have two colors, the paper finds that the party size $n$ grows roughly like this:
$$n \approx k \times \sqrt{\log k}$$

The Analogy:
Imagine $k$ is the size of the "perfect group" you are hunting for.

• If you want a group of 10 people ($k=10$), you need a party of roughly $10 \times \sqrt{3} \approx 17$ people.
• If you want a group of 1,000 people, you need a party of roughly $1,000 \times \sqrt{10} \approx 3,160$ people.

The author proves that the party size is very close to $k \sqrt{\log k}$. She gives a very precise "upper limit" (the maximum size you might ever need) and a "lower limit" (the minimum size that definitely works). The numbers are so close that for all practical purposes, the answer is just $k \sqrt{\log k}$.

2. The Multi-Color Scenario

What if you have 3, 4, or 100 colors?
The paper shows that if you have $\ell$ colors, the party size just scales up linearly.
$$n \approx \ell \times k \times \sqrt{\log k}$$

The Analogy:
If you have more colors, it's harder to force a pattern to appear. It's like having more paint colors on a canvas; you need a bigger canvas to guarantee that one specific color covers a big enough area to form your shape. The math says: Just multiply the party size by the number of colors.

Why is this a big deal?

1. It fills a gap: Mathematicians have studied "perfect cliques" (Ramsey numbers) for decades. They have also studied "minors" (Hadwiger numbers) for decades. But they never really put them together until now. This paper connects the two worlds.
2. It's surprisingly efficient: The formula $k \sqrt{\log k}$ is much smaller than the formulas for perfect cliques. This means that even if you can't find a perfect "everyone-knows-everyone" group, you can find a "shrinkable" group much earlier. It's like finding a rough draft of a masterpiece instead of waiting for the final polished version.
3. The "Randomness" Factor: The author uses random graphs (like a party where handshakes are decided by a coin flip) to prove the lower limits. She shows that if the party is too small, a random coloring will almost certainly hide the pattern. But once you cross that threshold, the pattern becomes unavoidable.

The "Small Party" Exceptions

The paper also solves some specific, small puzzles:

• For a group of 3 ($k=3$): You need a party of 5 people. (With 4 people, you can color the handshakes to avoid a triangle).
• For a group of 4 ($k=4$): You need a party of 7 people.

The Bottom Line

Maria Axenovich has figured out the "tipping point" for a very complex game. She tells us exactly how many people need to be in a room, and how many colors we can use, before we are mathematically forced to find a specific type of connected group, even if that group is messy and needs to be "cleaned up" (contracted) to look perfect.

It's a bit like saying: "If you have enough people in a room and enough colors to paint their handshakes, you can't help but create a specific shape, no matter how hard you try to avoid it." And now, we know exactly how many people are needed to make that inevitable.

Technical Summary

Here is a detailed technical summary of the paper "A note on Ramsey numbers for minors" by Maria Axenovich.

1. Problem Statement

The paper investigates the Ramsey number for minors, denoted as $R_h(k; \ell)$.

• Definition: $R_h(k; \ell)$ is the smallest integer $n$ such that any edge coloring of the complete graph $K_n$ with $\ell$ colors contains a monochromatic subgraph with Hadwiger number $k$.
• Hadwiger Number ($h(G)$): The largest integer $k$ such that the graph $G$ contains a $K_k$-minor (a clique of size $k$ obtainable via edge contractions and vertex deletions).
• Context: This extends classical Ramsey theory ($R(k)$, which seeks a monochromatic $K_k$) to graph minors. While the Hadwiger Conjecture ($h(G) \ge \chi(G)$) is a central open problem in graph theory, the specific Ramsey parameter $R_h(k)$ had not been explicitly addressed in the literature prior to this work.

2. Methodology

The author employs a combination of probabilistic methods, extremal graph theory, and structural graph decomposition to establish bounds.

• Upper Bounds (Density Arguments):

  • The proof relies heavily on Thomason's Theorem regarding the minimum edge density required to guarantee a $K_k$-minor. Thomason determined that a graph with average degree $c(k)$ has $h(G) \ge k$, where $c(k) = \beta k \sqrt{\log_2 k}(1+o(1))$ and $\beta \approx 0.265656$.
  • The author applies the Pigeonhole Principle to edge colorings: in an $\ell$-colored $K_n$, the majority color class must have a density sufficient to trigger Thomason's result, thereby guaranteeing a monochromatic $K_k$-minor.
  • Refinement: For the 2-color case, the author refines the constant by analyzing connectivity. If the majority color graph is highly connected, Thomason's result applies directly. If not, the graph contains a large induced subgraph with high minimum degree, allowing the construction of a $K_k$-minor either in the graph or its complement (the other color).

• Lower Bounds (Probabilistic and Packing Methods):

  • Random Graphs: For lower bounds, the author considers random graphs $G(n, 1/2)$. Using results by Bollobás, Catlin, and Erdős, it is shown that for $n \approx k\sqrt{\log k}$, the Hadwiger number of a random graph is likely less than $k$. Thus, a random 2-coloring of $K_n$ avoids monochromatic $K_k$-minors.
  • Graph Decomposition (Wilson's Theorem): For the general $\ell$-color case, the author constructs a specific graph $H$ (derived from a $K_k$-minor-free graph with optimal density) and uses Wilson's Theorem on pairwise edge-disjoint decompositions. By decomposing $K_n$ into copies of $H$ and assigning each copy a unique color, a coloring is constructed where no color class contains a $K_k$-minor.

3. Key Contributions and Results

A. Asymptotic Bounds for $R_h(k; 2)$

The paper establishes tight asymptotic bounds for the 2-color case:
$$k\sqrt{\log k}(1 + o(1)) \le R_h(k; 2) \le 1.031 \cdot k\sqrt{\log k}(1 + o(1))$$

• Lower Bound: Derived from the Hadwiger number of random graphs $G(n, 1/2)$.
• Upper Bound: Improved from a trivial application of Thomason's density theorem ($1.062\dots$) to 1.031 through a refined case analysis involving graph connectivity and minimum degree.
• Conjecture: The author conjectures that the constant factor is exactly 1, i.e., $R_h(k; 2) \sim k\sqrt{\log k}$.

B. Asymptotic Bounds for $R_h(k; \ell)$

For a fixed number of colors $\ell$ and large $k$:
$$R_h(k; \ell) = 2\beta \ell k \sqrt{\log k} (1 + o(1))$$
where $\beta \approx 0.265656$.

• This result shows that the Ramsey number for minors scales linearly with the number of colors $\ell$, unlike the classical Ramsey number which grows exponentially.

C. Exact Values and Small Cases

The paper provides exact values and bounds for small $k$:

• $R_h(3) = 5$: Any 2-coloring of $K_5$ yields a monochromatic cycle ($K_3$-minor). $K_4$ can be colored with two $P_4$s (paths), avoiding cycles.
• $R_h(4) = 7$: The author proves $R_h(4) \le 7$ via a detailed structural analysis of 3-chromatic graphs, improving the trivial bound of 8.
• General Small Bounds: For $k \ge 5$, $2(k-2) \le R_h(k) \le 32(k-2)^{\lfloor \log(k-2) \rfloor + 1}$.

D. Specific Case for $k=3$

For any $\ell \ge 1$:
$$R_h(3; \ell) = 2\ell + 1$$
This is proven by decomposing $K_{2\ell}$ into $\ell$ Hamiltonian paths (which are $K_3$-minor free) and showing that $K_{2\ell+1}$ forces a cycle in one color class.

4. Significance

• Filling a Gap: This work explicitly defines and analyzes the Ramsey number for minors, a natural parameter that complements the extensive research on the Hadwiger Conjecture.
• Asymptotic Precision: The paper provides the first precise asymptotic estimates for $R_h(k; \ell)$, determining the exact dependence on $k$ (specifically the $k\sqrt{\log k}$ term) and $\ell$.
• Methodological Innovation: The combination of Thomason's density results with structural connectivity arguments and Wilson's decomposition theorems offers a robust framework for analyzing Ramsey-type problems on graph minors.
• Open Problems: The paper identifies the exact value of the constant $c$ in $R_h(k; 2) \sim c k\sqrt{\log k}$ as a primary open question, conjecturing $c=1$. It also suggests that a direct proof avoiding density theorems would be valuable.

In summary, Axenovich demonstrates that the Ramsey number for minors behaves fundamentally differently from classical Ramsey numbers (polynomial vs. exponential growth) and provides the leading-order asymptotic behavior for both 2-color and multi-color scenarios.