Search

A 3-way (v , k , t) trade T of volume m consists of three pairwise disjoint collections T 1 , T 2 and T 3 , each of m blocks of size k , such that for every t -subset of v -set V , the number of blocks containing this t -subset is the same in each T i for 1 ≤ i ≤ 3 . If any t -subset of found(T ) occurs at most once in each T i for 1 ≤ i ≤ 3 , then T is called 3-way (v , k , t) Steiner trade. We attempt to complete the spectrum S 3 s (v , k) , the set of all possible volume sizes, for 3-way (v , k , 2) Steiner trades, by applying some block designs, such as BIBDs, RBs, GDDs, RGDDs, and r × s packing grid blocks. Previously, we obtained some results about the existence some 3-way (v , k , 2) Steiner trades. In particular, we proved that there exists a 3-way (v , k , 2) Steiner trade of volume m when 12 (k − 1) ≤ m for 15 ≤ k (Rashidi and Soltankhah in Discrete Math. 339(12): 2955–2963, 2016). Now, we show that the claim is correct also for k ≤ 14 . [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]

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]

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]

A graph is n-existentially closed (n-e.c.) if for any disjoint subsets A, B of vertices with A ∪ B = n , there is a vertex z ∉ A ∪ B adjacent to every vertex of A and no vertex of B. For a block design with block set B , its block intersection graph is the graph whose vertex set is B and two vertices (blocks) are adjacent if they have non-empty intersection. In this paper, we investigate the block intersection graphs of pairwise balanced designs, and propose a sufficient condition for such graphs to be 2-e.c. In particular, we study the λ -fold triple systems with λ ≥ 2 and determine for which parameters their block intersection graphs are 1- or 2-e.c. Moreover, for Steiner quadruple systems, the block intersection graphs and their analogue called { 1 } -block intersection graphs are investigated, and the necessary and sufficient conditions for such graphs to be 2-e.c. are established. [ABSTRACT FROM AUTHOR]

Let v ≡ 4 (mod 6) and v ≥ 4 . A canonical Kirkman packing design of order v, denoted by CKPD (v) , is a resolvable packing with r = (v - 4) / 2 parallel classes such that (i) each parallel class consists of a size 4 block and (v - 4) / 3 triples; (ii) the leave consists of the union of (v - 4) / 2 vertex-disjoint edges and a K 4 with no vertices in common with those edges. A canonical Kirkman packing design is said to be doubly resolvable if there exist a pair of orthogonal resolutions. A doubly resolvable packing design is the generalization of the Kirkman square, which is inextricably bound up with the existence of some constant weight codes such as constant composition codes and permutation codes, etc. In this paper, we establish the spectra of doubly resolvable CKPD (v) s with 36 possible exceptions for v. As its direct application, a class of permutation codes are obtained. [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]

A μ-way (v, k, t) trade is a pair T=(X,{T1,T2,...,Tμ}) such that for eacht-subset of v-set X the number of blocks containing this t-subset is the same in each Ti(1≤i≤μ). In the other words for each 1≤i

We introduce m-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) q-ary constant-weight codes meeting the Johnson bound. We present constructions of m-near-resolvable block designs, in particular based on Steiner systems and super-simple t-designs. [ABSTRACT FROM AUTHOR]

The unique Steiner triple system of order 7 has a point-block incidence graph known as the Heawood graph. Motivated by questions in combinatorial matrix theory, we consider the problem of constructing a faithful orthogonal representation of this graph, i.e., an assignment of a vector in C d to each vertex such that two vertices are adjacent precisely when assigned nonorthogonal vectors. We show that d = 10 is the smallest number of dimensions in which such a representation exists, a value known as the minimum semidefinite rank of the graph, and give such a representation in 10 real dimensions. We then show how the same approach gives a lower bound on this parameter for the incidence graph of any Steiner triple system, and highlight some questions concerning the general upper bound. [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]

In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by $$|T|+k$$ , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals | T| is at most cubic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs. [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]

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]

Ordering the blocks of a design, the point sum of an element is the sum of the indices of blocks containing that element. Block labelling for popularity asks for the point sums to be as equal as possible. When all point sums are equal, the system is egalitarian; when point sums differ by at most one, it is almost egalitarian. For Steiner quadruple systems, a doubling construction is adapted to establish that an egalitarian S (3 , 4 , v) exists whenever v ≡ 4 , 20 (mod 24) and that an almost egalitarian S (3 , 4 , v) exists whenever v ≡ 8 , 16 (mod 24) and v ≠ 8. [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]

