论文标题
独立横向的平均度条件
An average degree condition for independent transversals
论文作者
论文摘要
在1994年，Erdős，Gyárfás和üuczak提出了以下问题：给定的脱节顶点$ v_1，\ dots，\ dots，v_n $ size〜 $ k $，在任何一对$ v_i，v_j $之间，$ v_j $之间的一个优势，$ n $有多大的$ n $，使得有一个独立的横向横向横向跨性别？他们表明，最大$ n $最多是$（1+o（1））k^2 $，通过提供这些参数的明确结构，而没有独立的横向。他们还证明了一个较小的$ 2E $ factor。 在本文中，我们通过证明其上限结构最好解决这个问题：如果$ n \ le（1-o（1））k^2 $，总会有独立的横向。实际上，这个结果是一个非常特殊的情况，它是一个更通用的定理，它涉及“局部稀疏”的任意零件图中的独立横向，这意味着每对零件之间的最大程度相对较小。在这种情况下，Loh和Sudakov为存在独立横向的存在提供了全局\ emph {最大}度条件。我们表明，可以放松到\ emph {平均}度条件。 我们还可以使用新定理为更通用版本的Erdős-gyárfás-见uczak问题建立紧密的界限，并从1997年开始解决了Yuster的猜想。这利用了与Turán数量的完整两部分图形的联系，这可能引起了独立的关注。
In 1994, Erdős, Gyárfás and Łuczak posed the following problem: given disjoint vertex sets $V_1,\dots,V_n$ of size~$k$, with exactly one edge between any pair $V_i,V_j$, how large can $n$ be such that there will always be an independent transversal? They showed that the maximal $n$ is at most $(1+o(1))k^2$, by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a $2e$-factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if $n\le (1-o(1))k^2$, there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are `locally sparse', meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global \emph{maximum} degree condition for the existence of an independent transversal. We show that this can be relaxed to an \emph{average} degree condition. We can also use our new theorem to establish tight bounds for a more general version of the Erdős--Gyárfás--Łuczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turán numbers of complete bipartite graphs, which might be of independent interest.
