Search

This paper lies in the context of the studies of eigenfunctions of graphs having minimum cardinality of support. One of the tools is the weight‐distribution bound, a lower bound on the cardinality of support of an eigenfunction of a distance‐regular graph corresponding to a nonprincipal eigenvalue. The tightness of the weight‐distribution bound was previously shown in general for the smallest eigenvalue of a Grassmann graph. However, a characterisation of optimal eigenfunctions was not obtained. Motivated by this open problem, we consider the class of strongly regular Grassmann graphs and give the required characterisation in this case. We then show the tightness of the weight‐distribution bound for block graphs of affine designs (defined on the lines of an affine space with two lines being adjacent when intersect) and obtain a similar characterisation of optimal eigenfunctions. [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]

The Turán number T(n,5,3) $T(n,5,3)$ is the minimum size of a system of triples out of a base set X $X$ of n $n$ elements such that every quintuple in X $X$ contains a triple from the system. The exact values of T(n,5,3) $T(n,5,3)$ are known for n≤17 $n\le 17$. Turán conjectured that T(2m,5,3)=2m3 $T(2m,5,3)=2\left(\genfrac{}{}{0.0pt}{}{m}{3}\right)$, and no counterexamples have been found so far. If this conjecture is true, then T(2m+1,5,3)≥⌈m(m−2)(2m+1)∕6⌉ $T(2m+1,5,3)\ge \lceil m(m-2)(2m+1)\unicode{x02215}6\rceil $. We prove the matching upper bound for all n=2m+1>17 $n=2m+1\gt 17$ except n=27 $n=27$. [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]

Steiner triple systems (STSs) have been classified up to order 19. Earlier estimations of the number of isomorphism classes of STSs of order 21, the smallest open case, are discouraging as for classification, so it is natural to focus on the easier problem of merely counting the isomorphism classes. Computational approaches for counting STSs are here considered and lead to an algorithm that is used to obtain the number of isomorphism classes for order 21: 14,796,207,517,873,771. [ABSTRACT FROM AUTHOR]

A line coloring of PG(n,q) $\text{PG}(n,q)$, the n $n$‐dimensional projective space over GF(q) $(q)$, is an assignment of colors to all lines of PG(n,q) $\text{PG}(n,q)$ so that any two lines with the same color do not intersect. The chromatic index of PG(n,q) $\text{PG}(n,q)$, denoted by χ′(PG(n,q)) $\chi ^{\prime} (\text{PG}(n,q))$, is the least number of colors for which a coloring of PG(n,q) $\text{PG}(n,q)$ exists. This paper translates the problem of determining the chromatic index of PG(n,q) $\text{PG}(n,q)$ to the problem of examining the existences of PG(3,q) $\text{PG}(3,q)$ and PG(4,q) $\text{PG}(4,q)$ with certain properties. In particular, it is shown that for any odd integer n $n$ and q∈{3,4,8,16},χ′(PG(n,q))=(qn−1)∕(q−1) $q\in \{3,4,8,16\},\chi ^{\prime} (\text{PG}(n,q))=({q}^{n}-1)\unicode{x02215}(q-1)$, which implies the existence of a parallelism of PG(n,q) $\text{PG}(n,q)$ for any odd integer n $n$ and q∈{3,4,8,16} $q\in \{3,4,8,16\}$. [ABSTRACT FROM AUTHOR]

In 1971, Doyen and Vandensavel gave a special doubling construction that gives a direct construction of 2‐chromatic Steiner quadruple system of order v $v$ (SQS(v) $(v)$) for all v≡4 $v\equiv 4$ or 8(mod12) $8\,(\mathrm{mod}\,12)$. The first author presented a construction for 2‐chromatic SQSs based on 2‐chromatic candelabra quadruple systems and s $s$‐fan designs. In this paper, it is proved that a 2‐chromatic SQS(v) $(v)$ also exists if v≡10(mod12) $v\equiv 10\,(\mathrm{mod}\,12)$, or if v≡2(mod24) $v\equiv 2\,(\mathrm{mod}\,24)$. [ABSTRACT FROM AUTHOR]

