Sharp thresholds for Ramsey properties
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914365840556032 |
|---|---|
| author | Friedgut, Ehud Kuperwasser, Eden Samotij, Wojciech Schacht, Mathias |
| author_facet | Friedgut, Ehud Kuperwasser, Eden Samotij, Wojciech Schacht, Mathias |
| contents | In this work, we develop a unified framework for establishing sharp threshold results for various Ramsey properties. To achieve this, we view such properties as non-colourability of auxiliary hypergraphs. Our main technical result gives sufficient conditions on a sequence of such hypergraphs that guarantee that this non-colourability property has a sharp threshold in subhypergraphs induced by random subsets of the vertices.
Furthermore, we verify these conditions in several cases of interest. In the classical setting of Ramsey theory for graphs, we show that the property of being Ramsey for a graph $H$ in $r$ colours has a sharp threshold in $G_{n,p}$, for all $r \ge 2$ and all $H$ in a class of graphs that includes all cliques and cycles. In the arithmetic setting, we establish sharpness of thresholds for the properties corresponding to van der Waerden's theorem and Schur's theorem, also in any number of colours. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_13982 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Sharp thresholds for Ramsey properties Friedgut, Ehud Kuperwasser, Eden Samotij, Wojciech Schacht, Mathias Combinatorics In this work, we develop a unified framework for establishing sharp threshold results for various Ramsey properties. To achieve this, we view such properties as non-colourability of auxiliary hypergraphs. Our main technical result gives sufficient conditions on a sequence of such hypergraphs that guarantee that this non-colourability property has a sharp threshold in subhypergraphs induced by random subsets of the vertices. Furthermore, we verify these conditions in several cases of interest. In the classical setting of Ramsey theory for graphs, we show that the property of being Ramsey for a graph $H$ in $r$ colours has a sharp threshold in $G_{n,p}$, for all $r \ge 2$ and all $H$ in a class of graphs that includes all cliques and cycles. In the arithmetic setting, we establish sharpness of thresholds for the properties corresponding to van der Waerden's theorem and Schur's theorem, also in any number of colours. |
| title | Sharp thresholds for Ramsey properties |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2207.13982 |