论文标题
不可避免的双色调模式的演变和均衡性的极端案例的演变
The evolution of unavoidable bi-chromatic patterns and extremal cases of balanceability
论文作者
论文摘要
我们研究了$ n $足够大的颜色模式，在$ 2 $ 2 $ - 颜色的边缘$ \ min \ {e（r），e（b）\} $，$ e（r）$（r）$和$ e（b）$是红色和蓝色的数字。更准确地说，我们确定这种不可避免的模式如何从颜色中不受限制地演变，即$ \ min \ {e（r），e（b）\} \ ge 0 $（由Ramsey's theorem给出）（由Ramsey's Theorem给出），即可能的最高限制，即$ | E（e（R） - E（R） - E（R） - E（R） - E（r）| \ le 1 $。我们还研究了每种颜色中某些子结构的效果。特别是，我们表明，在$ 2 $颜色中，每种颜色引起的图形都没有$ r $边缘的诱导匹配，但不可避免的图案的外观已经被授予了对$ \ min \ {e（e（r），e（b）\} $的限制较弱的限制。我们完成了图$ g $的平衡数字$ bal（n，g）的后果（即，至少$ k $的最低$ k $，使每$ 2 $ -EDGE $ k_n $ a $ k_n $带有$ \ min \ min \ min \ {e（r），e（b），e（b）\}> k $，每个$ g $ a $ g $ in $ g $ in $ n $ y y $ y y var in yr $ gens，in var in yr $ y y yr y;是$ bal（n，g）\ ge c n^{2- \ varepsilon} $的图形$ g $，这是可以实现的最高数量级，以及$ bal（n，g）\ le c（g）$，$ c（g）$的图形，其中$ c（g）$仅取决于$ g $ $ g $。我们描述了后者。
We study the color patterns that, for $n$ sufficiently large, are unavoidable in $2$-colorings of the edges of a complete graph $K_n$ with respect to $\min \{e(R), e(B)\}$, where $e(R)$ and $e(B)$ are the numbers of red and, respectively, blue edges. More precisely, we determine how such unavoidable patterns evolve from the case without restriction in the coloring, namely that $\min \{e(R), e(B)\} \ge 0$ (given by Ramsey's theorem), to the highest possible restriction, namely that $|e(R) - e(B)| \le 1$. We also investigate the effect of forbidding certain sub-structures in each color. In particular, we show that, in $2$-colorings whose graphs induced by each of the colors are both free from an induced matching on $r$ edges, the appearance of the unavoidable patterns is already granted with a much weaker restriction on $\min \{e(R), e(B)\}$. We finish analyzing the consequences of these results to the balancing number $bal(n,G)$ of a graph $G$ (i.e. the minimum $k$ such that every $2$-edge coloring of $K_n$ with $\min \{e(R), e(B)\} > k$ contains a copy of $G$ with half the edges in each color), and show that, for every $\varepsilon > 0$, there are graphs $G$ with $bal(n,G) \ge c n^{2-\varepsilon}$, which is the highest order of magnitude that is possible to achieve, as well as graphs where $bal(n,G) \le c(G)$, where $c(G)$ is a constant that depends only $G$. We characterize the latter ones.
