Improved bounds for the minimum degree of minimal multicolor Ramsey graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909833906618368 |
|---|---|
| author | Attwa, Yamaan Mattheus, Sam Szabó, Tibor Verstraete, Jacques |
| author_facet | Attwa, Yamaan Mattheus, Sam Szabó, Tibor Verstraete, Jacques |
| contents | We provide two novel constructions of $r$ edge-disjoint $K_{k+1}$-free graphs on the same vertex set, each of which has the property that every small induced subgraph contains a complete graph on $k$ vertices. The main novelty of our argument is the combination of an algebraic and a probabilistic coloring scheme, which utilizes the beneficial algebraic and combinatorial properties of the Hermitian unital. These constructions improve on a number of upper bounds on the smallest possible minimum degree of minimal $r$-color Ramsey graphs for the clique $K_{k+1}$ when $r\geq c\frac{k}{\log^2 k}$ and $k$ is large enough. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09068 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved bounds for the minimum degree of minimal multicolor Ramsey graphs Attwa, Yamaan Mattheus, Sam Szabó, Tibor Verstraete, Jacques Combinatorics We provide two novel constructions of $r$ edge-disjoint $K_{k+1}$-free graphs on the same vertex set, each of which has the property that every small induced subgraph contains a complete graph on $k$ vertices. The main novelty of our argument is the combination of an algebraic and a probabilistic coloring scheme, which utilizes the beneficial algebraic and combinatorial properties of the Hermitian unital. These constructions improve on a number of upper bounds on the smallest possible minimum degree of minimal $r$-color Ramsey graphs for the clique $K_{k+1}$ when $r\geq c\frac{k}{\log^2 k}$ and $k$ is large enough. |
| title | Improved bounds for the minimum degree of minimal multicolor Ramsey graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.09068 |