A Construction of Almost Steiner Systems |
| |
| Authors: | Asaf Ferber Rani Hod Michael Krivelevich Benny Sudakov |
| |
| Affiliation: | 1. School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel;2. School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel;3. Department of Mathematics, ETH, Zurich, Switzerland;4. Department of Mathematics, UCLA, Los Angeles, California |
| |
| Abstract: | Let n, k, and t be integers satisfying  . 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  . In this note we prove that for every  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. |
| |
| Keywords: | Steiner systems |
|
|
