Maximum hypergraphs without regular subgraphs

Jaehoon Kim (김재훈)

Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA

Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA

2011/06/03 Fri 4PM-5PM (Room 3433, Bldg. E6-1)

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.