We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n-1+r-2edges. We conjecture that if n r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n-1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n < r cannot be weakened.
- Regular graph
- Set system
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics