Article ID Journal Published Year Pages File Type
5777541 Journal of Combinatorial Theory, Series A 2017 15 Pages PDF
Abstract
We use an algebraic method to prove a degree version of the celebrated Erdős-Ko-Rado theorem: given n>2k, every intersecting k-uniform hypergraph H on n vertices contains a vertex that lies on at most (n−2k−2) edges. This result implies the Erdős-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 Erdős on hypergraph matchings. Improving the work of Bollobás, Daykin, and Erdős from 1976, we show that, given integers n, k, s with n≥3k2s, every k-uniform hypergraph H on n vertices with minimum vertex degree greater than (n−1k−1)−(n−sk−1) contains s disjoint edges.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,