Colored Unavoidable Patterns and Balanceable Graphs

Journal article

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 Ω(n^2−1/trr) edges in each color contains a member from a certain finite family F^rt of r-edge-colored complete graphs. Next, we study a related problem where the corresponding Turán threshold is linear. We call an edge-coloring of a path with rk edges 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 n^2−o(1) edges from each color do not guarantee the existence of a balanced path on 7k edges.

Authors: Bowen, M; Hansberg, A; Montejano, A; Müyesser, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Electronic Journal of Combinatorics
• Journal: The Electronic Journal of Combinatorics
• Volume: 31
• Issue: 2
• Publication date: 2024-05-03
• DOI: 10.37236/10571
• EISSN: 1077-8926
• ISSN: 1077-8926
• Language: English
• Keywords: Computer science; Colored; Law; Political science