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]

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {H}$ with small maximum codegree has an almost‐perfect matching. We extend this result by obtaining a conflict‐free matching, where conflicts are encoded via a collection C$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {H}$ has a conflict‐free, almost‐perfect matching. This has many applications, one of which yields new asymptotic results for so‐called 'high‐girth' Steiner systems. Our main tool is a random greedy algorithm which we call the 'conflict‐free matching process'. [ABSTRACT FROM AUTHOR]

Let H$H$ be a k$k$‐uniform D$D$‐regular simple hypergraph on N$N$ vertices. Based on an analysis of the Rödl nibble, in 1997, Alon, Kim and Spencer proved that if k⩾3$k \geqslant 3$, then H$H$ contains a matching covering all but at most ND−1/(k−1)+o(1)$ND^{-1/(k-1)+o(1)}$ vertices, and asked whether this bound is tight. In this paper we improve their bound by showing that for all k>3$k > 3$, H$H$ contains a matching covering all but at most ND−1/(k−1)−η$ND^{-1/(k-1)-\eta }$ vertices for some η=Θ(k−3)>0$\eta = \Theta (k^{-3}) > 0$, when N$N$ and D$D$ are sufficiently large. Our approach consists of showing that the Rödl nibble process not only constructs a large matching but it also produces many well‐distributed 'augmenting stars' which can then be used to significantly improve the matching constructed by the Rödl nibble process. Based on this, we also improve the results of Kostochka and Rödl from 1998 and Vu from 2000 on the size of matchings in almost regular hypergraphs with small codegree. As a consequence, we improve the best known bounds on the size of large matchings in combinatorial designs with general parameters. Finally, we improve the bounds of Molloy and Reed from 2000 on the chromatic index of hypergraphs with small codegree (which can be applied to improve the best known bounds on the chromatic index of Steiner triple systems and more general designs). [ABSTRACT FROM AUTHOR]

Recently Chase determined the maximum possible number of cliques of size t in a graph on n vertices with given maximum degree. Soon afterward, Chakraborti and Chen answered the version of this question in which we ask that the graph have m edges and fixed maximum degree (without imposing any constraint on the number of vertices). In this paper we address these problems on hypergraphs. For s-graphs with s\geq 3 a number of issues arise that do not appear in the graph case. For instance, for general s-graphs we can assign degrees to any i-subset of the vertex set with 1≤ i ≤ s 1. We establish bounds on the number of t-cliques in an s-graph H with i-degree bounded by Δ in three contexts: H has n vertices; H has m (hyper)edges; and (generalizing the previous case) H has a fixed number p of u-cliques for some u with s≤ u≤ t. When Δ is of a special form we characterize the extremal s-graphs and prove that the bounds are tight. These extremal examples are the shadows of either Steiner systems or partial Steiner systems. On the way to proving our uniqueness results, we extend results of Füredi and Griggs on uniqueness in Kruskal--Katona from the shadow case to the clique case. [ABSTRACT FROM AUTHOR]

One way to study the combinatorics of finite metric spaces is to study the betweenness relation associated with the metric space. In the hypergraph metrization problem, one has to find and characterize metric betweennesses with collinear triples (or alternatively, non-degenerate triangles) that coincide with the edges of a given 3-uniform hypergraph. Metrizability of different kinds of hypergraphs was investigated in the last decades. Chen showed that Steiner triple systems are not metric, while Richmond and Richmond characterized linear betweennesses, i.e. metric betweennesses that realize the complete 3-uniform hypergraph. The latter result was also generalized to pseudometric (almost-metric) betweennesses by Beaudou et al. In this paper, we further extend this theory by characterizing the largest non-linear almost-metric betweennesses that satisfy certain hereditary properties, as well as the ones that contain a small linear number of non-degenerate triangles. [ABSTRACT FROM AUTHOR]

A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its "combinatorial shadow". We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities. [ABSTRACT FROM AUTHOR]

