A Construction of Almost Steiner Systems. Issue 11 (10th November 2013)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Hod, Rani; Krivelevich, Michael; Sudakov, Benny
• Is Part Of: Journal of combinatorial designs. Volume 22:Issue 11(2014:Nov.)
• Page Start: 488
• Page End: 494
• Publication Date: 2013-11-10
• Subjects: Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21380
• Languages: English
• ISSNs: 1063-8539

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <italic>n</italic>, <italic>k</italic>, and <italic>t</italic> be integers satisfying <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1800mrgg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21380:jcd21380-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>></mml:mo><mml:mi>k</mml:mi><mml:mo>></mml:mo><mml:mi>t</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. A Steiner system with parameters <italic>t</italic>, <italic>k</italic>, and <italic>n</italic> is a <italic>k</italic>‐uniform hypergraph on <italic>n</italic> vertices in which every set of <italic>t</italic> distinct vertices is contained in exactly one edge. An outstanding problem in Design Theory is to determine whether a nontrivial Steiner system exists for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1800mrb8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21380:jcd21380-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>t</mml:mi><mml:mo>≥</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. In this note we prove that for every <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1800mr9q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21380:jcd21380-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>></mml:mo><mml:mi>t</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> and sufficiently large <italic>n</italic>, there exists an almost Steiner system with parameters <italic>t</italic>, <italic>k</italic>, and <italic>n</italic>; that is, there exists a <italic>k</italic>‐uniform hypergraph on <italic>n</italic> vertices such that every set of <italic>t</italic> distinct vertices is covered by either one or two edges.</p> </abstract>