Premium
A Construction of Almost Steiner Systems
Author(s) -
Ferber Asaf,
Hod Rani,
Krivelevich Michael,
Sudakov Benny
Publication year - 2014
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21380
Subject(s) - hypergraph , combinatorics , mathematics , steiner system , steiner tree problem , existential quantification , set (abstract data type) , discrete mathematics , enhanced data rates for gsm evolution , computer science , telecommunications , programming language
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.