Consider the following problem. In a school with three classes containing n students each, given that their genders are unknown, find the minimum possible number of triples of same-gender students—not all of which are from the same class. Muaengwaeng asked this question and conjectured that the minimum scenario occurs when the classes are all boys, all girls and half-and-half. In this paper, we solve many generalizations of the problem including when the school has more than three classes, when triples are replaced by groups of larger sizes, when the classes are of different sizes, and when gender is replaced by other non-binary attributes. [ABSTRACT FROM AUTHOR]

We consider edge decompositions of K v (3) − I , the complete 3-uniform hypergraph of order v minus a set of v / 3 mutually disjoint edges (1-factor). We prove that a decomposition into tight 6-cycles exists if and only if v ≡ 0 , 3 , 6 (mod 12) and v ≥ 6 ; and a decomposition into tight 9-cycles exists for all v ≥ 9 divisible by 3. These results are complementary to the theorems of Akin et al. [Discrete Math. 345 (2022)] and Bunge et al. [Australas. J. Combin. 80 (2021)] who settled the case of K v (3). [ABSTRACT FROM AUTHOR]

A linear hypergraph, also known as a partial Steiner system, is a collection of subsets of a set such that no two of the subsets have more than one element in common. Most studies of linear hypergraphs consider only the uniform case, in which all the subsets have the same size. In this paper we provide, for the first time, asymptotically precise estimates of the number of linear hypergraphs in the non-uniform case, as a function of the number of subsets of each size. [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]

For a family F of r‐graphs, let ex(n,F) denote the maximum number of edges in an F‐free r‐graph on n vertices. Let Fr(v,e) denote the family of all r‐graphs with e edges and at most v vertices. We prove that ex(n,Fr(r+1,2)∪Fr(r+2,3))=(1r−o(1))(nr−1). [ABSTRACT FROM AUTHOR]

Let Ct denote the loose cycle on t = 2s vertices, that is, the 3-uniform hypergraph obtained from a graph cycle C on s vertices by replacing each edge e =\{ u, v\} of C with the edge triple\{ u, xe, v\}, where xe is uniquely assigned to e. We will give a tight minimum degree condition that guarantees all sufficiently large 3-uniform hypergraphs on n\in tZ vertices contain n t vertex disjoint copies of Ct. [ABSTRACT FROM AUTHOR]

The existence of Steiner triple systems STS(n) of order n containing no nontrivial subsystem is well known for every admissible n. We generalize this result in two ways. First we define the expander property of 3-uniform hypergraphs and show the existence of Steiner triple systems which are almost perfect expanders. Next we define the strong and weak spreading property of linear hypergraphs, and determine the minimum size of a linear triple system with these properties, up to a small constant factor. A linear triple system on a vertex set V has the spreading, or respectively weakly spreading property if any sufficiently large subset V 0 ⊂ V contains a pair of vertices with which a vertex of V rV 0 forms a triple of the system. Here the condition on V 0 refers to jV 0j 4 or V 0 is the support of more than one triples, respectively. This property is strongly connected to the connectivity of the structure the so-called inuence maximisation. We also discuss how the results are related to Erd}os' conjecture on locally sparse STSs, subsquare-free Latin-squares and possible applications in finite geometry. [ABSTRACT FROM AUTHOR]

We prove that any Steiner triple system S, with n = v(S) sufficiently large, admits a packing by almost spanning paths that covers almost all edges. More formally, for any μ > 0, we obtain a family of (1-μ)n=3 pairwise edge-disjoint paths, with (1-μ)n vertices each, all contained in S. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the following question: given an arbitrary Steiner triple system S on m vertices and any 3‐uniform hypertree T on n vertices, is it necessary that S contains T as a subgraph provided m≥(1+μ)n? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive. [ABSTRACT FROM AUTHOR]

We construct a Ramsey class whose objects are Steiner systems. In contrast to the situation with general r -uniform hypergraphs, it turns out that simply putting linear orders on their sets of vertices is not enough for this purpose: one also has to strengthen the notion of subobjects used from “induced subsystems” to something we call “strongly induced subsystems”. Moreover we study the Ramsey properties of other classes of Steiner systems obtained from this class by either forgetting the order or by working with the usual notion of subsystems. This leads to a perhaps surprising induced Ramsey theorem in which designs get coloured. [ABSTRACT FROM AUTHOR]

