Search

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]

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]

Let Σ = (X, B) be a 6-cycle system of order v, so v = 1, 9 mod 12. A c-colouring of type s is a map φ B → C, with C set of colours, such that exactly c colours are used and for every vertex x all the blocks containing x are coloured exactly with s colours. Let v-1/2 = qs + r, with q, r ≥ 0. φ is equitable if for every vertex x the set of the v-1/2 blocks containing x is partitioned in r colour classes of cardinality q + 1 and s - r colour classes of cardinality q. In this paper we study bicolourings and tricolourings, for which, respectively, s = 2 and s = 3, distinguishing the cases v = 12k+1 and v = 12k+9. In particular, we settle completely the case of s = 2, while for s = 3 we determine upper and lower bounds for c. [ABSTRACT FROM AUTHOR]

The existence of Large sets of Kirkman Triple Systems (LKTS) is an old problem in combinatorics. Known results are very limited, and a lot of them are based on the works of Denniston (1974, 1979) [2,3,5,4]. The only known recursive constructions are a tripling construction by Denniston (1979) [5] and a product construction by Lei (2002). Both construct an LKTS( u v ) on the basis of an LKTS( v ). In this paper, we describe a construction of LKTS ( q n + 2 ) from LKTS ( q + 2 ) , where q is a prime power of the form 6 t + 1 . We could construct previous unknown LKTS( v ) by this result, the smallest among them have v = 171 , 345 , 363 . [ABSTRACT FROM AUTHOR]

This article investigates the robustness of binary incomplete block designs against giving rise to a disconnected design in the event of observation loss. A link is established between theE-value of a planned design and the extent of observation loss that can be experienced while still guaranteeing an eventual design from which all treatment contrasts can be estimated. Patterns of missing observations covered include loss of entire blocks and loss of individual observations. Simple bounds are provided enabling practitioners to easily assess the robustness of a planned design. [ABSTRACT FROM AUTHOR]

We consider the problem of embedding the Steiner points of a Steiner tree with a given topology into the rectilinear plane. Thereby, the length of the path between a distinguished terminal and each other terminal must not exceed given length restrictions. The task is to find an embedding minimizing the total length of the tree. We show that the problem can be formulated as simple linear programming. Moreover, we analyze the structure of feasible embeddings and give a combinatorial polynomial time algorithm for the problem. Our algorithm combines a dynamic programming approach and binary search and relies on the total unimodularity of a matrix appearing in a sub-problem. 1 [ABSTRACT FROM AUTHOR]

Given a seven-element set X = {1, 2, 3, 4, 5, 6, 7}, there are 30 ways to define a Fano plane on it. Let us call a line of such a Fano plane--that is to say an unordered triple from X--ordinary or defective, according to whether the sum of two smaller integers from the triple is or is not equal to the remaining one, respectively. A point of the labeled Fano plane is said to be of the order s, 0 ≤ s ≤ 3, if there are s defective lines passing through it. With such structural refinement in mind, the 30 Fano planes are shown to fall into eight distinct types. Out of the total of 35 lines, nine ordinary lines are of five different kinds, whereas the remaining 26 defective lines yield as many as ten distinct types. It is shown that no labeled Fano plane can have all points of zero-th order, or feature just one point of order two. A connection with prominent configurations in Steiner triple systems is also pointed out. [ABSTRACT FROM AUTHOR]

Let 픽qn be a vector space of dimension n over the finite field ---q. A q-analog of a Steiner system (also known as a q-Steiner system), denoted Sq (t, k, n), is a set S of k-dimensional subspaces of ---qn such that each t-dimensional subspace of ---qn is contained in exactly one element of S. Presently, q-Steiner systems are known only for t = 1, and in the trivial cases t = k and k = n. In this paper, the first nontrivial q-Steiner systems with t ≥ 2 are constructed. Specifically, several nonisomorphic q-Steiner systems S2 (2, 3, 13) are found by requiring that their automorphism groups contain the normalizer of a Singer subgroup of GL(13, 2). This approach leads to an instance of the exact cover problem, which turns out to have many solutions. [ABSTRACT FROM AUTHOR]

Necessary conditions for existence of a resolvable group divisible design (GDD) with block size 3 and type [ABSTRACT FROM AUTHOR]

