Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2303.09296 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909948382806016 |
|---|---|
| author | Lee, Jae-baek Noel, Jonathan A. |
| author_facet | Lee, Jae-baek Noel, Jonathan A. |
| contents | A graph $H$ is said to be common if the number of monochromatic labelled copies of $H$ in a $2$-colouring of the edges of a large complete graph is asymptotically minimized by a random colouring. It is well known that the disjoint union of two common graphs may be uncommon; e.g., $K_2$ and $K_3$ are common, but their disjoint union is not. We investigate the commonality of disjoint unions of multiple copies of $K_3$ and $K_2$. As a consequence of our results, we obtain an example of a pair of uncommon graphs whose disjoint union is common. Our approach is to reduce the problem of showing that certain disconnected graphs are common to a constrained optimization problem in which the constraints are derived from supersaturation bounds related to Razborov's Triangle Density Theorem. We also improve bounds on the Ramsey multiplicity constant of a triangle with a pendant edge and the disjoint union of $K_3$ and $K_2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_09296 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Disconnected Common Graphs via Supersaturation Lee, Jae-baek Noel, Jonathan A. Combinatorics A graph $H$ is said to be common if the number of monochromatic labelled copies of $H$ in a $2$-colouring of the edges of a large complete graph is asymptotically minimized by a random colouring. It is well known that the disjoint union of two common graphs may be uncommon; e.g., $K_2$ and $K_3$ are common, but their disjoint union is not. We investigate the commonality of disjoint unions of multiple copies of $K_3$ and $K_2$. As a consequence of our results, we obtain an example of a pair of uncommon graphs whose disjoint union is common. Our approach is to reduce the problem of showing that certain disconnected graphs are common to a constrained optimization problem in which the constraints are derived from supersaturation bounds related to Razborov's Triangle Density Theorem. We also improve bounds on the Ramsey multiplicity constant of a triangle with a pendant edge and the disjoint union of $K_3$ and $K_2$. |
| title | Disconnected Common Graphs via Supersaturation |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2303.09296 |