Density of rainbow triangles and properly colored $K_4$'s
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915802374995968 |
|---|---|
| author | Balogh, József Bradshaw, Peter Garcia, Ramon I. Lidický, Bernard |
| author_facet | Balogh, József Bradshaw, Peter Garcia, Ramon I. Lidický, Bernard |
| contents | We establish a sharp upper bound on the number of properly $3$-edge-colored $K_4$'s in graphs with $R$ red, $G$ green and $B$ blue edges. We give a computer-free flag-algebra proof of this bound, and we also convert our proof into a classical counting proof and an entropy proof.
Additionally, for every $k\ge 4$, for a fixed rainbow coloring $F$ of a complete graph $K_k$, we give a sharp upper bound on the number copies of $F$ in a $\binom{k}{2}$-edge-colored graph. Our proof of this result relies on a new flag-algebra version of Hölder's inequality.
We also give a computer-free flag-algebra proof of the fact that a graph with $R$ red, $G$ green, and $B$ blue edges has at most $\sqrt{2 RGB}$ rainbow triangles, which was originally proven by T.-W. Chao and H.-H. H. Yu using the entropy method. We also provide an even shorter entropy proof of their result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21061 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Density of rainbow triangles and properly colored $K_4$'s Balogh, József Bradshaw, Peter Garcia, Ramon I. Lidický, Bernard Combinatorics 05C35 We establish a sharp upper bound on the number of properly $3$-edge-colored $K_4$'s in graphs with $R$ red, $G$ green and $B$ blue edges. We give a computer-free flag-algebra proof of this bound, and we also convert our proof into a classical counting proof and an entropy proof. Additionally, for every $k\ge 4$, for a fixed rainbow coloring $F$ of a complete graph $K_k$, we give a sharp upper bound on the number copies of $F$ in a $\binom{k}{2}$-edge-colored graph. Our proof of this result relies on a new flag-algebra version of Hölder's inequality. We also give a computer-free flag-algebra proof of the fact that a graph with $R$ red, $G$ green, and $B$ blue edges has at most $\sqrt{2 RGB}$ rainbow triangles, which was originally proven by T.-W. Chao and H.-H. H. Yu using the entropy method. We also provide an even shorter entropy proof of their result. |
| title | Density of rainbow triangles and properly colored $K_4$'s |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2511.21061 |