Metraipolis › archive › dc_0e89fb23ca7a
Counting edge-colorings of a complete graph avoiding a rainbow $K_4$ — arXiv:2609.23179
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.23179
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T21:44:45.955Z
- SHA-256 of the archived text
c3ce2355df6d344200e0050e0f7df4e64e25d0b096f609c708e4397408b9d233- Stable URL of this page
https://metraipolis.com/documento/dc_0e89fb23ca7a
How to cite
Counting edge-colorings of a complete graph avoiding a rainbow $K_4$ — arXiv:2609.23179 — arXiv (en), https://arxiv.org/abs/2609.23179 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0e89fb23ca7a (Metraipolis archive dc_0e89fb23ca7a, sha256 c3ce2355df6d344200e0050e0f7df4e64e25d0b096f609c708e4397408b9d233)
BibTeX
@misc{dc0e89fb23ca7a,
title = {Counting edge-colorings of a complete graph avoiding a rainbow $K_4$ — arXiv:2609.23179},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.23179},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0e89fb23ca7a; sha256 c3ce2355df6d344200e0050e0f7df4e64e25d0b096f609c708e4397408b9d233},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23179. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For $k, r, n$ natural numbers let $\rho_{r,k}(K_n)$ be the number of $r$-edge-colorings of $K_n$ that do not contain a rainbow copy of a $K_k$, that is, a copy of $K_k$ in which all edges receive different colors. When $k=3$, the quantity $\rho_{r,3}(K_n)$ represents the number of Gallai Colorings. It was proved by Balogh and Li and independently by Bastos, Benevides and Han, that most of the Gallai colorings are 2-colorings, for $n$ large. A natural analogue conjecture would be that when $k=4$, $r\ge 5$ and $n$ large, most rainbow-$K_4$-free $r$-edge-colorings are $5$-colorings. We show that this is not true in general and identify an exact threshold for $r$ where this ceases to be true. For the range where the conjecture is false, we determine the exponential growth of $\rho_{r,4}(K_n)$ for every fixed $r$. More precisely, for \(6\le r\le24\), we prove that \(\rho_{r,4}(K_n)=(\binom{r}{5}+o(1))5^{\binom{n}{2}}\); and for each \(r\ge25\), the proportion using at most five colors tends to zero, and \(\rho_{r,4}(K_n)=r^{(n^2/4)+o(n^2)}\). A bipartite construction, with all edges within the two parts assigned one common color, achieves the latter exponential growth rate. The lower bounds can be easily generalized for every $k$. Those results are related to other recent results about counting colorings that avoid rainbow cliques or given rainbow patterns in general. Our proof combines hypergraph containers with the graph removal lemma, structural estimates for color palettes and a refined count of colorings close to a fixed five-color palette.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.23179 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:26:41.110Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).