We call a partial Steiner triple system C (configuration) t-Ramsey if for large enough n (in terms of [ABSTRACT FROM AUTHOR]

Erdős [1] conjectured that for all $${k \geq 2}$$ , $${s \geq 1}$$ and $${n \geq {k(s+1)}}$$ , an n-vertex k-uniform hypergraph $${\mathcal{F}}$$ with $${\nu(\mathcal{F})=s}$$ cannot have more than $${\max\{\binom{sk+k-1}k,\binom nk-\binom{n-s}k\}}$$ edges. It took almost fifty years to prove it for triple systems. In [5] we proved the conjecture for all s and all $${n \geq 4(s+1)}$$ . Then Łuczak and Mieczkowska [6] proved the conjecture for sufficiently large s and all n. Soon after, Frankl proved it for all s. Here we present a simpler version of that proof which yields Erdős' conjecture for $${s \geq 33}$$ . Our motivation is to lay down foundations for a possible proof in the much harder case k = 4, at least for large s. [ABSTRACT FROM AUTHOR]

A cross-free set of size m in a Steiner triple system [ABSTRACT FROM AUTHOR]

This paper deals with extremal problems concerning colorings of partial Steiner systems. We establish a new sufficient condition for r-colorability of a hypergraph from some class of such systems in terms of maximum vertex degree. Moreover, as a corollary we obtain a new lower bound for the threshold probability for r-colorability of a random hypergraph in a binomial model. [ABSTRACT FROM AUTHOR]

The expansion G+ of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a new vertex disjoint from V(G) such that distinct edges are enlarged by distinct vertices. Let ex3 (n, F) denote the maximum number of edges in a 3-uniform hypergraph with n vertices not containing any copy of a 3-uniform hypergraph F. The study of ex3(n, G+) includes some well-researched problems, including the case that F consists of k disjoint edges, G is a triangle, G is a path or cycle, and G is a tree. In this paper we initiate a broader study of the behavior of ex3(n, G+). Specifically, we show ex3 (n, K s,t+) = Θ(n3-3/s) whenever t > (s -- 1)! and s ≥ 3. One of the main open problems is to determine for which graphs G the quantity ex3 (n, G+) is quadratic in n. We show that this occurs when G is any bipartite graph with Turan number o(nφ) where φ = 1+√5/2, and in particular this shows ex3 (n, G+) = O(n²) when G is the three-dimensional cube graph. [ABSTRACT FROM AUTHOR]

Let n, k, and t be integers satisfying [ABSTRACT FROM AUTHOR]

The Turán number of hypergraphs has been studied extensively. Here we deal with a recent direction, the linear Turán number, and restrict ourselves to linear triple systems, a collection of triples on a set of points in which any two triples intersect in at most one point. For a fixed linear triple system F , the linear Turán number ex L (n , F) is the maximum number of triples in a linear triple system with n points that does not contain F as a subsystem. We initiate the study of the linear Turán number for an acyclic F. In this case ex L (n , F) is linear in n and we aim for good bounds. Since the case of trees is already difficult for graphs (Erdős–Sós conjecture), we concentrate on matchings, paths and small trees. In case of matchings, where M k is the set of k pairwise disjoint triples, we prove that for fixed k and large enough n , ex L (n , M k) = f (n , k) where f (n , k) is the maximum number of triples that can meet k − 1 points in a linear triple system on n points. This is an analogue of an old result of Erdős on hypergraph matchings. For the k -edge linear path P k we show (extending some standard path increasing methods used for graphs) that ex L (n , P k) ≤ 1. 5 k n which is probably far from best possible. Finding ex L (n , F) relates to difficult problems on Steiner triple systems and interesting even for small trees. For example, for P 4 , the path with four triples, ex L (n , P 4) ≤ 4 n 3 with equality only for disjoint union of affine planes of order 3. On the other hand, for E 4 , the tree having three pairwise disjoint triples and a fourth one meeting all of them, we have bounds only: 6 ⌊ n − 3 4 ⌋ ≤ ex L (n , E 4) ≤ 2 n. [ABSTRACT FROM AUTHOR]

Abstract: In this short survey, some approaches that can be used to solve the generalized -design problem are considered. Special cases of the generalized -design problem include well-known conjectures for -designs, degree sequences of graphs and hypergraphs, and partial Steiner systems. Also described are some related problems such as the characterization of -vectors of pure simplicial complexes, which are well known but little understood. Some suggestions how enumerative and polyhedral techniques may help are also described. [Copyright &y& Elsevier]

Abstract: A friendship 3-hypergraph is a 3-hypergraph in which for any 3 distinct vertices , and , there exists a unique fourth vertex such that , , are 3-hyperedges. Sós constructed friendship 3-hypergraphs using Steiner triple systems. Hartke and Vandenbussche showed that any friendship 3-hypergraph can be partitioned into ’s. (A is the set of four hyperedges of size three that can be formed from a set of 4 elements.) These ’s form a set of 4-tuples which we call a friendship design. We define a geometric friendship design to be a resolvable friendship design that can be embedded into an affine geometry. Refining the problem from friendship designs to geometric friendship designs allows us to state some structure results about these geometric friendship designs and decrease the search space when searching for geometric friendship designs. Hartke and Vandenbussche discovered 5 new examples of friendship designs which happen to be geometric friendship designs. We show the 3 non-isomorphic geometric designs on 16 vertices are the only such non-isomorphic geometric designs on 16 vertices. We also improve the known lower and upper bounds on the number of hyperedges in any friendship 3-hypergraph. Finally, we show that no friendship 3-hypergraph exists on 11 or 12 points. [Copyright &y& Elsevier]

Abstract: Masbaum and Vaintrobʼs “Pfaffian matrix-tree theorem” implies that counting spanning trees of a 3-uniform hypergraph (abbreviated to 3-graph) can be done in polynomial time for a class of “3-Pfaffian” 3-graphs, comparable to and related to the class of Pfaffian graphs. We prove a complexity result for recognizing a 3-Pfaffian 3-graph and describe two large classes of 3-Pfaffian 3-graphs – one of these is given by a forbidden subgraph characterization analogous to Littleʼs for bipartite Pfaffian graphs, and the other consists of a class of partial Steiner triple systems for which the property of being 3-Pfaffian can be reduced to the property of an associated graph being Pfaffian. We exhibit an infinite set of partial Steiner triple systems that are not 3-Pfaffian, none of which can be reduced to any other by deletion or contraction of triples. We also find some necessary or sufficient conditions for the existence of a spanning tree of a 3-graph (much more succinct than can be obtained by the currently fastest polynomial-time algorithm of Gabow and Stallmann for finding a spanning tree) and a superexponential lower bound on the number of spanning trees of a Steiner triple system. [Copyright &y& Elsevier]

A Steiner System, denoted S(t, k, υ), is a vertex set X containing υ vertices, and a collection of subsets of X of size k, called blocks, such that every t vertices from X are in exactly one of the blocks. A Steiner Triple System, or STS, is a special case of a Steiner System where t = 2, k = 3 and υ = 1 or 3 (mod6) [7]. A Bi-Steiner Triple System, or BSTS, is a Steiner Triple System with the vertices colored in such a way that each block of vertices receives precisely two colors. Out of the 80 BSTS(15)s, only 23 are colorable [1]. In this paper, using a computer program that we wrote, we give a complete description of all proper colorings, all feasible partitions, chromatic polynomial and chromatic spectrum of every colorable BSTS(15). [ABSTRACT FROM AUTHOR]

Abstract: A family of k-subsets of an n-set X is disjoint union-free (DUF) if all disjoint pairs of elements of have distinct unions; that is, if for every , and implies . DUF families of maximum size have been studied by Erdös and Füredi. Let be DUF with the property that is not DUF for any k-subset E of X not already in . Then is maximally DUF. We introduce the problem of finding the minimum size of maximally DUF families and provide bounds on this quantity for . [Copyright &y& Elsevier]

In this paper we introduce the notion of a bicolour graph of a Steiner triple system. Given an arbitrary colouring of the points of a Steiner triple system, the bicolour graph is the graph obtained on the point set of the system by placing an edge between two points if they have the same colour and appear in a triple with a point of a different colour. The case where the graph is Kv was partially solved by Colbourn et al. (Electron. J. Combin. 6(1) (1999) 16) and the case where the graph is an independent set was solved by Milici et al. (Discrete Math. 240(1–3) (2001) 145–160). We show that every near 1-factor may occur as the bicolour graph of a Steiner triple system with four exceptions. In addition we consider the cases of a 2-factor and a near 2-factor and the complement of a 2-factor. [Copyright &y& Elsevier]

The Erdo˝s–Stone–Simonovits Theorem implies that the Tura´n density of a family of graphs is the minimum of the Tura´n densities of the individual graphs from the family. It was conjectured by Mubayi and Ro¨dl (J. Combin. Theory Ser. A, submitted) that this is not necessarily true for hypergraphs, in particular for triple systems. We give an example, which shows that their conjecture is true. [Copyright &y& Elsevier]

For a family of r-graphs F the Tura´n number ex (n, F) is the maximum number of edges in an n vertex r-graph that does not contain any member of F. The Tura´n density π(F)=limlower limit n→∞ ex(n,F)/((nr). When F is an r-graph, π(F)≠0, and r>2, determining π(F) is a notoriously hard problem, even for very simple r-graphs F. For example, when r=3, the value of π(F) is known for very few (<10) irreducible r-graphs. Building upon a method developed recently by de Caen and Fu¨redi (J. Combin. Theory Ser. B78 (2000), 274–276), we determine the Tura´n densities of several 3-graphs that were not previously known. Using this method, we also give a new proof of a result of Frankl and Fu¨redi (Combinatorica 3 (1983), 341–349) that π(H)=2/9, where H has edges 123,124,345. Let F(3,2) be the 3-graph 123,145,245,345, let K−4 be the 3-graph 123,124,234, and let C5 be the 3-graph 123,234,345,451,512. We prove

In this paper we study Turán and Ramsey numbers in linear triple systems, defined as 3-uniform hypergraphs in which any two triples intersect in at most one vertex. A famous result of Ruzsa and Szemerédi is that for any fixed c > 0 and large enough n the following Turán-type theorem holds. If a linear triple system on n vertices has at least c n 2 edges then it contains a triangle : three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called s -configurations. The main tool is a generalization of the induced matching lemma from a b a -patterns to more general ones. We slightly generalize s -configurations to extended s -configurations. For these we cannot prove the corresponding Turán-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any t -coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail C 15 (configuration with blocks 123, 345, 561 and 147), are t -Ramsey for any t ≥ 1. The most interesting one among them is the wicket , D 4 , formed by three rows and two columns of a 3 × 3 point matrix. In fact, the wicket is 1-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of constructing hypercycle systems of 5-cycles in complete 3-uniform hypergraphs. A hypercycle system C (r , k , v) of order v is a collection of r-uniform k-cycles on a v-element vertex set, such that each r-element subset is an edge in precisely one of those k-cycles. We present cyclic hypercycle systems C (3 , 5 , v) of orders v = 25 , 26 , 31 , 35 , 37 , 41 , 46 , 47 , 55 , 56 , a highly symmetric construction for v = 40 , and cyclic 2-split constructions of orders 32 , 40 , 50 , 52 . As a consequence, all orders v ≤ 60 permitted by the divisibility conditions admit a C (3 , 5 , v) system. New recursive constructions are also introduced. [ABSTRACT FROM AUTHOR]

The existence of Steiner triple systems STS (n) of order n containing no nontrivial subsystem is well known for every admissible n. We generalize this result in two ways. First we define the expander property of 3-uniform hypergraphs and show the existence of Steiner triple systems which are almost perfect expanders. Next we define the strong and weak spreading properties of linear hypergraphs, and determine the minimum size of a linear triple system with these properties, up to a small constant factor. This property is strongly connected to the connectivity of the structure and of the so-called influence maximization. We also discuss how the results are related to Erdős' conjecture on locally sparse STS s, influence maximization, subsquare-free Latin squares and possible applications in finite geometry. [ABSTRACT FROM AUTHOR]