Ramsey numbers for regular induced subgraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913105896800256 |
|---|---|
| author | Dyson, Paul W. McKay, Brendan D. |
| author_facet | Dyson, Paul W. McKay, Brendan D. |
| contents | A problem proposed by Erdős, Fajtlowicz and Staton asks for the smallest $n$ for which every graph on $n$ vertices contains a regular induced subgraph of order at least $k$. A variation is to ask for a regular induced subgraph of order exactly $k$. In this paper we provide exact values for $k\le 5$ and lower bounds for $k=6$ and $k=7$. We also improve the general lower bound of Alon, Krivelevich and Sudakov [SIAM J. Disc. Math, 2008]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_08215 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Ramsey numbers for regular induced subgraphs Dyson, Paul W. McKay, Brendan D. Combinatorics 05D10, 05C55, 05C35 A problem proposed by Erdős, Fajtlowicz and Staton asks for the smallest $n$ for which every graph on $n$ vertices contains a regular induced subgraph of order at least $k$. A variation is to ask for a regular induced subgraph of order exactly $k$. In this paper we provide exact values for $k\le 5$ and lower bounds for $k=6$ and $k=7$. We also improve the general lower bound of Alon, Krivelevich and Sudakov [SIAM J. Disc. Math, 2008]. |
| title | Ramsey numbers for regular induced subgraphs |
| topic | Combinatorics 05D10, 05C55, 05C35 |
| url | https://arxiv.org/abs/2604.08215 |