A Kirkman triple system of order v, KTS(v), is a resolvable Steiner triple system on v elements. In this paper, we investigate an open problem posed by Doug Stinson, namely the existence of KTS(v) which contain as a subdesign a Steiner triple system of order u, an STS(u). We present several different constructions for designs of this form. As a consequence, we completely settle the extremal case v=2u+1, for which a list of possible exceptions had remained for close to 30 years. Our new constructions also provide the first infinite classes for the more general problem. We reduce the other maximal case v=2u+3 to (at present) three possible exceptions. In addition, we obtain results for other cases of the form v=2u+w and also near v=3u. Our primary method introduces a new type of Kirkman frame which contains group divisible design subsystems. These subsystems can occur with different configurations, and we use two different varieties in our constructions. [ABSTRACT FROM AUTHOR]

We address several extremal problems concerning the spreading property of point sets of Steiner triple systems. This property is closely related to the structure of subsystems, as a set is spreading if and only if there is no proper subsystem which contains it. We give sharp upper bounds on the size of a minimal spreading set in a Steiner triple system and show that if all the minimal spreading sets are large then the examined triple system must be a projective space. We also show that the size of a minimal spreading set is not an invariant of a Steiner triple system. [ABSTRACT FROM AUTHOR]

Steiner triple systems form one of the most studied classes of combinatorial designs. Configurations, including subsystems, play a central role in the investigation of Steiner triple systems. With sporadic instances of small systems, ad hoc algorithms for counting or listing configurations are typically fast enough for practical needs, but with many systems or large systems, the relevance of computational complexity and algorithms of low complexity is highlighted. General theoretical results as well as specific practical algorithms for important configurations are presented. [ABSTRACT FROM AUTHOR]

We propose a method of constructing block designs which combine genetic algorithm and a method for constructing designs with a prescribed automorphism group using tactical decompositions (i.e., orbit matrices). We apply this method to construct new Steiner systems with parameters S(2,5,45) $S(2,5,45)$ and new symmetric designs with parameters (71, 15, 3). [ABSTRACT FROM AUTHOR]

A bipartite biregular (m,n;g) $(m,n;g)$‐graph Γ ${\rm{\Gamma }}$ is a bipartite graph of even girth g $g$ having the degree set {m,n} $\{m,n\}$ and satisfying the additional property that the vertices in the same partite set have the same degree. An (m,n;g) $(m,n;g)$‐bipartite biregular cage is a bipartite biregular (m,n;g) $(m,n;g)$‐graph of minimum order. In their 2019 paper, Filipovski, Ramos‐Rivera, and Jajcay present lower bounds on the orders of bipartite biregular (m,n;g) $(m,n;g)$‐graphs, and call the graphs that attain these bounds bipartite biregular Moore cages. In our paper, we improve the lower bounds obtained in the above paper. Furthermore, in parallel with the well‐known classical results relating the existence of k $k$‐regular Moore graphs of even girths g=6,8 $g=6,8$, and 12 to the existence of projective planes, generalized quadrangles, and generalized hexagons, we prove that the existence of an S(2,k,v) $S(2,k,v)$‐Steiner system yields the existence of a bipartite biregular k,v−1k−1;6 $\left(k,\frac{v-1}{k-1};6\right)$‐cage, and, vice versa, the existence of a bipartite biregular (k,n;6) $(k,n;6)$‐cage whose order is equal to one of our lower bounds yields the existence of an S(2,k,1+n(k−1)) $S(2,k,1+n(k-1))$‐Steiner system. Moreover, with regard to the special case of Steiner triple systems, we completely solve the problem of determining the orders of (3,n;6) $(3,n;6)$‐bipartite biregular cages for all integers n≥4 $n\ge 4$. Considering girths higher than 6, we relate the existence of generalized polygons (quadrangles, hexagons, and octagons) to the existence of (n+1,n2+1;8) $(n+1,{n}^{2}+1;8)$‐, (n2+1,n3+1;8) $({n}^{2}+1,{n}^{3}+1;8)$‐, (n,n+2;8) $(n,n+2;8)$‐, (n+1,n3+1;12) $(n+1,{n}^{3}+1;12)$‐ and (n+1,n2+1;16) $(n+1,{n}^{2}+1;16)$‐bipartite biregular cages, respectively. Using this connection, we also derive improved upper bounds for the orders of other classes of bipartite biregular cages of girths 8, 12, and 14. [ABSTRACT FROM AUTHOR]

