A construction of almost Steiner systems

DOI10.1002/JCD.21380zbMATH Open1307.05022arXiv1303.4065OpenAlexW1524753800MaRDI QIDQ2935201FDOQ2935201

Asaf Ferber, Michael Krivelevich, Rani Hod, Benny Sudakov

Publication date: 22 December 2014

Published in: Journal of Combinatorial Designs (Search for Journal in Brave)

Abstract: Let $n$, $k$, and $t$ be integers satisfying $n>k>tge2$. 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 $tgeq6$. In this note we prove that for every $k>tge2$ 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.

Full work available at URL: https://arxiv.org/abs/1303.4065

Recommendations

• Steiner t-Designs for Large t
• scientific article; zbMATH DE number 874486
• scientific article; zbMATH DE number 4051640
• Publication:3033772
• On infinite Steiner systems

zbMATH Keywords

Steiner systemalmost Steiner system

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Steiner systems in finite geometry (51E10) Triple systems (05B07)

Cites Work

• On a packing and covering problem
• More-than-nearly-perfect packings and partial designs
• Title not available (Why is that?)
• Nearly optimal partial Steiner systems

Cited In (7)

• Title not available (Why is that?)
• Supersaturation of \(C_4\): from Zarankiewicz towards Erdős-Simonovits-Sidorenko
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Title not available (Why is that?)
• On an infinite class of Steiner systems constructed from affine spaces
• Title not available (Why is that?)
• Steiner t-Designs for Large t

This page was built for publication: A construction of almost Steiner systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2935201)