2019/12/13 by Matt Bowen, Adriana Hansberg, Bowen, Matt +5
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1912.06302
openalex publication_date 2019/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a Turán-type problem on edge-colored complete graphs. We show that for any r and t, any sufficiently large r-edge-colored complete graph on n vertices with Ω(n2-1/trr) edges in each color contains a member from certain finite family Ftr of r-edge-colored complete graphs. We conjecture that Ω(n2-1/t) edges in each color are sufficient to find a member from Ftr. A result of Girão and Narayanan confirms this conjecture when r=2. Next, we study a related problem where the corresponding Turán threshold is linear. We call an edge-coloring of a path Prk balanced if each color appears k times in the coloring. We show that any 3-edge-coloring of a large complete graph with kn+o(n) edges in each color contains a balanced P3k. This is tight up to a constant factor of 2. For more colors, the problem becomes surprisingly more delicate. Already for r=7, we show that even n2-o(1) edges from each color does not guarantee existence of a balanced P7k.