The paper is a continuation of Part I and contains several further results on generalized boundary triples, the corresponding Weyl functions, and applications of this technique to ordinary and partial differential operators. We establish a connection between Post's theory of boundary pairs of closed nonnegative forms on the one hand and the theory of generalized boundary triples of nonnegative symmetric operators on the other hand. Applications to the Laplacian operator on bounded domains with smooth, Lipschitz, and even rough boundary, as well as to mixed boundary value problem for the Laplacian are given. Other applications concern with the momentum, Schrödinger, and Dirac operators with local point interactions. These operators demonstrate natural occurrence of ES$ES$‐generalized boundary triples with domain invariant Weyl functions and essentially selfadjoint reference operators A0. [ABSTRACT FROM AUTHOR]

Link prediction plays an important role in constructing knowledge graph. Recently, graph representation learning models yield state‐of‐the‐art results. However, existing models concentrate merely on triples or graph structures and mostly ignore textual descriptions, resulting in incomplete or partial information. In this paper, we propose a novel graph representation learning model to address this challenge, namely multi‐source heterogeneous information fusion with adaptive importance sampling. Our model leverages multiple sources, such triple, graph structure and textual description, and generate rich‐attribute embeddings for entities, encapsulating relations simultaneously. We also propose an adaptive importance sampling algorithm to boost aggregation of useful features from local neighbours. Additionally, we also boost node aggregation of useful features from local neighbours by adaptive importance sampling algorithm in our model. Experimental results on two benchmark datasets show that our proposed model significantly outperforms state‐of‐the‐art methods. [ABSTRACT FROM AUTHOR]

A pentagonal geometry PENT(k,r) is a partial linear space, where every line is incident with k points, every point is incident with r lines, and for each point x, there is a line incident with precisely those points that are not collinear with x. Here we generalize the concept by allowing the points not collinear with x to form the point set of a Steiner system S(2,k,w) whose blocks are lines of the geometry. [ABSTRACT FROM AUTHOR]

We introduce an impartial combinatorial game on Steiner triple systems called Next One to Fill Is the Loser (Nofil). Players move alternately, choosing points of the triple system. If a player is forced to fill a block on their turn, they lose. By computing nim‐values, we determine optimal strategies for Nofil on all Steiner triple systems up to order 15 and a sampling for orders 19, 21 and 25. The game Nofil can be thought of in terms of play on a corresponding hypergraph which will become a graph during play. At that point Nofil is equivalent to playing the game Node Kayles on the graph. We prove necessary conditions and sufficient conditions for a graph to reached playing Nofil. We conclude that the complexity of determining the outcome of the game Nofil on Steiner triple systems is PSPACE‐complete for randomized reductions. [ABSTRACT FROM AUTHOR]

Three‐dimensional (3D) micro‐and nanostructures have played an important role in topological photonics, microfluidics, acoustic, and mechanical engineering. Incorporating biomimetic geometries into the design of metastructures has created low‐density metamaterials with extraordinary physical and photonic properties. However, the use of surface‐based biomimetic geometries restricts the freedom to tune the relative density, mechanical strength, and topological phase. The Steiner tree method inspired by the feature of the shortest connection distance in biological neural networks is applied, to create 3D metastructures and, through two‐photon nanolithography, neuron‐inspired 3D structures with nanoscale features are successfully achieved. Two solutions are presented to the 3D Steiner tree problem: the Steiner tree networks (STNs) and the twisted Steiner tree networks (T‐STNs). STNs and T‐STNs possess a lower density than surface‐based metamaterials and that T‐STNs have Young's modulus enhanced by 20% than the STNs. Through the analysis of the space groups and symmetries, a topological nontrivial Dirac‐like conical dispersion in the T‐STNs is predicted, and the results are based on calculations with true predictive power and readily realizable from microwave to optical frequencies. The neuron‐inspired 3D metastructures opens a new space for designing low‐density metamaterials and topological photonics with extraordinary properties triggered by a twisting degree‐of‐freedom. [ABSTRACT FROM AUTHOR]

