Turán Colourings in Off-Diagonal Ramsey Multiplicity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909086911561728 |
|---|---|
| author | Hyde, Joseph Lee, Jae-baek Noel, Jonathan A. |
| author_facet | Hyde, Joseph Lee, Jae-baek Noel, Jonathan A. |
| contents | The \emph{Ramsey multiplicity constant} of a graph $H$ is the limit as $n$ tends to infinity of the minimum density of monochromatic labeled copies of $H$ in a $2$-edge colouring of $K_n$. Fox and Wigderson recently identified a large family of graphs whose Ramsey multiplicity constants are attained by sequences of ``Turán colourings''; i.e. colourings in which one of the colour classes forms the edge set of a balanced complete multipartite graph. Each graph in their family comes from taking a connected non-3-colourable graph with a critical edge and adding many pendant edges. We extend their result to an off-diagonal variant of the Ramsey multiplicity constant which involves minimizing a weighted sum of red copies of one graph and blue copies of another. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_06959 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Turán Colourings in Off-Diagonal Ramsey Multiplicity Hyde, Joseph Lee, Jae-baek Noel, Jonathan A. Combinatorics 05C35, 05D10 The \emph{Ramsey multiplicity constant} of a graph $H$ is the limit as $n$ tends to infinity of the minimum density of monochromatic labeled copies of $H$ in a $2$-edge colouring of $K_n$. Fox and Wigderson recently identified a large family of graphs whose Ramsey multiplicity constants are attained by sequences of ``Turán colourings''; i.e. colourings in which one of the colour classes forms the edge set of a balanced complete multipartite graph. Each graph in their family comes from taking a connected non-3-colourable graph with a critical edge and adding many pendant edges. We extend their result to an off-diagonal variant of the Ramsey multiplicity constant which involves minimizing a weighted sum of red copies of one graph and blue copies of another. |
| title | Turán Colourings in Off-Diagonal Ramsey Multiplicity |
| topic | Combinatorics 05C35, 05D10 |
| url | https://arxiv.org/abs/2309.06959 |