论文标题
边缘不被单色二分图覆盖
Edges not covered by monochromatic bipartite graphs
论文作者
论文摘要
令$ f_k（n，h）$表示任何单色副本中未包含的最大边数〜$ h $ in $ k $ - $ k_n $的边缘颜色，然后让$ ex（n，h）$表示turán的$ h $。代替$ f_2（n，h）$，我们只是写$ f（n，h）$。 Keevash和Sudakov证明了$ f（n，h）= ex（n，h）$，如果$ h $是边缘临界图或$ C_4 $，并询问此相等性是否适用于任何图$ h $。该问题的所有已知确切值都需要$ h $才能包含至少一个周期。在本文中，我们专注于无环图，并具有以下结果： （1）当$ h $是蜘蛛或双扫帚时，我们证明$ f（n，h）= ex（n，h）$。 （2）$ h $中的a \ emph {tail}是一条路径$ p_3 = v_0v_1v_2 $，这样$ v_2 $仅与$ v_1 $相邻，而$ v_1 $仅与$ v_0相邻，$ v_2 $ h $中的v_2 $。当$ h $是带有尾巴的两部分图时，我们会获得$ f（n，h）$的紧密上限。该结果提供了第一个两部分图，这些图在负面回答了Keevash和Sudakov的问题。 （3）Liu，Pikhurko和Sharifzadeh询问$ f_k（n，t）=（k-1）ex（n，t）$时，$ t $是一棵树。我们为$ f_ {2k}（n，p_ {2k}）$提供了一个上限，并在$ 2K-1 $是PRIME时表明它很紧。这为他们的问题提供了负面答案。
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 $ex(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)=ex(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)=ex(n,H)$ when $H$ is a spider or a double broom. (2) A \emph{tail} in $H$ is a path $P_3=v_0v_1v_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)ex(n,T)$ when $T$ is a tree. We provide an upper bound for $f_{2k}(n,P_{2k})$ and show it is tight when $2k-1$ is prime. This provides a negative answer to their question.
