KAIST Discrete Math Seminar

We show that an n-vertex hypergraph with no r-regular subgraph has at most 2^n-1+r-2 edges. We conjecture that if n>r, then every n-vertex hypergraph with no r-regular subgraph having the maximum number of edges contains a full star, meaning 2^n-1 distinct edges containing a single vertex. We prove this conjecture for n≥425. This is joint work with Alexandr V. Kostochka.