A μ-way (v, k, t) trade of volume m consists of μ disjoint collections T1, T2, . . . Tμ, each of m blocks, such that for every t-subset of v-set V the number of blocks containing this t-subset is the same in each Ti (1 ≤ i ≤ μ). In other words any pair of collections {Ti, Tj}, 1 ≤ i < j ≤ μ is a (v, k, t) trade of volume m. In this paper we investigate the existence of ≥-way (v, k, t) trades and prove the existence of. (i) 3-way (v, k, 1) trades Steiner trades) of each volume m,m ≥ 2. (ii) 3-way (v, k, 2) trades of each volume m,m ≥ 6 except possibly m = 7. We establish the non-existence of 3-way (v, 3, 2) trade of volume 7. It is shown that the volume of a 3-way (v, k, 2) Steiner trade is at least 2k for k ≥ 4. Also the spectrum of 3-way (v, k, 2) Steiner trades for k = 3 and 4 are specified. [ABSTRACT FROM AUTHOR]

A criterion for the continuity of the Steiner ratio, the Steiner subratio, and the Steiner-Gromov ratio in the space of all compact metric spaces with the Gromov-Hausdorff metric is obtained. It is also proved that these functions are upper semicontinuous. [ABSTRACT FROM AUTHOR]

In 2009 it was established that any partial Steiner triple system of order u has an embedding of order v for each v &#8805: 2u+1 such that v = 1, 3 (mod 6), in accordance with a conjecture of Lindner. It is known that for each u ≥ 9, there exists a partial Steiner triple system of order u that does not have an embedding of order v for any v < 2u + 1, so this result is best possible in one sense. Many partial Steiner triple systems do have embeddings of orders smaller than 2u + 1, however, although little is known about when such embeddings exist. In this paper we construct embeddings of orders less than 2u+1 for partial Steiner triple systems with few triples. In particular, we show that a partial Steiner triple system of order u ≥ 62 with at most u²/50-11u/100-116/75 triples has an embedding of order v for each admissible integer v ≥ 8u+17/5. [ABSTRACT FROM AUTHOR]

We prove that, for even m, the chromatic index of the projective triple system STS( [ABSTRACT FROM AUTHOR]

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

For a block design $${\mathcal{D}}$$ , a series of block intersection graphs G, or i-BIG( $${\mathcal{D}}$$), i = 0, . . . , k is defined in which the vertices are the blocks of $${\mathcal{D}}$$ , with two vertices adjacent if and only if the corresponding blocks intersect in exactly i elements. A silver graph G is defined with respect to a maximum independent set of G, called an α- set. Let G be an r-regular graph and c be a proper ( r + 1)-coloring of G. A vertex x in G is said to be rainbow with respect to c if every color appears in the closed neighborhood $${N[x] = N(x) \cup \{x\}}$$ . Given an α-set I of G, a coloring c is said to be silver with respect to I if every $${x\in I}$$ is rainbow with respect to c. We say G is silver if it admits a silver coloring with respect to some I. Finding silver graphs is of interest, for a motivation and progress in silver graphs see Ghebleh et al. (Graphs Combin 24(5):429-442, ) and Mahdian and Mahmoodian (Bull Inst Combin Appl 28:48-54, ). We investigate conditions for 0-BIG( $${\mathcal{D}}$$) and 1-BIG( $${\mathcal{D}}$$) of Steiner 2-designs $${{\mathcal{D}}=S(2,k,v)}$$ to be silver. [ABSTRACT FROM AUTHOR]

It is well known that when [ABSTRACT FROM AUTHOR]

Abstract: A flower, , around a point in a Steiner triple system is the set of all triples in which contain the point , namely . This paper determines the possible number of common flowers that two Steiner triple systems can have in common. For all admissible pairs where we construct a pair of Steiner triple systems of order where the flowers around elements of are identical in both Steiner triple systems, except for the pairs , and . Equivalently this result shows that there is a Steiner triple trade of foundation that can be embedded in a for each admissible and except when or . [Copyright &y& Elsevier]

Abstract: In this paper, we study the problem of finding the largest integer for which there exists a set of points and blocks in a balanced incomplete block design such that none of the points lie on any of the blocks. We investigate this problem for two types of BIBDs: projective planes and Steiner triple systems. For a Steiner triple system on points, we prove that , and we determine necessary and sufficient conditions for equality to be attained in this bound. For a projective plane of order , we prove that , and we show that equality can be attained in this bound whenever is an even power of two. [Copyright &y& Elsevier]

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

Abstract: A Steiner system is a pair , where is a -element set and is a set of -subsets of , called blocks, with the property that every -element subset of is contained in a unique block. The sub-design in a Steiner quadruple system is said to be a spanning block design. The order of a Steiner quadruple system with a spanning block design should satisfy the necessary condition . It is proved that the above necessary condition is also sufficient. As a consequence, it is also proved that a 3-BD exists for any . [Copyright &y& Elsevier]

The article presents information on a research paper on discrete mathematics which concludes that two fold systems hold good for all natural numbers. The authors construct a pairwise balanced design (PBD) for the order 6n+4 and two fold exit systems for the order 3n+2. It makes use of Steiner Triple System (STS), a type of block design in combinatorial mathematics, already existing for the order 6n+1 and 6n+3 and PBD for the order 6n+5.

The original classiffcation of PBIBDs defined group divisible designs GDD(v=v1+ v2+…+vg,g,k,λ1,λ2) with λ1≠0. In this paper, we prove that the necessary conditions are suffcient for the existence of the group divisible designs with two groups of unequal sizes and block size three with λ2=1 [ABSTRACT FROM AUTHOR]

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]

