The configuration polytope of ℓ-line configurations in Steiner triple systems

It has been shown that the number of occurrences of any ℓ-line configuration in a Steiner triple system can be written as a linear combination of the numbers of full m-line configurations for 1 ≤ m ≤ ℓ; full means that every point has degree at least two. More precisely, the coefficients of the linear combination are ratios of polynomials in v, the order of the Steiner triple system. Moreover, the counts of full configurations, together with v, form a linear basis for all of the configuration counts when ℓ ≤ 7. By relaxing the linear integer equalities to fractional inequalities, a configuration polytope is defined that captures all feasible assignments of counts to the full configurations. An effective procedure for determining this polytope is developed and applied when ℓ = 6. Using this, minimum and maximum counts of each configuration are examined, and consequences for the simultaneous avoidance of sets of configurations explored. To Alex Rosa on the Occasion of his Seventieth Birthday     

The Number of Cyclic Configurations of Type (v3) and the Isomorphism Problem

A configuration of points and lines is cyclic if it has an automorphism that permutes its points in a full cycle. A closed formula is derived for the number of nonisomorphic connected cyclic configurations of type (v₃), i.e. which have v points and lines, and each point/line is incident with exactly three lines/points. In addition, a Bays–Lambossy type theorem is proved for cyclic configurations if the number of points is a product of two primes or a prime power.     

Configurations in 4-Cycle Systems

A 4-cycle system of order n, denoted by 4CS(n), exists if and only if n1 (mod 8). There are four configurations which can be formed by two 4-cycles in a 4CS(n). Formulas connecting the number of occurrences of each such configuration in a 4CS(n) are given. The number of occurrences of each configuration is determined completely by the number d of occurrences of the configuration D consisting of two 4-cycles sharing a common diagonal. It is shown that for every n1 (mod 8) there exists a 4CS(n) which avoids the configuration D, i.e. for which d=0. The exact upper bound for d in a 4CS(n) is also determined.Acknowledgments A substantial part of the work forming this paper was done while the first author was visiting the Department of Pure Mathematics of The Open University at Milton Keynes; he thanks the Department for hospitality and the UK EPSRC for financial support (grant number GR/R78282/01). The first author also gratefully acknowledges the support of the Australian Research Council. The fourth author is supported by the VEGA grant 1/0261/03. All the authors thank the referees for their helpful comments.Final version received: November 11, 2003     

Unions of orthogonally convex or orthogonally starshaped polygons

LetT be a simply connected orthogonal polygon having the property that for every three points ofT, at least two of these points see each other via staircases inT. ThenT is a union of three orthogonally convex polygons. The number three is best possible.ForT a simply connected orthogonal polygon,T is a union of two orthogonally convex polygons if and only if for every sequencev ₁,...,v _n,v _n+1 =v ₁ inT, n odd, at least one consecutive pairv _i ,v _i+1 sees each other via staircase paths inT, 1 i n. An analogous result says thatT is a union of two orthogonal polygons which are starshaped via staircase paths if and only if for every odd sequence inT, at least one consecutive pair sees a common point via staircases inT.Supported in part by NSF grants DMS-8908717 and DMS-9207019.     

On the rank of truncated incidence matrices of linear spaces

It is well known that for every finite linear space the number b of lines is greater or equal to the number v of points of the space. In this paper we investigate the relation between the nonnegative integer b - v and suitable configurations of subspaces of a linear space.     

Classification of (v, 3)-configurations

A (v, 3)-configuration is a nondegenerate matrix of dimension v over the field GF(2) considered up to permutation of rows and columns and containing exactly three 1’s in the rows and columns, while the inverse matrix has also exactly three 1’s in the rows and columns. It is proved that, for each even v ≥ 4, there is only one indecomposable (v, 3)-configuration, while, for odd v, there are no such configurations, the only exception being the unique (5, 3)-configuration.     

Maximal resolvable packings and minimal resolvable coverings of triples by quadruples

Determination of maximal resolvable packing number and minimal resolvable covering number is a fundamental problem in designs theory. In this article, we investigate the existence of maximal resolvable packings of triples by quadruples of order v (MRPQS(v)) and minimal resolvable coverings of triples by quadruples of order v (MRCQS(v)). We show that an MRPQS(v) (MRCQS(v)) with the number of blocks meeting the upper (lower) bound exists if and only if v≡0 (mod 4). As a byproduct, we also show that a uniformly resolvable Steiner system URS(3, {4, 6}, {r₄, r₆}, v) with r₆≤1 exists if and only if v≡0 (mod 4). All of these results are obtained by the approach of establishing a new existence result on RH(6²ⁿ) for all n≥2. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 209–223, 2010     

Some combinatorial constructions for optimal perfect deletion-correcting codes

There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(k − t, k, v)-codes and T(k − t, k, v)-codes respectively. The cardinality of a T(k − t, k, v)-code is determined by its parameters, while T*(k − t, k, v)-codes do not necessarily have a fixed size. Let N(k − t, k, v) denote the maximum number of codewords in any T*(k − t, k, v)-code. A T*(k − t, k, v)-code with N(k − t, k, v) codewords is said to be optimal. In this paper, some combinatorial constructions for optimal T*(2, k, v)-codes are developed. Using these constructions, we are able to determine the values of N(2, 4, v) for all positive integers v. The values of N(2, 5, v) are also determined for almost all positive integers v, except for v = 13, 15, 19, 27 and 34.      

On large sets of almost Hamilton cycle decompositions

