2013/03/17 by Ferber, Asaf, Hod, Rani, Krivelevich, Michael +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1303.4065
Let n, k, and t be integers satisfying n>k>t≥2. A Steiner system with parameters t, k, and n is a k-uniform hypergraph on n vertices in which every set of t distinct vertices is contained in exactly one edge. An outstanding problem in Design Theory is to determine whether a nontrivial Steiner system exists for t≥6. In this note we prove that for every k>t≥2 and sufficiently large n, there exists an almost Steiner system with parameters t, k, and n; that is, there exists a k-uniform hypergraph on n vertices such that every set of t distinct vertices is covered by either one or two edges.