Bounds for Rainbow-uncommon Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916149664415744 |
|---|---|
| author | Bates, Blake Berikkyzy, Zhanar Chiem, Nick Elvin, Gabriel Fines, Risa Lie, Maja Mikulás, Hanna Reiter, Isaac Zhou, Kevin |
| author_facet | Bates, Blake Berikkyzy, Zhanar Chiem, Nick Elvin, Gabriel Fines, Risa Lie, Maja Mikulás, Hanna Reiter, Isaac Zhou, Kevin |
| contents | We say a graph $H$ is $r$-rainbow-uncommon if the maximum number of rainbow copies of $H$ under an $r$-coloring of $E(K_n)$ is asymptotically (as $n \to \infty$) greater than what is expected from uniformly random $r$-colorings. Via explicit constructions, we show that for $H\in\{K_3,K_4, K_5\}$, $H$ is $r$-rainbow-uncommon for all $r\geq {|V(H)|\choose 2}$. We also construct colorings to show that for $t \geq 6$, $K_t$ is $r$-rainbow-uncommon for sufficiently large $r$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04055 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bounds for Rainbow-uncommon Graphs Bates, Blake Berikkyzy, Zhanar Chiem, Nick Elvin, Gabriel Fines, Risa Lie, Maja Mikulás, Hanna Reiter, Isaac Zhou, Kevin Combinatorics 05C15 We say a graph $H$ is $r$-rainbow-uncommon if the maximum number of rainbow copies of $H$ under an $r$-coloring of $E(K_n)$ is asymptotically (as $n \to \infty$) greater than what is expected from uniformly random $r$-colorings. Via explicit constructions, we show that for $H\in\{K_3,K_4, K_5\}$, $H$ is $r$-rainbow-uncommon for all $r\geq {|V(H)|\choose 2}$. We also construct colorings to show that for $t \geq 6$, $K_t$ is $r$-rainbow-uncommon for sufficiently large $r$. |
| title | Bounds for Rainbow-uncommon Graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2403.04055 |