Jiang, T;
Letzter, S;
Methuku, A;
Yepremyan, L;
(2024)
Rainbow subdivisions of cliques.
Random Structures and Algorithms
, 64
(3)
pp. 625-644.
10.1002/rsa.21186.
Preview |
Text
rainbow-subdivision.pdf - Accepted Version Download (394kB) | Preview |
Abstract
We show that for every integer m ≥ 2 and large n, every properly edge-coloured graph on n vertices with at least n(log n)^{53} edges contains a rainbow subdivision of K_{m}. This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.
| Type: | Article |
|---|---|
| Title: | Rainbow subdivisions of cliques |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1002/rsa.21186 |
| Publisher version: | https://doi.org/10.1002/rsa.21186 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | cycles, expanders, expansion, homomorphism, mixing time, rainbow Turan number, random walk, subdivision of cliques |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10181461 |
Archive Staff Only
 |
View Item |
