Colored unavoidable patterns and balanceable graphs

Publication date 12 December 2019

Abstract: We study a Tur'an-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

O m e g a (n^{2 - 1 / t r^{r}})

edges in each color contains a member from certain finite family

m a t h c a l F_{t}^{r}

of

r

-edge-colored complete graphs. We conjecture that

O m e g a (n^{2 - 1 / t})

edges in each color are sufficient to find a member from

{m a t h c a l F}_{t}^{r}

. A result of Gir~ao and Narayanan confirms this conjecture when

r = 2

. Next, we study a related problem where the corresponding Tur'an threshold is linear. We call an edge-coloring of a path

P_{r k}

balanced if each color appears

k

times in the coloring. We show that any

3

-edge-coloring of a large complete graph with

k n + o (n)

edges in each color contains a balanced

P_{3 k}

. 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 does not guarantee existence of a balanced

P_{7 k}

.

Recommendations

Cited in

(6)

This page was built for publication: Colored unavoidable patterns and balanceable graphs