Title    name KAIST Discrete Math Seminar     Title Maximum hypergraphs without regular subgraphs   Speaker Kim, Jaehoon (UIUC)   Date 2011-06-03   Host   Place KAIST   File     Abstract : 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.

Information Center for Mathematical Sciences KAIST 335 Gwahangno (373-1 Guseong-dong), Yuseong-gu, Daejeon 305-701, Republic of Korea TEL +82-42-869-8195~6, FAX +82-42-869-5722, e-mail : mathnet@mathnet.or.kr Copyright (c) 2009 by ICMS. All Rights Reserved