Let n and ℓ be positive integers. Recent papers by Kreher, Stinson, and Veitch have explored variants of the problem of ordering the points in a triple system (such as a Steiner triple system [STS], directed triple system, or Mendelsohn triple system) on n points so that no block occurs in a segment of ℓ consecutive entries (thus the ordering is locally block‐avoiding). We describe a greedy algorithm which shows that such an ordering exists, provided that n is sufficiently large when compared with ℓ. This algorithm leads to improved bounds on the number of points in cases where this was known, but also extends the results to a significantly more general setting (which includes, e.g., orderings that avoid the blocks of a design). Similar results for a cyclic variant of this situation are also established. We construct STSs and quadruple systems where ℓ can be large, showing that a bound of Stinson and Veitch is reasonable. Moreover, we generalize the Stinson–Veitch bound to a wider class of block designs and to the cyclic case. The results of Kreher, Stinson, and Veitch were originally inspired by results of Alspach, Kreher, and Pastine, who (motivated by zero‐sum avoiding sequences in abelian groups) were interested in orderings of points in a partial Steiner triple system where no segment is a union of disjoint blocks. Alspach et al. show that, when the system contains at most k pairwise disjoint blocks, an ordering exists when the number of points is more than 15k−5. By making use of a greedy approach, the paper improves this bound to 9k+O(k2∕3). [ABSTRACT FROM AUTHOR]

Let PG(Fqv) be the (v−1)‐dimensional projective space over Fq and let Γ be a simple graph of order qk−1q−1 for some k. A 2−(v,Γ,λ) design over Fq is a collection ℬ of graphs (blocks) isomorphic to Γ with the following properties: the vertex set of every block is a subspace of PG(Fqv); every two distinct points of PG(Fqv) are adjacent in exactly λ blocks. This new definition covers, in particular, the well‐known concept of a 2−(v,k,λ) design over Fq corresponding to the case that Γ is complete. In this study of a foundational nature we illustrate how difference methods allow us to get concrete nontrivial examples of Γ‐decompositions over F2 or F3 for which Γ is a cycle, a path, a prism, a generalized Petersen graph, or a Moebius ladder. In particular, we will discuss in detail the special and very hard case that Γ is complete and λ=1, that is, the Steiner 2‐designs over a finite field. Also, we briefly touch the new topic of near resolvable 2−(v,2,1) designs over Fq. This study has led us to some (probably new) collateral problems concerning difference sets. Supported by multiple examples, we conjecture the existence of infinite families of Γ‐decompositions over a finite field that can be obtained by suitably labeling the vertices of Γ with the elements of a Singer difference set. [ABSTRACT FROM AUTHOR]

We study the localization number of incidence graphs of designs. In the localization game played on a graph, the cops attempt to determine the location of an invisible robber via distance probes. The localization number of a graph G, written ζ(G), is the minimum number of cops needed to ensure the robber's capture. We present bounds on the localization number of incidence graphs of balanced incomplete block designs. Exact values of the localization number are given for the incidence graphs of projective and affine planes. Bounds are given for Steiner systems and for transversal designs. [ABSTRACT FROM AUTHOR]

It is shown that for v≠7,8,11,12, or 13, there exists an optimal covering with triples on v points that contains no Pasch configurations. [ABSTRACT FROM AUTHOR]

A (k,l)‐configuration is a set of l blocks on k points. For Steiner triple systems, (l+2,l)‐configurations are of particular interest. The smallest nontrivial such configuration is the Pasch configuration, which is a (6,4)‐configuration. A Steiner triple system of order v, an STS(v), is r‐sparse if it does not contain any (l+2,l)‐configuration for 4≤l≤r. The existence problem for anti‐Pasch Steiner triple systems has been solved, but these have been classified only up to order 19. In the current work, a computer‐aided classification shows that there are 83,003,869 isomorphism classes of anti‐Pasch STS(21)s. Exploration of the classified systems reveals that there are three 5‐sparse STS(21)s but no 6‐sparse STS(21)s. The anti‐Pasch STS(21)s lead to 14 Kirkman triple systems, none of which is doubly resolvable. [ABSTRACT FROM AUTHOR]

An oriented tetrahedron defined on four vertices is a set of four cyclic triples with the property that any ordered pair of vertices is contained in exactly one of the cyclic triples. A tetrahedral quadruple system of order n with index λ, denoted by TQSλ(n), is a pair (X,ℬ), where X is an n‐set and ℬ is a set of oriented tetrahedra (blocks) such that every cyclic triple on X is contained in exactly λ members of ℬ. A TQSλ(n) is pure if there do not exist two blocks with the same vertex set. When λ=1, the spectrum of a pure TQS(n) has been completely determined by Ji. In this paper, we show that there exists a pure TQS2(n) if and only if n≡1,2(mod 3) and n≥7. A corollary is that a simple QS4(n) also exists if and only if n≡1,2(mod 3) and n≥7. [ABSTRACT FROM AUTHOR]

