Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2311.18301 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910520838193152 |
|---|---|
| author | Sun, Yihang |
| author_facet | Sun, Yihang |
| contents | We study the rainbow version of the graph commonness property: a graph $H$ is $r$-rainbow common if the number of rainbow copies of $H$ (where all edges have distinct colors) in an $r$-coloring of edges of $K_n$ is maximized asymptotically by independently coloring each edge uniformly at random. $H$ is \emph{$r$-rainbow uncommon} otherwise. We show that if $H$ has a cycle, then it is $r$-rainbow uncommon for every $r$ at least the number of edges of $H$. This generalizes a result of Erdős and Hajnal, and proves a conjecture of De Silva, Si, Tait, Tunçbilek, Yang, and Young. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_18301 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Rainbow common graphs must be forests Sun, Yihang Combinatorics We study the rainbow version of the graph commonness property: a graph $H$ is $r$-rainbow common if the number of rainbow copies of $H$ (where all edges have distinct colors) in an $r$-coloring of edges of $K_n$ is maximized asymptotically by independently coloring each edge uniformly at random. $H$ is \emph{$r$-rainbow uncommon} otherwise. We show that if $H$ has a cycle, then it is $r$-rainbow uncommon for every $r$ at least the number of edges of $H$. This generalizes a result of Erdős and Hajnal, and proves a conjecture of De Silva, Si, Tait, Tunçbilek, Yang, and Young. |
| title | Rainbow common graphs must be forests |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2311.18301 |