论文标题
在某些拓扑和组合下限上，旋转型型高图
On some topological and combinatorial lower bounds on chromatic number of Kneser type hyper graphs
论文作者
论文摘要
在本文中，我们证明了Erdös的猜想的概括，内容涉及某些旋转型超图的色数。对于整数$ n，k，r，s $，带有$ n \ ge rk $和$ 2 \ le s \ le r $，$ r $ r $ - 统一的一般kneser kneser kneser hypraph $ \ mbox {kg}^r_s^r_s（n，k）$，所有$ k $ aus $ k $ of $ k $ of $ k $ of $ \ \ \ \ \ {1 ,， $ \ {a_1，\ dots，a_r \} $ $ k $ -subsets，$ s $ - $ s $ wise的空交叉点作为边缘集。 Case $ r = S = 2 $，是Kneser \ Cite {K}在1955年考虑的，他猜想其色数为$ N-2（K-1）$。 lovász\ cite {l}在1978年最终证明了这一点。该猜想是由Alon，Frankl和Lovász\ Cite {Afl}在1986年证明的。Sarkaria \ cite {s}在1990年考虑了$ s> 2 $的情况，他声称在那里证明其较低的限制是其彩色数量的较低限制，以便其彩色数字，从而将所有先前的结果概述。不幸的是，Lange和Ziegler \ Cite \ Cite {Z'}在Sarkaria的感应方法中发现了一个错误，$ r $的主要因素数量，而Sarkaria的证明只有在$ S $小于$ r $或$ r $或$ S = 2 $的最小质量因素时才起作用。在本文中，通过应用Ziegler \ cite {Z}和Meunier \ Cite {M}的$ \ Mathbb Z_P $ -Tucker Lemma，我们终于证明了Erdös的猜想，并证明了Sarkaria的索取结果，以获得Sarkaria的任何$ 2 \ le s \ le s \ le s \ le r $。我们还使用类似于Alon，Frankl和Lovász\ Cite {AFL}的方法提供了另一个结果的另一个证明，并计算某些可能自身感兴趣的简单复合物的连通性。
In this paper, we prove a generalization of a conjecture of Erdös, about the chromatic number of certain Kneser-type hypergraphs. For integers $n,k,r,s$ with $n\ge rk$ and $2\le s\le r$, the $r$-uniform general Kneser hypergraph $\mbox{KG}^r_s(n,k)$, has all $k$-subsets of $\{1,\dots,n\}$ as the vertex set and all multi-sets $\{A_1,\dots, A_r\}$ of $k$-subsets with $s$-wise empty intersections as the edge set. The case $r=s=2$, was considers by Kneser \cite{K} in 1955, where he conjectured that its chromatic number is $n-2(k-1)$. This was finally proved by Lovász \cite{L} in 1978. The case $r>2$ and $s=2$, was considered by Erdös in 1973, and he conjectured that its chromatic number is $\left\lceil\frac{n-r(k-1)}{r-1}\right\rceil$. This conjecture was proved by Alon, Frankl and Lovász \cite{AFL} in 1986. The case where $s>2$, was considered by Sarkaria \cite{S} in 1990, where he claimed to prove a lower bound for its chromatic number which generalized all previous results. Unfortunately, an error was found by Lange and Ziegler \cite{Z'} in 2006 in the induction method of Sarkaria on the number of prime factors of $r$, and Sarkaria's proof only worked when $s$ is less than the smallest prime factor of $r$ or $s=2$. In this paper, by applying the $\mathbb Z_p$-Tucker lemma of Ziegler \cite{Z} and Meunier \cite{M}, we finally prove the general Erdös conjecture and prove the claimed result of Sarkaria for any $2\le s\le r$. We also provide another proof of a special case of this result, using methods similar to those of Alon, Frankl, and Lovász \cite{AFL} and compute the connectivity of certain simplicial complexes that might be of interest in their own right.