Abstract: A Steiner quadruple system is said to be -resolvable if its blocks can be partitioned into parts such that each point of occurs in exactly two blocks in each part. The necessary condition for the existence of -resolvable Steiner quadruple systems s is or 10 (mod 12). Hartman and Phelps in [A. Hartman, K.T. Phelps, Steiner quadruple systems, in: J.H. Dinitz, D.R. Stinson (Eds.), Contemporary Design Theory, Wiley, New York, 1992, pp. 205–240] posed a question whether the necessary condition for the existence of -resolvable Steiner quadruple systems is sufficient. In this paper, we consider the last twenty orders of -resolvable Steiner quadruple systems and show that the necessary condition for the existence of -resolvable Steiner quadruple systems is also sufficient except for the order 10. [Copyright &y& Elsevier]

Abstract: -resolvable candelabra quadruple systems play an important role in the construction of -resolvable Steiner quadruple systems. In this paper, we consider -resolvable candelabra quadruple systems with three groups and show that the necessary conditions on the existence of -RCQS when is even are also sufficient. As its application, we improve the existing result on -resolvable Steiner quadruple systems. [Copyright &y& Elsevier]

Let X be a v-set [ABSTRACT FROM AUTHOR]

A Skolem-type sequence is a sequence ( s, . . . , s) of positive integers $${i\in D}$$ such that for each $${i\in D}$$ there is exactly one $${j\in \{1, \ldots , t - i\}}$$ such that s = s = i. Positions in the sequence not occupied by integers $${i\in D}$$ contain null elements. In 1939, Peltesohn solved the existence problem for cyclic Steiner triple systems for v ≡ 1, 3(mod 6), v ≠ 9. Using the same technique in 1981, Colbourn and Colbourn extended the solution to all admissible λ > 1. It is known that Skolem-type sequences may be used to construct cyclic Steiner triple systems as well as cyclic triple systems with λ = 2. The main result of this paper is an extension of former results to cyclic triple systems with λ > 2. In addition we introduce a new kind of Skolem-type sequence. [ABSTRACT FROM AUTHOR]

Abstract: It is well known that, given a Steiner triple system, a quasigroup can be formed by defining an operation by the identities and , where is the third point in the block containing the pair . The same is true for a Mendelsohn triple system, where the pair is considered to be ordered. But it is not true in general for directed triple systems. However, directed triple systems which form quasigroups under this operation do exist. We call these Latin directed triple systems, and in this paper we begin the study of their existence and properties. [Copyright &y& Elsevier]

Abstract: A two-fold pentagon system is a decomposition of the complete 2-multigraph (every two distinct vertices joined by two edges) into pentagons. A two-fold Steiner pentagon system is a two-fold pentagon system such that every pair of distinct vertices is joined by a path of length two in exactly two pentagons of the system. We consider two-fold Steiner pentagon systems with an additional property : for any two vertices, the two paths of length two joining them are distinct. We determine completely the spectrum for such systems, and point out an application of such systems to certain 4-cycle systems. [Copyright &y& Elsevier]

Pairwise disjoint 3-GDDs can be used to construct some optimal constant-weight codes. We study the existence of a pair of disjoint 3-GDDs of type g u and establish that its necessary conditions are also sufficient. [ABSTRACT FROM AUTHOR]

Abstract: A Hanani triple system of order , , is a decomposition of the complete graph into sets of disjoint triangles and one set of disjoint triangles. A nearly Kirkman triple system of order , , is a decomposition of into sets of disjoint triangles; here is a one-factor of . The Hanani triple systems of order and the nearly Kirkman triple systems of order can be classified using the classification of the Steiner triple systems of order . This is carried out here for : There are 3787983639 isomorphism classes of s and 25328 isomorphism classes of s. Several properties of the classified systems are tabulated. In particular, seven of the s have orthogonal resolutions, and five of the s admit a pair of resolutions in which the almost parallel classes are orthogonal. [Copyright &y& Elsevier]

Cameron and Kazanidis have recently shown that rank-three graphs are either cores or have complete cores, and they asked whether this holds for all strongly regular graphs. We prove that this is true for the point graphs and line graphs of generalized quadrangles and that when the number of points is sufficiently large, it is also true for the block graphs of Steiner systems and orthogonal arrays. [ABSTRACT FROM AUTHOR]

We consider the existence problem for 'Steiner networks' (trivalent graphs with 2 π/3 angles at each junction) in strictly convex domains, with 'Neumann' boundary conditions. For each of the three possible combinatorial possibilities, sufficient conditions on the domain are derived for existence. In addition, in each case explicit examples of nonexistence are given. [ABSTRACT FROM AUTHOR]

We propose several problems on the Fibonacci polytope. [ABSTRACT FROM AUTHOR]

Abstract: We give a construction of a 2- design starting from a Steiner system and an affine plane of order n. This construction is applied to known classes of Steiner systems arising from affine and projective geometries, Denniston designs, and unitals. We also consider the extendability of these designs to 3-designs. [ABSTRACT FROM AUTHOR]

