On the existence of mandatory representation designs with block sizes 3 and k

A mandatory representation design MR[ν,K] is a pairwise balanced design on ν points with block sizes from K in which for each k ∈ K there is a block in the design of size k. Mendelsohn and Rees [4] investigated the existence of MR[ν,K]s, where 3 ∈ K. In this report we consider additional necessary conditions, where K = {3,k}. These conditions are proved to be sufficient for 4 ≤ k ≤ 50 with one genuine exception. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 122–131, 2000     

New large sets of t‐designs

Abstact: We introduce generalizations of earlier direct methods for constructing large sets of t‐designs. These are based on assembling systematically orbits of t‐homogeneous permutation groups in their induced actions on k‐subsets. By means of these techniques and the known recursive methods we construct an extensive number of new large sets, including new infinite families. In particular, a new series of LS[3](2(2 + m), 8·3^m ? 2, 16·3^m ? 3) is obtained. This also provides the smallest known ν for a t‐(ν, k, λ) design when t ≥ 16. We present our results compactly for ν ≤ 61, in tables derived from Pascal's triangle modulo appropriate primes. © 2000 John Wiley & Sons, Inc. J Combin Designs 9: 40–59, 2001     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

A jump inversion theorem for the enumeration jump

Abstract. We prove a jump inversion theorem for the enumeration jump and a minimal pair type theorem for the enumeration reducibilty. As an application some results of Selman, Case and Ash are obtained. Received: 15 May 1998     

Chemical trees enumeration algorithms

In the chemical community the need for representing chemical structures within a given family and of efficiently enumerating these structures suggested the use of computers and the implementation of fast enumeration algorithms. This paper considers the isomeric acyclic structures focusing on the enumeration of the alkane molecular family. For this family, Trinajsti et al. (1991) devised an enumeration algorithm which is the most widely known and utilized nowadays. Kvasnika and Pospichal (1991) have proposed an algorithmic scheme which, from the computational complexity point of view, can prove to be more efficient than the Trinajsti one, nevertheless, this algorithm, to the best of our knowledge, has never been implemented. Indeed an efficient implementation requires the introduction of non trivial data structures and other computational tricks. The main contribution of this paper consists of the definition of the implementation details of Kvasnika-Pospichals algorithm, in a comparison of Trinajstis, Kvasnika-Pospichals and two new algorithms, proposed here, in terms of both computational complexity analysis and running times.AMS classification: 05A15, 05C05, 05C30, 05C90Part of this work has been developed during a visit of the first two authors at the EPFL of Lausanne     

An application of coding theory to a problem in graphical enumeration

This note was written while the first author was visiting the Department of Combinatorics and Optimization of the University of Waterloo as an Adjunct Professor. He would like to thank his colleagues there for their hospitality. The second author acknowledges the support of the National Science and Engineering Research Council of Canada given under grant #0GP0009258.     

Structure and automorphism groups of Hadamard designs

Let n be the order of a Hadamard design, and G any finite group. Then there exists many non-isomorphic Hadamard designs of order 2^{12|G| + 13} n with automorphism group isomorphic to G.This research was supported in part by the National Science Foundation.     

Two-dimensional minimax Latin hypercube designs

We investigate minimax Latin hypercube designs in two dimensions for several distance measures. For the ?^∞-distance we are able to construct minimax Latin hypercube designs of n points, and to determine the minimal covering radius, for all n. For the ?¹-distance we have a lower bound for the covering radius, and a construction of minimax Latin hypercube designs for (infinitely) many values of n. We conjecture that the obtained lower bound is attained, except for a few small (known) values of n. For the ?²-distance we have generated minimax solutions up to n=27 by an exhaustive search method. The latter Latin hypercube designs are included in the website www.spacefillingdesigns.nl.     

Decomposing triples into cyclic designs

Motivated by constructing cyclic simple designs, we consider how to decomposing all the triples of Z_v into cyclic triple systems. Furthermore, we define a large set of cyclic triple systems to be a decomposition of triples of Z_v into indecomposable cyclic designs. Constructions of decompositions and large sets are given. Some infinite classes of decompositions and large sets are obtained. Large sets of small v with odd v<97 are also given. As an application, the results are used to construct cyclic simple triple systems.     