We show that for any n divisible by 3, almost all order-n Steiner triple systems have a perfect matching (also known as a parallel class or resolution class). In fact, we prove a general upper bound on the number of perfect matchings in a Steiner triple system and show that almost all Steiner triple systems essentially attain this maximum. We accomplish this via a general theorem comparing a uniformly random Steiner triple system to the outcome of the triangle removal process, which we hope will be useful for other problems. Our methods can also be adapted to other types of designs; for example, we sketch a proof of the theorem that almost all Latin squares have transversals. [ABSTRACT FROM AUTHOR]

The maximum independence number of Steiner triple systems of order v is well‐known. Motivated by questions of access balancing in storage systems, we determine the maximum total cardinality of a pair of disjoint independent sets of Steiner triple systems of order v for all admissible orders. [ABSTRACT FROM AUTHOR]

A pair of orthogonal latin cubes of order q is equivalent to a maximum distance separable code with distance 3 or to an OA1(3,5,q) orthogonal array. We construct pairs of orthogonal latin cubes for sequences of previously unknown orders qi=16(18i−1)+4 and qi′=16(18i+5)+4. The minimal new obtained parameters of orthogonal arrays are OA1(3,5,84). [ABSTRACT FROM AUTHOR]

A partial Steiner triple system of order u is a pair (U,A), where U is a set of u elements and A is a set of triples of elements of U such that any two elements of U occur together in at most one triple. If each pair of elements occur together in exactly one triple it is a Steiner triple system. An embedding of a partial Steiner triple system (U,A) is a (complete) Steiner triple system (V,B) such that U⊆V and A⊆B. For a given partial Steiner triple system of order u it is known that an embedding of order v⩾2u+1 exists whenever v satisfies the obvious necessary conditions. Determining whether "small" embeddings of order v<2u+1 exist is a more difficult task. Here we extend a result of Colbourn on the NP‐completeness of these problems. We also exhibit a family of counterexamples to a conjecture concerning when small embeddings exist. [ABSTRACT FROM AUTHOR]

Let D(n) be the number of pairwise disjoint Steiner quadruple systems (SQS) of order n. A simple counting argument shows that D(n)≤n−3 and a set of n−3 such systems is called a large set. No nontrivial large set was constructed yet, although it is known that they exist if n≡2 or 4(mod6) is large enough. When n≥7 and n≡1 or 5(mod6), we present a recursive construction and prove a recursive formula on D(4n), as follows: D(4n)≥2n+min{D(2n),2n−7}. The related construction has a few advantages over some of the previously known constructions for pairwise disjoint SQSs. [ABSTRACT FROM AUTHOR]

It is known that in any r‐coloring of the edges of a complete r‐uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on n vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3‐coloring of the edges? Gyárfás proved that (2n+3)/3 is an absolute lower bound and that this lower bound is best possible for infinitely many n. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually (1−o(1))n. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest 3‐partite hole (ie, disjoint sets X1,X2,X3 with |X1|=|X2|=|X3| such that no edge intersects all of X1,X2,X3) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the structure of the Steiner triple system and the coloring of its edges are restricted in a certain way. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems. [ABSTRACT FROM AUTHOR]

A partial Steiner triple system of order n is sequenceable if there is a sequence of length n of its distinct points such that no proper segment of the sequence is a union of point‐disjoint blocks. We prove that if a partial Steiner triple system has at most three point‐disjoint blocks, then it is sequenceable. [ABSTRACT FROM AUTHOR]