Abstract: An augmented Steiner quadruple system of order is an ordered triple , where is an SQS and is the set of all 2-subsets of . An augmented Steiner quadruple system of order is resolvable if can be partitioned into parts such that each part is a partition of . Hartman and Phelps in [A. Hartman, K.T. Phelps, Steiner quadruple systems, in: J.H. Dinitz, D.R. Stinson (Eds.), Contemporary Design Theory, Wiley, New York, 1992, pp. 205–240] conjectured that there exists a resolvable augmented Steiner quadruple systems of order for any positive integer or 10 (mod 12). In this paper, we show that the Hartman and Phelps conjecture is true. [Copyright &y& Elsevier]

The aim of this article is to answer a question posed by Merris in European Journal of Combinatorics, 24 (2003) pp. 413 - 430, about the possibility of finding split non-threshold graphs that are Laplacian integral, i.e. graphs for which the eigenvalues of the corresponding Laplacian matrix are integers. Using Kronecker products, balanced incomplete block designs, and solutions to certain Diophantine equations, we show how to build infinite families of these graphs. [ABSTRACT FROM AUTHOR]

Abstract: We show that for every admissible order or there exists a near-Steiner triple system of order that can be halved. As a corollary we obtain that a Steiner almost self-complementary graph with vertices exists if and only if or . [Copyright &y& Elsevier]

Motivated by applications in combinatorial group testing for consecutive positives, we investigate a block sequence of a maximum packing MP(t, k, v) which contains the blocks exactly once such that the collection of all blocks together with all unions of two consecutive blocks of this sequence forms an error correcting code with minimum distance d. Such a sequence is usually called a block sequence with consecutive unions having minimum distance d, and denoted by BSCU(t, k, v∣d). In this paper, we show that the necessary conditions for the existence of BSCU(3, 4, v∣4)s of Steiner quadruple systems, namely, v Ξ 2,4 (mod 6) and v ≥ 4, are also sufficient, excepting v = 8, 10. [ABSTRACT FROM AUTHOR]

The number of efficient points in criteria space of multiple objective combinatorial optimization problems is considered in this paper. It is concluded that under certain assumptions, that number grows polynomially although the number of Pareto optimal solutions grows exponentially with the problem size. In order to perform experiments, an original algorithm for obtaining all efficient points was formulated and implemented for three classical multiobjective combinatorial optimization problems. Experimental results with the shortest path problem, the Steiner tree problem on graphs and the traveling salesman problem show that the number of efficient points is much lower than a polynomial upper bound. [ABSTRACT FROM AUTHOR]

Abstract: A -design on points embeds a Steiner triple system (STS) if there is a subset of points on which the graphs of the design induce the blocks of a STS. It is established that , and that when equality is met that such a minimum embedding of an exists, except when . [Copyright &y& Elsevier]

We continue the study of specialized block-colourings of Steiner triple systems initiated in [2] in which the triples through any element are coloured according to a given partition π of the replication number. Such colourings are equitable if π is an equitable partition (i.e., the difference between any two parts of π is at most one). Our main results deal with colourings according to equitable partitions into two, and three parts, respectively. [ABSTRACT FROM AUTHOR]

Abstract: A Steiner pentagon system of order is said to be super-simple if its underlying -BIBD is super-simple; that is, any two blocks of the BIBD intersect in at most two points. In this paper, it is shown that the necessary condition for the existence of a super-simple ; namely, and or is sufficient, except for , and possibly for . In the process, we also improve an earlier result for the spectrum of super-simple -BIBDs, removing all the possible exceptions. We also give some new examples of Steiner pentagon packing and covering designs (SPPDs and SPCDs). [Copyright &y& Elsevier]

Let $$K_{1(3)} = \{k : k \equiv 1 ({\rm mod}\,3)\}$$ . For w ∈ K 1(3), a $$(v, K_{1(3)} \cup \{w^*\})$$ -PBD is a pairwise balanced design on v points with block size from the set K 1(3) in which there is at least one block of size w. In this paper, we investigate the existence problem for (v, K 1(3) ∪ {w *})-PBDs and give a complete solution to this problem. As its applications, we solve completely the embedding problem for directed designs DB(4,1;u)s. In addition, we also apply our (v, K 1(3) ∪ {w *})-PBDs to do embeddings for near resolvable triple systems and nested Steiner triple systems and give unified and simple new proofs of two known theorems. Some new 4-GDDs are constructed as well. [ABSTRACT FROM AUTHOR]