A large set of CS(v, k, λ), k‐cycle system of order v with index λ, is a partition of all k‐cycles of K_v into CS(v, k, λ)s, denoted by LCS(v, k, λ). A (v ? 1)‐cycle is called almost Hamilton. The completion of the existence spectrum for LCS(v, v ? 1, λ) only depends on one case: all v ≥ 4 for λ = 2. In this article, it is shown that there exists an LCS(v, v ? 1,2) for any v ≡ 0,1 (mod 4) except v = 5, and for v = 6,7,10,11. © 2006 Wiley Periodicals, Inc. J Combin Designs 16: 53–69, 2008     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

Support sizes of threefold resolvable triple systems

Let SS_R(v, 3) denote the set of all integer b* such that there exists a RTS(v, 3) with b* distinct triples. In this paper, we determine the set SS_R(v, 3) for v ≡ 3 (mod 6) and v ≥ 3 with only five undecided cases. We establish that SS_R(v, 3) = P(v, 3) for v ≡ 3 (mod 6), v ≥ 21 and v ≠ 33, 39 where P(v, 3) = {m_v, m_v + 4, m_v + 6, m_v + 7, …, 3m_v} and m_v, = v(v ? 1)/6. As a by‐product, we remove the last two undecided cases for the intersection numbers of Kirkman triple system of order 27, this improves the known result provided in [ 2 ]. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 275–289, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10037     

Some new bounds for the maximum number of vertex colorings of a (v,e)-graph

Let f(v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f(v, e, λ). In particular, a new notion of pseudo-proper colorings of a graph is given, which allows us to significantly improve the upper bounds for f(v, e, 3) given by Lazebnik and Liu in the case where e > v²/4. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 115–128, 1998     

Bounds and Constructions on (v, 4, 3, 2) Optical Orthogonal Codes

In this paper, we are concerned about optimal (v, 4, 3, 2)‐OOCs. A tight upper bound on the exact number of codewords of optimal (v, 4, 3, 2)‐OOCs and some direct and recursive constructions of optimal (v, 4, 3, 2)‐OOCs are given. As a result, the exact number of codewords of an optimal (v, 4, 3, 2)‐OOC is determined for some infinite series.     

Planar cyclic difference packings

A planar cyclic difference packing modulo v is a collection D = {d₁, d₂,…,d_k} of distinct residues modulo v such that any residue α ≢ 0 (mod v) has at most one representation as a difference d_i − d_j (mod v). This paper develops various constructions of such designs and for a fixed positive integer v presents upper and lower bounds on Ψ (v), the maximal number of elements that a planar cyclic difference packing modulo v can contain. This paper also presents the results of calculating Ψ (v) for v ≤ 144, including the fact that 134 is the smallest value of v for which the elementary upper bound of exceeds Ψ (v) by two. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 426–434, 2000     

A Magnetic Procedure for the Stability Number

A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new vertex linked to all common neighbours of u and v without changing the stability number. We prove that all graphs containing no chordless cycle C _k (k ≥ 5) and none of eleven forbidden subgraphs can be reduced to a stable set by repeated use of magnets. For such graphs a polynomial algorithm is given to determine the stability number.     

Resolvable packings of Kv with K2 × Kc's

The study of resolvable packings of K_v with K_r × K_c's is motivated by the use of DNA library screening. We call such a packing a (v, K_r × K_c, 1)‐RP. As usual, a (v, K_r × K_c, 1)‐RP with the largest possible number of parallel classes (or, equivalently, the largest possible number of blocks) is called optimal. The resolvability implies v ≡ 0 (mod rc). Let ρ be the number of parallel classes of a (v, K_r × K_c, 1)‐RP. Then we have ρ ≤ ?(v‐1)/(r + c ? 2)?. In this article, we present a number of constructive methods to obtain optimal (v, K₂ × K_c, 1)‐RPs meeting the aforementioned bound and establish some existence results. In particular, we show that an optimal (v, K₂ × K₃, 1)‐RP meeting the bound exists if and only if v ≡ 0 (mod 6). © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 177–189, 2009     

Existence of directed BIBDs with block size 7 and related perfect 5-deletion-correcting codes of length 7

Wang and Yin have established the existence of a directed BIBD with block size 7 and index 1 (a DBIBD(v, 7, 1)) for all v ≡ 1, 7 (mod 21) except for v = 22 and possibly for 68 other cases. In this paper, we reduce the number of possible exceptions to 4, namely v = 274, 358, 400, 526. Correspondingly, for all such v, our results establish the existence of a T(2, 7, v)-code or equivalently a perfect 5-deletion-correcting code with words of length 7 over an alphabet of size v, where all the coordinates must be different. In the process, we also reduce the possible exceptions for (v, 7, 2)-BIBDs to 2 cases, v = 274 and 358 (in addition to the non-existent (22, 7, 2)-BIBD).     

Mixed Random Mosaics

Cowan [2] has defined random mosaics processes RMP in R² and has given some basic properties of them. In particular Cowan introduces the fundamental parameters α, β_k, γ_k of the process and, in terms of them, he computes the mean values of the area α, perimeter h, number of ares w and number of vertices v of a typical polygon of the RMP. Our purpose is to consider the RMP obtained by superposition of two independent random mosaics. Then, the characteristics a₁₂, h₁₂, w₁₂, v₁₂ of the resulting process are computed in terms of the characteristics a_i, h_i, w_i, v_i, of each process. The case of non random tessellations mixed with random mosaics is also considered.