论文标题
着色，横向和当地的稀疏性
Colourings, transversals and local sparsity
论文作者
论文摘要
通过最近引入列表着色的形式和对遇到本地稀疏条件的独立横向的早期工作的动机，我们使用半随机方法来证明以下结果。 对于任何功能$μ$满足$μ（d）= o（d）$ as $ d \ to \ infty $，有一个功能$λ$满足$λ（d）= d+o（d）$ as $ d \ to \ to \ infty $，因此以下是以下内容。对于任何图$ h $，其顶点的任何分区至少为$λ$，以至于（a）对于每个部分，其平均水平超出其学位到其他零件的平均水平最多是$ d $，并且（b）（b）从顶点到其他零件的最高学位最多是$ $ $，保证是构成$ h $ h $ h $ h $ h $ h $ h $ h $ h $ h的部分。 这是Loh和Sudakov（2007）以及Molloy和Thron（2012）的两个结果的普遍加强，这反过来又意味着Reed和Sudakov（2002）的早期结果。
Motivated both by recently introduced forms of list colouring and by earlier work on independent transversals subject to a local sparsity condition, we use the semi-random method to prove the following result. For any function $μ$ satisfying $μ(d)=o(d)$ as $d\to\infty$, there is a function $λ$ satisfying $λ(d)=d+o(d)$ as $d\to\infty$ such that the following holds. For any graph $H$ and any partition of its vertices into parts of size at least $λ$ such that (a) for each part the average over its vertices of degree to other parts is at most $d$, and (b) the maximum degree from a vertex to some other part is at most $μ$, there is guaranteed to be a transversal of the parts that forms an independent set of $H$. This is a common strengthening of two results of Loh and Sudakov (2007) and Molloy and Thron (2012), each of which in turn implies an earlier result of Reed and Sudakov (2002).
