Open Collections

Completion and deficiency problems

Banff International Research Station for Mathematical Innovation and Discovery

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 talk we answer it for relatively sparse STSs, showing that given a partial STS of order n with at most $r \leq \epsilon n^2$ triples, it can always be embedded into a complete STS of order $n+O(\sqrt{r})$, 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 P and a graph G, we define the deficiency of the graph G with respect to the property P to be the smallest positive integer $t$ such that the join $G\ast K_t$ has property P. 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. This is joint work with Rajko Nenadov and Benny Sudakov

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: ETH

2020-03-03

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73670

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/