Rainbow subdivisions of cliques

DOI10.1002/RSA.21186MaRDI QIDQ6201035zbMATH OpenFDO

Authors Tao Jiang, Shoham Letzter, Abhishek Methuku, L. Yepremyan

Publication date 25 March 2024

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.08814

zbMATH Keywords

random walkexpansioncycleshomomorphismmixing timeexpandersrainbow Turan numbersubdivision of cliques

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Paths and cycles (05C38) Random walks on graphs (05C81)

Abstract: We show that for every integer $mge2$ and large $n$, every properly edge-coloured graph on $n$ vertices with at least $n(logn{)}^{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.

Recommendations

• Rainbow clique subdivisions
• Rainbow Turán number of clique subdivisions
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Rainbow triangles and cliques in edge-colored graphs

Cites work

• Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homöomorph sind
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Hypergraphs with no tight cycles
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Rainbow Turán Problems
• Rainbow Turán number of clique subdivisions
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Rainbow Turán problem for even cycles
• The Extremal Number of Tight Cycles
• The probabilistic method
• Topological Cliques in Graphs
• Topological cliques in graphs II
• \(C_4\)-free subgraphs with large average degree

Cited in

(2)

• Rainbow clique subdivisions
• Cycles with many chords

This page was built for publication: Rainbow subdivisions of cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201035)