论文标题
在彩虹极端问题上
On a rainbow extremal problem for color-critical graphs
论文作者
论文摘要
已经对以下问题进行了广泛的研究：给定$ k $ graphs $ g_1，\ dots，g_k $上的一组常见顶点$ n $，$ g_i $上的哪些条件可确保$ h $的“彩色”副本，即，$ h $ of $ h $的副本最多来自$ g_i $？ $ \ sum_ {i \ in [k]} e（g_i）$在给定图形$ h $的五颜六色副本上的下限被keevash，saks，sudakov和verstraëte考虑了。他们定义了$ \ operatorname {ex} _k（n，h）$，是图形的最大边缘总数$ g_1，\ dots，g_k $，在一组尺寸$ n $上没有$ h $的颜色副本。他们完全确定了$ \ operatorname {ex} _k（n，k_r）$ for $ n $，通过显示的，具体取决于$ k $的值，这两个天然结构之一始终是极端结构。此外，他们对每个批判性图形都有相同的猜测，并证明了这是针对三色图形的。 我们证明了他们对4色批判图的猜想，几乎所有$ r $ colital-colitication Graphs当$ r> 4 $时。此外，我们表明，对于每个非颜色的非两部分图，这两个自然结构都不是$ k $的一定值。这回答了Keevash，Saks，Sudakov和Verstraëte的问题。
There has been extensive studies on the following question: given $k$ graphs $G_1,\dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a `colorful' copy of $H$, i.e., a copy of $H$ containing at most one edge from each $G_i$? A lower bound on $\sum_{i\in [k]} e(G_i)$ enforcing a colorful copy of a given graph $H$ was considered by Keevash, Saks, Sudakov, and Verstraëte. They defined $\operatorname{ex}_k(n,H)$ to be the maximum total number of edges of the graphs $G_1,\dots, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $\operatorname{ex}_k(n,K_r)$ for large $n$ by showing that, depending on the value of $k$, one of the two natural constructions is always the extremal construction. Moreover, they conjectured the same holds for every color-critical graphs and proved it for 3-color-critical graphs. We prove their conjecture for 4-color-critical graphs and for almost all $r$-color-critical graphs when $r > 4$. Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of $k$. This answers a question of Keevash, Saks, Sudakov, and Verstraëte.
