Search

A triple system is cancellative if it does not contain three distinct sets A , B , C such that the symmetric difference of A and B is contained in C. We show that every cancellative triple system H that satisfies a particular inequality between the sizes of H and its shadow must be structurally close to the balanced blowup of some Steiner triple system. Our result contains a stability theorem for cancellative triple systems due to Keevash and Mubayi as a special case. It also implies that the boundary of the feasible region of cancellative triple systems has infinitely many local maxima, thus giving the first example showing this phenomenon. [ABSTRACT FROM AUTHOR]

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 r ≤ ε n 2 triples, it can always be embedded into a complete STS of order n + O (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 def (G) of the graph G with respect to the property P to be the smallest positive integer t such that the join G ⁎ 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. The main goal of this paper is to propose a systematic study of these problems; thus several future research directions are also given. [ABSTRACT FROM AUTHOR]

Abstract: Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. Lap Chi Lau proved that the conclusion holds whenever S is 24k-edge-connected in G. We improve Lauʼs result by showing that it suffices for S to be 6.5k-edge-connected in G. This and an analogous result for packing stronger objects called “S-connectors” follow from a common generalization of the Tree Packing Theorem and Hakimiʼs criterion for orientations with specified outdegrees. We prove the general theorem using submodular functions and the Matroid Union Theorem. [Copyright &y& Elsevier]

Let S be a Steiner triple system and G a cubic graph. We say that G is S-colourable if its edges can be coloured so that at each vertex the incident colours form a triple of S. We show that if S is a projective system PG(n,2), n⩾2, then G is S-colourable if and only if it is bridgeless, and that every bridgeless cubic graph has an S-colouring for every Steiner triple system of order greater than 3. We establish a condition on a cubic graph with a bridge which ensures that it fails to have an S-colouring if S is an affine system, and we conjecture that this is the only obstruction to colouring any cubic graph with any non-projective system of order greater than 3. [Copyright &y& Elsevier]