Article ID Journal Published Year Pages File Type
4656727 Journal of Combinatorial Theory, Series B 2016 23 Pages PDF
Abstract

We prove that for every integer r≥2r≥2, an n-vertex k-uniform hypergraph H containing no r  -regular subgraphs has at most (1+o(1))(n−1k−1) edges if k≥r+1k≥r+1 and n   is sufficiently large. Moreover, if r∈{3,4}r∈{3,4}, r|kr|k and k, n are both sufficiently large, then the maximum number of edges in an n-vertex k-uniform hypergraph containing no r  -regular subgraphs is exactly (n−1k−1), with equality only if all edges contain a specific vertex v. We also ask some related questions.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,