论文标题
着色线性超图：Erdős-Faber-Lovász猜想和组合无效
Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the Combinatorial Nullstellensatz
论文作者
论文摘要
长期以来，Erdős-Faber-Lovász的猜想指出，每$ n $均匀的线性hypergaph带有$ n $ edges的线性超盖具有适当的顶点颜色，使用$ n $颜色。在本文中，我们提出了一个代数框架，并制定了相应的更强的猜想。使用组合无效的nullstellensatz，我们将Erdős-faber-Lovász猜想减少到某些多项式中的非零系数。这些系数反过来又与某些辅助图的定位序列的方向数量有关。我们证明了某些方向的存在，这验证了我们代数工作方法的必要条件。
The long-standing Erdős-Faber-Lovász conjecture states that every $n$-uniform linear hypergaph with $n$ edges has a proper vertex-coloring using $n$ colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erdős-Faber-Lovász conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work.
