Nearly tight bound for rainbow clique subdivisions in properly edge-colored graphs and applications
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917259797069824 |
|---|---|
| author | Kuang, Peiru Wang, Yan |
| author_facet | Kuang, Peiru Wang, Yan |
| contents | An edge-colored graph is said to be rainbow if all its edges have distinct colors. In this paper, we study the rainbow analogue of a fundamental result of Mader [\emph{Math. Ann.} \textbf{174} (1967), 265--268] on the existence of subdivisions in graphs with large average degree. This is part of the study of rainbow analogues of classical Turán problems, a framework systematically introduced by Keevash, Mubayi, Sudakov and Verstraëte [\emph{Combin. Probab. Comput.} \textbf{16} (2007), 109--126]. We prove that every properly edge-colored graph on $n$ vertices with average degree at least $t^2(\log n)^{1+o(1)}$ contains a rainbow subdivision of $K_t$. When $t$ is a constant, this bound is tight up to the $o(1)$ term. So it essentially resolves a question raised by Jiang, Methuku and Yepremyan [\emph{European J. Combin.} \textbf{110} (2023), 103675] on rainbow clique subdivisions, and also implies a result of Alon, Bucić, Sauermann, Zakharov and Zamir [\emph{Proc. Lond. Math. Soc.} \textbf{130} (2025), e70044] on rainbow cycles. In addition, we present several applications of our result to problems in additive combinatorics, number theory and coding theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08390 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nearly tight bound for rainbow clique subdivisions in properly edge-colored graphs and applications Kuang, Peiru Wang, Yan Combinatorics An edge-colored graph is said to be rainbow if all its edges have distinct colors. In this paper, we study the rainbow analogue of a fundamental result of Mader [\emph{Math. Ann.} \textbf{174} (1967), 265--268] on the existence of subdivisions in graphs with large average degree. This is part of the study of rainbow analogues of classical Turán problems, a framework systematically introduced by Keevash, Mubayi, Sudakov and Verstraëte [\emph{Combin. Probab. Comput.} \textbf{16} (2007), 109--126]. We prove that every properly edge-colored graph on $n$ vertices with average degree at least $t^2(\log n)^{1+o(1)}$ contains a rainbow subdivision of $K_t$. When $t$ is a constant, this bound is tight up to the $o(1)$ term. So it essentially resolves a question raised by Jiang, Methuku and Yepremyan [\emph{European J. Combin.} \textbf{110} (2023), 103675] on rainbow clique subdivisions, and also implies a result of Alon, Bucić, Sauermann, Zakharov and Zamir [\emph{Proc. Lond. Math. Soc.} \textbf{130} (2025), e70044] on rainbow cycles. In addition, we present several applications of our result to problems in additive combinatorics, number theory and coding theory. |
| title | Nearly tight bound for rainbow clique subdivisions in properly edge-colored graphs and applications |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.08390 |