Inaccuracies in computations in the paper of the authors on classification of perfect binary codes of lengths 15 and 16 and of rank 13 are fixed. An explicit construction of all extended perfect codes of length 16 and rank 13 with a given kernel size is presented. Perfect binary codes of length 15 and rank 14 obtained by the general doubling construction are classified. [ABSTRACT FROM AUTHOR]

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  A transformation of Steiner quadruple systems S(υ, 4, 3) is introduced. For a given system, it allows to construct new systems of the same order, which can be nonisomorphic to the given one. The structure of Steiner systems S(υ, 4, 3) is considered. There are two different types of such systems, namely, induced and singular systems. Induced systems of 2-rank r can be constructed by the introduced transformation of Steiner systems of 2-rank r − 1 or less. A sufficient condition for a Steiner system S(υ, 4, 3) to be induced is obtained. [ABSTRACT FROM AUTHOR]

Abstract: Generalized Steiner systems were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size with minimum Hamming distance , in which each codeword has length and weight . As to the existence of a , a lot of work has been done for , while not so much is known for . The notion GDD was first introduced by Chen et al. and used to construct . The necessary condition for the existence of a is . In this paper, it is proved that there exists a for any prime power and . By using this result, the known results on the existence of optimal quaternary constant weight codes are then extended. [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]

Abstract: The concept of good large set of Steiner triple systems (or GLS in short) was introduced by Lu in his paper “on large sets of disjoint Steiner triple systems”, [J. Lu, On large sets of disjoint Steiner triple systems, I–III, J. Combin. Theory (A) 34 (1983) 140-182]. In this paper a doubling construction for GLSs is displayed and some existence results are obtained. [Copyright &y& Elsevier]

Abstract: We present an orderly algorithm for classifying triple systems. Subsequently, we show that there exist exactly 7038,699,746 nonisomorphic simple 2- designs. The method is also used to confirm the previously accomplished classifications of 2-, 2- and 2- designs. [Copyright &y& Elsevier]

Abstract: A hexagon triple is the graph consisting of the three triangles (triples) , and , where , and are distinct. The triple is called an inside triple. A hexagon triple system of order is a pair where is a collection of edge disjoint hexagon triples which partitions the edge set of with vertex set . The inside triples form a partial Steiner triple system. We show that any Steiner triple system of order can be embedded in the inside triples of a hexagon triple system of order approximately . [Copyright &y& Elsevier]

Abstract: A -design of order embeds a given Steiner triple system if there is a subset of points on which the graphs of the design induce the blocks of the original Steiner triple system. It has been established that , and that when equality is met, such a minimum embedding of an STS() exists, except when . Equality only holds when . One natural question is: What is the smallest order such that some STS can be embedded into a -design of order ? We solve the problem for 7 of the 10 congruence classes modulo 30. [Copyright &y& Elsevier]