Recently, Franek et al. introduced large sets of v − 1 L-intersecting Steiner triple systems of order v (STS(v)) and gave four constructions for them (Des., Codes and Cryptogr., 26 (2002), 243–256). In this paper, we mainly focus on large sets of v − 1{0, 1}-intersecting STS(v) and large sets of v + 1{1}-intersecting STS(v). For this purpose, we introduce a concept of L-intersecting partitionable candelabra system (L-PCS) of order v with q(v) subsystems and establish a relationship between L-PCS and large set of q(v)L-intersecting STS(v). Some constructions for L-PCSs are also presented by 3-wise balanced designs. These facilitate the production of some new infinite classes of these large sets. [ABSTRACT FROM AUTHOR]

Abstract: It is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration C 14. We find three configurations such that a Steiner triple system is affine if and only if it does not contain any of these configurations. Similarly, we characterize Hall triple systems, a superclass of affine Steiner triple systems, using two forbidden configurations. [Copyright &y& Elsevier]

Abstract: A Steiner 2-design is said to be halvable if the block set can be partitioned into two isomorphic sets. This is equivalent to an edge-disjoint decomposition of a self-complementary graph G on vertices into . The obvious necessary condition of those orders for which there exists a halvable is that admits the existence of an with an even number of blocks. In this paper, we give an asymptotic solution for various block sizes. We prove that for any or any Mersenne prime k, there is a constant number such that if and satisfies the above necessary condition, then there exists a halvable . We also show that a halvable exists for over a half of possible orders. Some recursive constructions generating infinitely many new halvable Steiner 2-designs are also presented. [Copyright &y& Elsevier]

Let C be a d-semi-distance code of length n and N the cardinality of C. In this paper we obtain an upper bound on N: $$N \le { n \choose k_0-d+1 } / { k_0 \choose k_0-d+1 }$$ , where k 0 = ⌊ ( n + d − 1)/2 ⌋. When a code C attains the upper bound and n + d − 1 is even, C corresponds to a Steiner system S( k 0 − d + 1, k 0, n) in a natural way. Let S be a Steiner system S( t, k, n) with k + t − 1 ≤ n ≤ k + t + 1 (1 ≤ t ≤ k < n). Then S corresponds to an optimal ( k − t + 1)-semi-distance code of length n in a natural way. [ABSTRACT FROM AUTHOR]

Abstract: Given a Steiner triple system , we say that a cubic graph G is -colourable if its edges can be coloured by points of in such way that the colours of any three edges incident with the same vertex form a triple of . We prove that there is Steiner triple system of order 21 which is universal in the sense that every simple cubic graph is -colourable. This improves the result of Grannell et al. [J. Graph Theory 46 (2004), 15–24] who found a similar system of order 381. On the other hand, it is known that any universal Steiner triple system must have order at least 13, and it has been conjectured that this bound is sharp (Holroyd and Škoviera [J. Combin. Theory Ser. B 91 (2004), 57–66]). [Copyright &y& Elsevier]

Abstract: We give the first known examples of 6-sparse Steiner triple systems by constructing 29 such systems in the residue class 7 modulo 12, with orders ranging from 139 to 4447. We then present a recursive construction which establishes the existence of 6-sparse systems for an infinite set of orders. Observations are also made concerning existing construction methods for perfect Steiner triple systems, and we give a further example of such a system. This has order 135,859 and is only the fourteenth known. Finally, we present a uniform Steiner triple system of order 180,907. [Copyright &y& Elsevier]

Recently, the added-hyperplane (AHP) bound was proposed on the foundation of the tangential sphere bound (TSB) of Poltyrev. AHP utilises a Bonferroni-type inequality (known as the Hunter bound) together with the Gallager first bounding technique (GFBT) and is tighter than TSB; however, it suffers from a performance-degrading overhead. Another inequality from the Hunter-bound family is applied to the GFBT and a novel technique has been proposed to waive the need for global geometrical properties of the code, removing the aforementioned overhead. Also, a star-structured graph is proposed as the corresponding spanning tree for the Hunter bound. The improved tangential sphere bound (ITSB) is tighter than TSB and AHP and does not impose any overhead or extra optimisation. ITSB is thus the tightest upper bound on the performance of linear binary block codes over AWGN channel. ITSB is then applied to different block (slow) fading channels as well as low-density parity-check codes. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we investigate the k-path cover problem for graphs, which is to find the minimum number of vertex disjoint k-paths that cover all the vertices of a graph. The k-path cover problem for general graphs is NP-complete. Though notable applications of this problem to database design, network, VLSI design, ring protocols, and code optimization, efficient algorithms are known for only few special classes of graphs. In order to solve this problem for cacti, i.e., graphs where no edge lies on more than one cycle, we introduce the so-called Steiner version of the k-path cover problem, and develop an efficient algorithm for the Steiner k-path cover problem for cacti, which finds an optimal k-path cover for a given cactus in polynomial time. [Copyright &y& Elsevier]

