pith. sign in

arxiv: 1605.07535 · v1 · pith:543K4UX5new · submitted 2016-05-24 · 🧮 math.CO

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

classification 🧮 math.CO
keywords degreehypergraphbinomconjecturecontainsedgeseverygiven
0
0 comments X
read the original abstract

We use an algebraic method to prove a degree version of the celebrated Erd\H os-Ko-Rado theorem: given $n>2k$, every intersecting $k$-uniform hypergraph $H$ on $n$ vertices contains a vertex that lies on at most $\binom{n-2}{k-2}$ edges. This result can be viewed as a special case of the degree version of a well-known conjecture of Erd\H{o}s on hypergraph matchings. Improving the work of Bollob\'as, Daykin, and Erd\H os from 1976, we show that given integers $n, k, s$ with $n\ge 3k^2 s$, every $k$-uniform hypergraph $H$ on $n$ vertices with minimum vertex degree greater than $\binom{n-1}{k-1}-\binom{n-s}{k-1}$ contains $s$ disjoint edges.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.