论文标题
3个相交超图的交点光谱
The intersection spectrum of 3-chromatic intersecting hypergraphs
论文作者
论文摘要
对于HyperGraph $ h $，将其交叉点频谱$ i（h）$定义为所有交叉尺寸的集合$ | e \ e \ cap f | $ of Dinters Edges $ e，f \ in E（H）$。在1973年的开创性论文中，介绍了当地的引理，Erdős和Lovász问：$ K $ - 均匀$ 3 $ 3 $ chrostic thromotic交点超级盖的交叉频谱必须多大？他们表明，这样的超图必须至少具有三个相交大小，并猜想交点频谱的大小倾向于以$ k $为单位。尽管ERDS和其他研究人员多年来重申了几次问题，但到目前为止，三个十字路口大小的下限已经显着地承受了任何改进。在本文中，我们通过表明至少有$ k^{1/2-o（1）} $相交大小来证明Erdős-Lovász的猜想。我们的证明是由拉姆西型参数和密度增量方法之间的微妙相互作用组成。
For a hypergraph $H$, define its intersection spectrum $I(H)$ as the set of all intersection sizes $|E\cap F|$ of distinct edges $E,F\in E(H)$. In their seminal paper from 1973 which introduced the local lemma, Erdős and Lovász asked: how large must the intersection spectrum of a $k$-uniform $3$-chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with $k$. Despite the problem being reiterated several times over the years by Erdős and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the Erdős-Lovász conjecture in a strong form by showing that there are at least $k^{1/2-o(1)}$ intersection sizes. Our proof consists of a delicate interplay between Ramsey type arguments and a density increment approach.
