论文标题
某些旋塞型超图的色度的下限
Lower bounds for the chromatic number of certain Kneser-type hypergraphs
论文作者
论文摘要
Let $n\ge 1$, $r\ge 2$, and $s\ge 0$ be integers and ${\cal P}=\{P_1,\dots, P_l\}$ be a partition of $[n]=\{1,\dots, n\}$ with $|P_i|\le r$ for $i=1,\dots, l$.另外，让$ \ cal f $为$ [n] $的非空本集。 $ r $ - 均匀的kneser-type hypergraph $ \ mbox {kg}^r（{\ cal f}，{\ cal p}，s）$是所有$ \ cal p $ -admissible Elements $ f \ in {\ cal f} $ f \ f ins $ | f \ cap p_i | f \ f \ | | | | | | | | | | | | | | | | $ i = 1，\ dots，l $和所有$ r $ -subsets $ \ \ {f_1，\ dots，f_r \} $的边缘集，该顶点集的$ | f_i \ cap f_i \ cap f_i \ cap f_j | \ le s $全部$ 1 \ le i i <j \ j \ le l $ r $。在本文中，我们将Abyazi Sani和Alishahi的公平$ r $ -R $ - 可溶性$ \ mbox {ecd}^r（{\ cal f}）$延长到一个允许边缘角度之间的交叉点时的情况。它将用$ \ mbox {ecd}^r（{\ cal f}，s）$表示。然后，我们将$ \ mbox {kg}^r（{\ cal f}，{\ cal p}，s）$的$ \ mbox {kg}^r（{\ cal p}，s）及其某些变体以$ \ mbox {ecd}^r（{ecd}^r（{\ cal f}，\ cal f}，\ lfloor s/ffloor s/fff）表示）的（{\ cal p}，s）$的色度下限（这项工作概括了Kneser Hypergraphs的文献中的许多现有结果。它将目前作者的先前结果从所有$ k $ - $ [n] $的特殊家族的结果概括为一般家庭$ \ cal f $ subset的$ [n] $。
Let $n\ge 1$, $r\ge 2$, and $s\ge 0$ be integers and ${\cal P}=\{P_1,\dots, P_l\}$ be a partition of $[n]=\{1,\dots, n\}$ with $|P_i|\le r$ for $i=1,\dots, l$. Also, let $\cal F$ be a family of non-empty subsets of $[n]$. The $r$-uniform Kneser-type hypergraph $\mbox{KG}^r({\cal F}, {\cal P},s)$ is the hypergraph with the vertex set of all $\cal P$-admissible elements $F\in {\cal F}$, that is $|F\cap P_i|\le 1$ for $i=1,\dots, l$ and the edge set of all $r$-subsets $\{F_1,\dots, F_r\}$ of the vertex set that $|F_i\cap F_j|\le s$ for all $1\le i<j\le r$. In this article, we extend the equitable $r$-colorability defect $\mbox{ecd}^r({\cal F})$ of Abyazi Sani and Alishahi to the case when one allows intersection among the vertices of an edge. It will be denoted by $\mbox{ecd}^r({\cal F},s)$. We then, give (under certain assumptions) lower bounds for the chromatic number of $\mbox{KG}^r({\cal F}, {\cal P},s)$ and some of its variants in terms of $\mbox{ecd}^r({\cal F},\lfloor s/2\rfloor)$. This work generalizes many existing results in the literature of the Kneser hypergraphs. It generalizes the previous results of the current authors from the special family of all $k$-subsets of $[n]$ to a general family $\cal F$ of subsets.
