A Construction of Almost Steiner Systems. Issue 11 (10th November 2013) - Ferber, Asaf; Hod, Rani; Krivelevich, Michael; Sudakov, Benny
Abstract Let n, k, and t be integers satisfying <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1800mrgg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n>k>t≥2</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1800mrb8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />t≥6</alternatives>. In this note we prove that for every <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1800mr9q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k>t≥2</alternatives> 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.