Edges not covered by monochromatic bipartite graphs

Xiutao Zhu; Ervin Győri; Zhen He; Zequn Lv; Nika Salia; Casey Tompkins; Kitti Varga

paper

Edges not covered by monochromatic bipartite graphs

arXiv:2210.11037

Abstract

Let $f_{k} (n, H)$ denote the maximum number of edges not contained in any monochromatic copy of~ $H$ in a $k$ -coloring of the edges of $K_{n}$ , and let $e x (n, H)$ denote the Turán number of $H$ . In place of $f_{2} (n, H)$ we simply write $f (n, H)$ . Keevash and Sudakov proved that $f (n, H) = e x (n, H)$ if $H$ is an edge-critical graph or $C_{4}$ and asked if this equality holds for any graph $H$ . All known exact values of this question require $H$ to contain at least one cycle. In this paper we focus on acyclic graphs and have the following results: (1) We prove $f (n, H) = e x (n, H)$ when $H$ is a spider or a double broom. (2) A \emph{tail} in $H$ is a path $P_{3} = v_{0} v_{1} v_{2}$ such that $v_{2}$ is only adjacent to $v_{1}$ and $v_{1}$ is only adjacent to $v_{0}, v_{2}$ in $H$ . We obtain a tight upper bound for $f (n, H)$ when $H$ is a bipartite graph with a tail. This result provides the first bipartite graphs which answer the question of Keevash and Sudakov in the negative. (3) Liu, Pikhurko and Sharifzadeh asked if $f_{k} (n, T) = (k - 1) e x (n, T)$ when $T$ is a tree. We provide an upper bound for $f_{2 k} (n, P_{2 k})$ and show it is tight when $2 k - 1$ is prime. This provides a negative answer to their question.