Rainbow subdivisions of cliques

DOI10.1002/RSA.21186arXiv2108.08814MaRDI QIDQ6201035FDOQ6201035

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

Publication date: 25 March 2024

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

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.

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

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

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)

Cites Work

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

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)