Completion and deficiency problems

DOI10.1016/J.JCTB.2020.05.004zbMATH Open1448.05024arXiv1904.01394OpenAlexW3030526969MaRDI QIDQ2200922FDOQ2200922

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)

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.

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

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

zbMATH Keywords

completion problemsdeficiencySteiner triple systemsembedding partial designs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• The \(n\)-queens completion problem
• An Evans-Style Result for Block Designs
• On deficiency problems for graphs
• Title not available (Why is that?)
• On sufficient conditions for spanning structures in dense graphs
• Hamilton completion and the path cover number of sparse random graphs
• Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths

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)