Completion and deficiency problems

DOI10.1016/J.JCTB.2020.05.004MaRDI QIDQ2200922zbMATH OpenOpenAlexFDO

Authors Rajko Nenadov, Adam Zsolt Wagner, Benny Sudakov

Publication date 24 September 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

completion problemsdeficiencySteiner triple systemsembedding partial designs

Mathematics Subject Classification ID

Other designs, configurations (05B30) Triple systems (05B07)

Abstract: Given a partial Steiner triple system (STS) of order $n$, what is the order of the smallest complete STS it can be embedded into? The study of this question goes back more than 40 years. In this paper we answer it for relatively sparse STSs, showing that given a partial STS of order $n$ with at most $rlevarepsilon{n}^2$ triples, it can always be embedded into a complete STS of order $n+O(sqrtr)$, which is asymptotically optimal. We also obtain similar results for completions of Latin squares and other designs. This suggests a new, natural class of questions, called deficiency problems. Given a global spanning property $mathcalP$ and a graph $G$, we define the deficiency of the graph $G$ with respect to the property $mathcalP$ to be the smallest positive integer $t$ such that the join $Gast{K}_t$ has property $mathcalP$. To illustrate this concept we consider deficiency versions of some well-studied properties, such as having a $K_k$-decomposition, Hamiltonicity, having a triangle-factor and having a perfect matching in hypergraphs. The main goal of this paper is to propose a systematic study of these problems; thus several future research directions are also given.

Recommendations

• On deficiency problems for graphs
• Embedding partial Steiner triple systems with few triples
• Embedding partial triple systems
• scientific article; zbMATH DE number 1123810
• Minimum embedding of Steiner triple systems into \((K_4 - e)\)-designs. II

Cites work

• scientific article; zbMATH DE number 3737686 (Why is no real title available?)
• scientific article; zbMATH DE number 3565005 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A Combinatorial Theorem with an Application to Latin Rectangles
• A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
• A conjecture on small embeddings of partial Steiner triple systems
• A degree sequence Hajnal-Szemerédi theorem
• A generalization of transversals for Latin squares
• A multipartite Hajnal-Szemerédi theorem
• A note on the path cover number of regular graphs
• A partial Steiner triple system of order n can be embedded in a Steiner triple system of order 6n + 3
• A proof of Lindner's conjecture on embeddings of partial Steiner triple systems
• An Ore-type theorem on equitable coloring
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
• Arc coverings of graphs
• Clique decompositions of multipartite graphs and completion of Latin squares
• Combinatorial designs and perfect codes
• Completing small partial triple systems
• Covering the vertices of a graph by vertex-disjoint paths
• Embedding Incomplete Latin Squares
• Embedding Partial Steiner Triple Systems
• Embedding partial Steiner triple systems with few triples
• Embeddings of partial Steiner triple systems
• Existence and embeddings of partial Steiner triple systems of order ten with cubic leaves
• Extremal problems for finite sets
• Finite embedding theorems for partial Latin squares, quasi-groups, and loops
• Finite partial quadruple systems can be finitely embedded
• Forbidding Hamilton cycles in uniform hypergraphs
• Fractional clique decompositions of dense partite graphs
• Fractional triangle decompositions in graphs with large minimum degree
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian circuits and path coverings of vertices in graphs
• On Hamilton's ideals
• On the finite completion of partial latin cubes
• On the maximal number of independent circuits in a graph
• Small embeddings of partial Steiner triple systems
• Thank Evans!
• The completion of finite incomplete Steiner triple systems with applications to loop theory
• The complexity of completing partial Latin squares
• Variants of the Hajnal-Szemer�di Theorem

Cited in

(7)

• Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths
• scientific article; zbMATH DE number 1279046 (Why is no real title available?)
• The \(n\)-queens completion problem
• On deficiency problems for graphs
• An Evans-style result for block designs
• Hamilton completion and the path cover number of sparse random graphs
• On sufficient conditions for spanning structures in dense graphs

This page was built for publication: Completion and deficiency problems

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