In 1977, D. Betten defined a geometric group to be a permutation group (G,Ω) such that G=Aut(R) for some hypergraph R on Ω. In this paper, we extend Betten's notion of a geometric group to what we call a geometric group of second order. By definition, this is a permutation group for which G=Aut(R) for some set R={R1,R2,...,Rd} of hypergraphs on Ω. Our main focus will be on permutation groups that are geometric of second order but not geometric. Within this small class of groups one finds the projective groups PGL(2,8),PΓL(2,8) and the affine groups AGL(1,8),AΓL(1,8). Our investigations, which are based primarily on these four groups, lead us to consider some familiar combinatorial structures (eg, Fano plane and affine design) in a less familiar context (overlarge sets of Steiner systems). [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 Ap,rm(n) be the best constant that fulfills the following inequality: for every m‐homogeneous polynomial P(z)=∑|α|=maαzα in n complex variables, ∑|α|=m|aα|r1/r≤Ap,rm(n)supz∈Bℓpn|P(z)|.For every degree m, and a wide range of values of p,r∈[1,∞] (including any r in the case p∈[1,2], and any r and p for the 2‐homogeneous case), we give the correct asymptotic behavior of these constants as n (the number of variables) tends to infinity. Remarkably, in many cases, extremal polynomials for these inequalities are not (as traditionally expected) found using classical random unimodular polynomials, and special combinatorial configurations of monomials are needed. Namely, we show that Steiner polynomials (i.e., m‐homogeneous polynomials such that the multi‐indices corresponding to the nonzero coefficients form partial Steiner systems), do the work for certain range of values of p,r. As a byproduct, we present some applications of these estimates to the interpolation of tensor products of Banach spaces, to the study of (mixed) unconditionality in spaces of polynomials and to the multivariable von Neumann's inequality. [ABSTRACT FROM AUTHOR]

In 1973, Erdős asked whether there are n‐vertex partial Steiner triple systems with arbitrary high girth and quadratically many triples. (Here girth is defined as the smallest integer g⩾4 for which some g‐element vertex‐set contains at least g−2 triples.) We answer this question, by showing existence of approximate Steiner triple systems with arbitrary high girth. More concretely, for any fixed ℓ⩾4, we show that a natural constrained random process typically produces a partial Steiner triple system with (1/6−o(1))n2 triples and girth larger than ℓ. The process iteratively adds random triples subject to the constraint that the girth remains larger than ℓ. Our result is best possible up to the o(1)‐term, which is a negative power of n. [ABSTRACT FROM AUTHOR]

The p‐rank of a Steiner triple system (STS) B is the dimension of the linear span of the set of characteristic vectors of blocks of B, over GF(p). We derive a formula for the number of different STSs of order v and given 2‐rank r2, r2

It is shown that for v≠6,7,10,11,12,13, there exists an optimal packing with triples on v points that contains no Pasch configurations. Furthermore, for all v≡5 (mod 6), there exists a pairwise balanced design of order v, whose blocks are all triples apart from a single quintuple, and that has no Pasch configurations amongst its triples. [ABSTRACT FROM AUTHOR]

To every Steiner system with parameters (t,k,v) on {1,...,v} and blocks B, we can assign its characteristic vector χB, which is a (0,1)‐vector whose entries are indexed by the k‐subsets of {1,...,v} such that for each k‐subset A of {1,...,v},χB(A)=1 if and only if A∈B. In this paper, we show that the dimension of the vector space generated by all of the characteristic vectors of Steiner systems with parameters (t,k,v) is (vk)−(vt)+1, provided that 1≤t≤k≤v/2 and there is at least one such system. [ABSTRACT FROM AUTHOR]

We show that the maximum number of triples on n points, if no three triples span at most five points, is (1±o(1))n2/5. More generally, let f(r)(n;k,s) be the maximum number of edges in an r‐uniform hypergraph on n vertices not containing a subgraph with k vertices and s edges. In 1973, Brown, Erdős and Sós conjectured that the limit limn→∞n−2f(3)(n;k,k−2) exists for all k. They proved this for k=4, where the limit is 1/6 and the extremal examples are Steiner triple systems. We prove the conjecture for k=5 and show that the limit is 1/5. The upper bound is established via a simple optimisation problem. For the lower bound, we use approximate H‐decompositions of Kn for a suitably defined graph H. [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]

An H(m,g,k,3) design is a triple (X,T,B), where X is a set of mg points, T a partition of X into m disjoint sets of size g, and B a set of k‐element transverses of T, such that each 3‐element transverse of T is contained in exactly one of them. In 1990, Mills determined the existence of an H(m,g,4,3) design with m≠5. In this paper, an efficient construction shows that an H(5,g,4,3) exists for any integer g≡2,10(mod12) with g≥10. Consequently, the necessary and sufficient conditions for the existence of an H(m,g,4,3) design are m≥4, mg≡0(mod2), and g(m−1)(m−2)(mod3), with a definite exception (m,g)=(5,2). [ABSTRACT FROM AUTHOR]

