A note on Ramsey numbers for minors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917357654376448 |
|---|---|
| author | Axenovich, Maria Steiner, Raphael |
| author_facet | Axenovich, Maria Steiner, Raphael |
| contents | Let $R_h(k; \ell)$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $\ell$ colors results in a monochromatic $K_k$-minor, in other words, a graph with Hadwiger number $k$, i.e., a graph that could be transformed into a clique $K_k$ on $k$ vertices via a sequence of edge contractions and vertex deletions. More generally, for a graph $F$ and integer $\ell$ let $R_h(F;\ell)$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $\ell$ colors results in a monochromatic $F$-minor.
In 2001 Thomason and in 2005 Myers and Thomason asymptotically determined the extremal numbers for clique minors and $F$-minors, respectively. They found the respective explicitly computable leading constants $β=0.265656...$ and $γ(F)\cdot β$ for these extremal numbers.
We determine $R_h(F;2)$ for every graph $F$ as
$$R_h(F;2)=(γ(F)+o(1))|V(F)|\sqrt{\log_2(|V(F)|)},$$
where the $o(1)$-term tends to zero as $|V(F)|\rightarrow \infty$. In particular,
$$R_h(k;2)=(1+o(1))k\sqrt{\log_2 k}.$$
When $\ell\gg k \gg 1$, we show that
$$ R_h(k; \ell) = (2β+o(1)) \ell k \sqrt{\log_2 k}.$$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_10510 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A note on Ramsey numbers for minors Axenovich, Maria Steiner, Raphael Combinatorics 05D10, 05C15, 05C55, 05C83 Let $R_h(k; \ell)$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $\ell$ colors results in a monochromatic $K_k$-minor, in other words, a graph with Hadwiger number $k$, i.e., a graph that could be transformed into a clique $K_k$ on $k$ vertices via a sequence of edge contractions and vertex deletions. More generally, for a graph $F$ and integer $\ell$ let $R_h(F;\ell)$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $\ell$ colors results in a monochromatic $F$-minor. In 2001 Thomason and in 2005 Myers and Thomason asymptotically determined the extremal numbers for clique minors and $F$-minors, respectively. They found the respective explicitly computable leading constants $β=0.265656...$ and $γ(F)\cdot β$ for these extremal numbers. We determine $R_h(F;2)$ for every graph $F$ as $$R_h(F;2)=(γ(F)+o(1))|V(F)|\sqrt{\log_2(|V(F)|)},$$ where the $o(1)$-term tends to zero as $|V(F)|\rightarrow \infty$. In particular, $$R_h(k;2)=(1+o(1))k\sqrt{\log_2 k}.$$ When $\ell\gg k \gg 1$, we show that $$ R_h(k; \ell) = (2β+o(1)) \ell k \sqrt{\log_2 k}.$$ |
| title | A note on Ramsey numbers for minors |
| topic | Combinatorics 05D10, 05C15, 05C55, 05C83 |
| url | https://arxiv.org/abs/2603.10510 |