Asymptotic enumeration of RNA secondary structure

Based on the new representation of RNA secondary structures, we obtain the basic relations about secondary structures with a prescribed size m for hairpin loops and minimum stack length l. Furthermore, we make an asymptotic analysis on RNA secondary structures with certain additional constrains.     

Octahedral designs

An oriented octahedral design of order v, or OCT(v), is a decomposition of all oriented triples on v points into oriented octahedra. Hanani [H. Hanani, Decomposition of hypergraphs into octahedra, Second International Conference on Combinatorial Mathematics (New York, 1978), Annals of the New York Academy of Sciences, 319, New York Academy of Science, New York, 1979, pp. 260–264.] settled the existence of these designs in the unoriented case. We show that an OCT(v) exists if and only if v≡1, 2, 6 (mod 8) (the admissible numbers), and moreover the constructed OCT(v) are unsplit, i.e. their octahedra cannot be paired into mirror images. We show that an OCT(v) with a subdesign OCT(U) exists if and only if v and u are admissible and v≥u+4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:319–327, 2010     

Classification of designs with nontrivial automorphism groups

In this article, we introduce a new orderly backtrack algorithm with efficient isomorph rejection for classification of t‐designs. As an application, we classify all simple 2‐(13,3,2) designs with nontrivial automorphism groups. The total number of such designs amounts to 1,897,386. The decomposability of the designs is also considered. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 479–489, 2006     

An upper bound on the number of Steiner triple systems

Richard Wilson conjectured in 1974 the following asymptotic formula for the number of n ‐vertex Steiner triple systems: \begin{align*} STS(n) = \left( (1+o(1))\frac{n}{e^2} \right)^{\frac{n^2}{6}}\end{align*}. Our main result is that The proof is based on the entropy method. As a prelude to this proof we consider the number F(n) of 1 ‐factorizations of the complete graph on n vertices. Using the Kahn‐Lovász theorem it can be shown that We show how to derive this bound using the entropy method. Both bounds are conjectured to be sharp. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 399–406, 2013     

Quasi-affine symmetric designs

A symmetric design with parameters v = q ²(q + 2), k = q(q + 1), λ = q, q ≥ 2, is called a quasi-affine design if its point set can be partitioned into q + 2 subsets P ₀, P ₁,..., P _q , P _q+1 such that the induced structure in every point neighborhood is an affine plane of order q (repeated q times). A quasi-affine design with q ≥ 3 determines its point neighborhoods uniquely and dual of such a design is also a quasi-affine design. These structural properties pave way for definition of a strongly quasi-affine design and it is also shown that associated with every quasi-affine design is a unique strongly quasi-affine design from which the given quasi-affine design is obtained by certain unique cutting and pasting operation. This investigation also enables us to associate a unique 2-regular graph with q + 2 vertices and in turn, a unique colored partition of the integer q + 2. These combinatorial consequences are finally used to obtain an exponential lower bound on the number of non-isomorphic solutions of such symmetric designs improving the earlier lower bound of 2. Work of Sanjeevani Gharge is supported by Faculty Improvement Programme of U.G.C., India.     

Quantum field theory techniques in graphical enumeration

We present a method for counting closed graphs on a compact Riemannian surface, based on techniques suggested by quantum field theory.     

Bounds on the number of Hadamard designs of even order

A new lower bound on the number of non‐isomorphic Hadamard symmetric designs of even order is proved. The new bound improves the bound on the number of Hadamard designs of order 2n given in [12] by a factor of 8n ? 1 for every odd n > 1, and for every even n such that 4n ? 1 > 7 is a prime. For orders 8, 10, and 12, the number of non‐isomorphic Hadamard designs is shown to be at least 22,478,260, 1.31 × 10¹⁵, and 10²⁷, respectively. For orders 2n = 14, 16, 18 and 20, a lower bound of (4n ? 1)! is proved. It is conjectured that (4n ? 1)! is a lower bound for all orders 2n ≥ 14. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 363‐378, 2001