Degree versions of the Erdos-Ko-Rado theorem and Erdos hypergraph matching conjecture

作者：Huang Hao^*; Zhao Yi

来源：Journal of Combinatorial Theory - Series A, 2017, 150: 233-247.

DOI：10.1016/j.jcta.2017.03.006

• Degree version
• Hypergraph matching
• Algebraic method

We use an algebraic method to prove a degree version of the celebrated Erdos-Ko-Rado theorem: given n > 2k, every intersecting k-uniform hypergraph H on n vertices contains a vertex that lies on at most ((k-2) (n-2)) edges. This result implies the Erdos-Ko-Rado Theorem as a corollary. It can also be viewed as a special case of the degree version of a well-known conjecture of Erdds on hypergraph matchings. Improving the work of Bollobas, Daykin, and Erdds from 1976, we show that, given integers n, k, s with n >= 3k(2)s, every k-uniform hypergraph H on n vertices with minimum vertex degree greater than ((k-1) (n-1))- ((k-1) (n-s)) contains s disjoint edges.

• 出版日期2017-8