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 2n-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 2n-1 distinct edges containing a single vertex. We prove this conjecture for n≥425. This is joint work with Alexandr V. Kostochka.
Tags: 김재훈