We present the Cost-Distance problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known O(log k) randomized approximation scheme for Cost-Distance, where k is the number of sources. We reduce several common network design problems to Cost- Distance, obtaining (in some cases) the first known logarithmic approximation for them. These problems include single-sink buy-at-bulk with variable pipe types between different sets of nodes, facility location with buy-at-bulk-type costs on edges (integrated logistics), constructing singlesource multicast trees with good cost and delay properties, priority Steiner trees, and multilevel facility location. Our algorithm is also easier to implement and significantly faster than previously known algorithms for buy-at-bulk design problems. [ABSTRACT FROM AUTHOR]

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 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]

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called the Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus, most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph, this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any two-pin net and many higher pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works. [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]

Several evolutionary algorithms (EAs) applied to a wide class of communication network design problems modelled under the generalized Steiner problem (GSP) are evaluated. In order to provide a fault-tolerant design, a solution to this problem consists of a preset number of independent paths linking each pair of potentially communicating terminal nodes. This usually requires considering intermediate non-terminal nodes (Steiner nodes), which are used to ensure path redundancy, while trying to minimize the overall cost. The GSP is an NP-hard problem for which few algorithms have been proposed. This article presents a comparative study of pure and hybrid EAs applied to the GSP, codified over MALLBA, a general purpose library for combinatorial optimization. The algorithms were tested on several GSPs, and asset efficient numerical results are reported for both serial and distributed models of the evaluated algorithms. [ABSTRACT FROM AUTHOR]

Abstract  The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length n and Hamming weight 3 and having the following property: any 3 � n matrix whose rows are cyclic shifts of three different code vectors contains a 3 � 3 permutation matrix as a submatrix. This property (in the special case w = 3) characterizes conflict-avoiding codes of length n for w active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of w active users to transmit a data packet successfully in one of w attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length n with w = 3 is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for w = 3 which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class. [ABSTRACT FROM AUTHOR]

Abstract  A Steiner triple system of order n (for short, STS(n)) is a system of three-element blocks (triples) of elements of an n-set such that each unordered pair of elements occurs in precisely one triple. Assign to each triple (i,j,k) ∊ STS(n) a topological triangle with vertices i, j, and k. Gluing together like sides of the triangles that correspond to a pair of disjoint STS(n) of a special form yields a black-and-white tiling of some closed surface. For each n ≡ 3 (mod 6) we prove that there exist nonisomorphic tilings of nonorientable surfaces by pairs of Steiner triple systems of order n. We also show that for half of the values n ≡ 1 (mod 6) there are nonisomorphic tilings of nonorientable closed surfaces. [ABSTRACT FROM AUTHOR]

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 P be a k colored point set in general position, k ≥ 2. A family of quadrilaterals with disjoint interiors $$\mathcal Q_1, \ldots, \mathcal Q_m$$ is called a quadrangulation of P if $$V(\mathcal Q_1) \cup \cdots \cup V(\mathcal Q_m) = P$$ , the edges of all $$\mathcal Q_i$$ join points with different colors, and $$\mathcal Q_1 \cup \cdots \cup \mathcal Q_m = {\rm Conv} (P)$$ . In general it is easy to see that not all k-colored point sets admit a quadrangulation; when they do, we call them quadrangulatable. For a point set to be quadrangulatable it must satisfy that its convex hull Conv( P) has an even number of points and that consecutive vertices of Conv( P) receive different colors. This will be assumed from now on. In this paper, we study the following type of questions: Let P be a k-colored point set. How many Steiner points in the interior of Conv( P) do we need to add to P to make it quadrangulatable? When k = 2, we usually call P a bichromatic point set, and its color classes are usually denoted by R and B, i.e. the red and blue elements of P. In this paper, we prove that any bichromatic point set $$P = R\cup B$$ where | R| = | B| = n can be made quadrangulatable by adding at most $$\left\lfloor\frac{n -1}{3}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + 1$$ Steiner points and that $$\frac{m}{3}$$ Steiner points are occasionally necessary. To prove the latter, we also show that the convex hull of any monochromatic point set P of n elements can be always partitioned into a set $${\mathcal{S}} = \{{\mathcal{S}}_1,\ldots, {\mathcal{S}}_{t}\}$$ of star-shaped polygons with disjoint interiors, where $$V({\mathcal{S}}_1)\cup\cdots\cup V({\mathcal{S}}_{t }) = P$$ , and $$t\leq \left\lfloor\frac{n - 1}{3}\right\rfloor+1$$ . For n = 3 k this bound is tight. Finally, we prove that there are 3-colored point sets that cannot be completed to 3-quadrangulatable point sets. [ABSTRACT FROM AUTHOR]