论文标题
无三角形超图的色数
The chromatic number of triangle-free hypergraphs
论文作者
论文摘要
超图$ \ Mathcal {h} $中的三角形是三个不同的边缘$ e，f，g \ in \ Mathcal {h} $和三个不同的顶点$ u，v，w \ in V（\ Mathcal {h}）$ w \} \ subseteq f $，$ \ {w，u \} \ subseteq g $和$ \ {u，v，w \} \ cap e \ cap e \ cap f \ cap f \ cap g = \ emptyset $。约翰逊（Johansson）在1996年证明了$χ（g）= \ Mathcal {o}（δ/\logδ）$，对于任何最大程度$δ$的任何三角形图$ g $。库珀和穆贝伊随后将约翰逊定理概括为所有排名$ 3 $ HyperGraphs。在本文中，我们为所有超图提供了这两种结果的共同概括，表明，如果$ \ Mathcal {h} $是等级$ k $，无三角形的无三角形超图，则列表彩色号码\ [χ_ {\ ell}（\ ell}（\ Mathcal {h}） \ \ leq k} \ left \ {\ left（\ frac {\ frac {Δ_{\ ell}}} {\logΔ_{\ ell}}} \ right）^{\ frac {1} {1} $ \ Mathcal {H} $的$ \ ell $ -Degree。结果与常数分开。此外，我们的结果意味着，概括并改善了色数和独立性超图数的几个早期结果，而其证明是基于与超图中的先前作品不同的方法（因此为其提供了替代证明）。特别是，作为一种应用，我们建立了一个稀疏数量的稀疏超图，其中每个顶点都包含在几个三角形中，因此将Alon，Krivelevich和Sudakov的结果分别扩展到了等级2和3的库珀和Mubayi。
A triangle in a hypergraph $\mathcal{H}$ is a set of three distinct edges $e, f, g\in\mathcal{H}$ and three distinct vertices $u, v, w\in V(\mathcal{H})$ such that $\{u, v\}\subseteq e$, $\{v, w\}\subseteq f$, $\{w, u\}\subseteq g$ and $\{u, v, w\}\cap e\cap f\cap g=\emptyset$. Johansson proved in 1996 that $χ(G)=\mathcal{O}(Δ/\logΔ)$ for any triangle-free graph $G$ with maximum degree $Δ$. Cooper and Mubayi later generalized the Johansson's theorem to all rank $3$ hypergraphs. In this paper we provide a common generalization of both these results for all hypergraphs, showing that if $\mathcal{H}$ is a rank $k$, triangle-free hypergraph, then the list chromatic number \[ χ_{\ell}(\mathcal{H})\leq \mathcal{O}\left(\max_{2\leq \ell \leq k} \left\{\left( \frac{Δ_{\ell}}{\log Δ_{\ell}} \right)^{\frac{1}{\ell-1}} \right\}\right), \] where $Δ_{\ell}$ is the maximum $\ell$-degree of $\mathcal{H}$. The result is sharp apart from the constant. Moreover, our result implies, generalizes and improves several earlier results on the chromatic number and also independence number of hypergraphs, while its proof is based on a different approach than prior works in hypergraphs (and therefore provides alternative proofs to them). In particular, as an application, we establish a bound on chromatic number of sparse hypergraphs in which each vertex is contained in few triangles, and thus extend results of Alon, Krivelevich and Sudakov, and Cooper and Mubayi from hypergraphs of rank 2 and 3, respectively, to all hypergraphs.
