Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777541 | Journal of Combinatorial Theory, Series A | 2017 | 15 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hao Huang, Yi Zhao,