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

摘要

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. (C) 2017 Elsevier Inc. All rights reserved.