Abstract: Given a combinatorial design D with block set B, the block‐intersection graph (BIG) of D is the graph that has B as its vertex set, where two vertices B 1 ∈ B and B 2 ∈ B are adjacent if and only if | B 1 ∩ B 2 | > 0. The i‐block‐intersection graph (i‐BIG) of D is the graph that has B as its vertex set, where two vertices B 1 ∈ B and B 2 ∈ B are adjacent if and only if | B 1 ∩ B 2 | = i. In this paper, several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian 2‐BIGs and result in larger TTSs that also have Hamiltonian 2‐BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian 2‐BIGs (equivalently TTSs with cyclic 2‐intersecting Gray codes) as well as the complete spectrum for TTSs with 2‐BIGs that have Hamilton paths (i.e. for TTSs with 2‐intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel classes in arbitrary TTSs, and then construct larger TTSs with both cyclic 2‐intersecting Gray codes and parallel classes. [ABSTRACT FROM AUTHOR]

Abstract: Steiner systems are a fascinating topic of combinatorics. The most studied Steiner systems are S ( 2 , 3 , v ) (Steiner triple systems), S ( 3 , 4 , v ) (Steiner quadruple systems), and S ( 2 , 4 , v ). There are a few infinite families of Steiner systems S ( 2 , 4 , v ) in the literature. The objective of this paper is to present an infinite family of Steiner systems S ( 2 , 4 , 2 m ) for all m ≡ 2 ( mod 4 ) ≥ 6 from cyclic codes. As a by‐product, many infinite families of 2‐designs are also reported in this paper. [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]

In this article, it is shown that there is a partitioning of the set of 3-arcs in a projective plane of order three into nine pairwise disjoint Steiner triple systems of order 13. [ABSTRACT FROM AUTHOR]

An Euler tour of a hypergraph (also called a rank-2 universal cycle or 1-overlap cycle in the context of designs) is a closed walk that traverses every edge exactly once. In this paper, using a graph-theoretic approach, we prove that every triple system with at least two triples is eulerian, that is, it admits an Euler tour. Horan and Hurlbert have previously shown that for every admissible order >3, there exists a Steiner triple system with an Euler tour, while Dewar and Stevens have proved that every cyclic Steiner triple system of order >3 and every cyclic twofold triple system admits an Euler tour. [ABSTRACT FROM AUTHOR]

The problem of classifying cyclic Steiner quadruple systems (CSQSs) is considered. A computational approach shows that the number of isomorphism classes of such designs with orders 26 and 28 is 52,170 and 1,028,387, respectively. It is further shown that CSQSs of order 2 p, where p is a prime, are isomorphic iff they are multiplier equivalent. Moreover, no CSQSs of order less than or equal to 38 are isomorphic but not multiplier equivalent. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

A triple system is a collection of b blocks, each of size three, on a set of v points. It is j-balanced when every two j -sets of points appear in numbers of blocks that are as nearly equal as possible, and well balanced when it is j-balanced for each j ∈ {1, 2, 3}.Well-balanced systems arise in the minimization of variance in file availability in distributed file systems. It is shown that when a triple system that is 2-balanced and 3-balanced exists, so does one that is well balanced. Using known and new results on variants of group divisible designs, constructions for well-balanced triple systems are developed. Using these, the spectrum of pairs (v, b) for which such a well-balanced triple system exists is determined completely. [ABSTRACT FROM AUTHOR]

The problem we consider in this article ismotivated by data placement, in particular data replication in distributed storage and retrieval systems. We are given a set V of v servers along with b files (data, documents). Each file is replicated on exactly k servers. A placement consists in finding a family of b subsets of V (representing the files) called blocks, each of size k. Each server has some probability to fail and we want to find a placement that minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well-balanced design--that is, a family of blocks--each of size k, such that each j-element subset of V, 1 ≤ j ≤ k, belongs to the same or almost the same number of blocks (difference at most one). The existence of well-balanced designs is a difficult problem as it contains, as a subproblem, the existence of Steiner systems. We completely solve the case k = 2 and give bounds and constructions for k = 3 and some values of v and b. [ABSTRACT FROM AUTHOR]

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