A Steiner quadruple system of order v, denoted by SQS(v), is a pair $(X,{\cal B}),$ where X is a v-set of points and ${\cal B}$ is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in exactly one block of ${\cal B}$. An SQS(v) is resolvable if its block set can be partitioned into parallel classes. In 1987, Hartman showed that the necessary condition $v\equiv 4$ or $8\ (\rm {mod}\ 12)$ for the existence of a resolvable SQS(v) is sufficient with 23 possible exceptions. In this paper, we construct resolvable SQS(v)s for the 23 undecided orders. [ABSTRACT FROM AUTHOR]

Abstract: A Steiner triple system of order (briefly STS) consists of a -element set X and a collection of 3-element subsets of X, called blocks, such that every pair of distinct points in X is contained in a unique block. A large set of disjoint STS (briefly LSTS) is a partition of all 3-subsets (triples) of X into STS. In 1983–1984, Lu Jiaxi first proved that there exists an LSTS for any or with six possible exceptions and a definite exception . In 1989, Teirlinck solved the existence of LSTS for the remaining six orders. Since their proof is very complicated, it is much desired to find a simple proof. For this purpose, we give a new proof which is mainly based on the 3-wise balanced designs and partitionable candelabra systems. [Copyright &y& Elsevier]

Abstract: We discuss some properties of yet another class of graphs whose smallest member is the Petersen graph. These graphs, which we call extended Petersen graphs, arise naturally in the context of a construction of Steiner systems with maximal arcs but seem to be interesting on their own. [Copyright &y& Elsevier]

Abstract: It is well known that a Steiner triple system (STS) on points, an , can be seen as a collection of 3-subsets of its point set, called triples, such that each pair of points occurs in exactly one triple as well as a decomposition of a complete graph on vertices into cycles of length 3. By combining those two views on STSs we develop a method for its weak coloring. This method enables us to show that each is 4-colorable, which in turn implies that the chromatic spectrum of is [Copyright &y& Elsevier]

We show by counterexample that one of the main results in the paper “The Steiner number of a graph” by Chartrand and Zhang (Disc. Math. 242 (2002) 41–54) does not hold. To be more precise, we prove both that not every Steiner set is a geodetic set and that there are connected graphs whose Steiner number is strictly lower than its geodetic number. [Copyright &y& Elsevier]

We initiate a systematic study of embeddings of Steiner triple systems into Steiner systems S(2,4,v). We settle the existence of an embedding of the unique STS(7) and, with one possible exception, of the unique STS(9) into S(2,4,v). We also obtain bounds for embedding sizes of Steiner triple systems of larger orders. [Copyright &y& Elsevier]

A minimal defining set of a Steiner triple system on v points (STS(v)) is a partial Steiner triple system contained in only this STS(v), and such that any of its proper subsets is contained in at least two distinct STS(v)s. We consider the standard doubling and tripling constructions for STS(2v+1) and STS(3v) from STS(v) and show how minimal defining sets of an STS(v) gives rise to minimal defining sets in the larger systems. We use this to construct some new families of defining sets. For example, for Steiner triple systems on 3n points, we construct minimal defining sets of volumes varying by as much as 7n-2. [ABSTRACT FROM AUTHOR]

There are 80 non-isomorphic Steiner triple systems of order 15. A standard listing of these is given in Mathon et al.(1983, Ars Combin., 15, 3–110). We prove that systems #1 and #2 have no bi-embedding together in an orientable surface. This is the first known example of a pair of Steiner triple systems of ordern , satisfying the admissibility condition n ≡ 3 or 7(mod 12), which admits no orientable bi-embedding. We also show that the same pair has five non-isomorphic bi-embeddings in a non-orientable surface. [Copyright &y& Elsevier]

A full Steiner tree T for a given set of points P is defined to be linear if all Steiner points lie on one path called the trunk of T. A (nonfull) Steiner tree is linear if it is a degeneracy of a full linear Steiner tree. Suppose P is a simple polygonal line. Roughly speaking, T is similar to P if its trunk turns to the left or right when P does. P is a left-turn (or right-turn) polygonal spiral if it always turns to the left (or right) at its vertices. P is an infinite spiral if n tends to infinity. In this paper we first prove some results on nonminimal paths and the decomposition of Steiner minimal trees, and then, based on these results, we study the case in which an infinite spiral P has a Steiner minimal tree that is linear and similar to P itself. [ABSTRACT FROM AUTHOR]