A Number Theoretic Conjecture and the Existence of S–Cyclic Steiner Quadruple Systems

In their survey article on cyclic Steiner Quadruple Systems SQS(v) M. J. Grannel and T. S. Griggs advanced the conjecture (cf. [8, p. 412]) that their necessary condition for the existence of S-cyclic SQS(v) (cf. [7, p. 51]) is also sufficient. Some years prior to that E. Köhler [10] used a graph theoretical method to construct S-cyclic SQS(v). This method was extended in [17]-[20] and eventually used to reduce the conjecture of Grannel and Griggs to a number theoretic claim (cf. also [21], research problem 146). The main purpose of the present paper is to attack this claim. For the long intervals we have to distinguish four cases. The proof of cases I–III can be accomplished by a thorough study of how the multiples of a certain set belonging to the first column of a certain matrix (the elements of which are essentially the vertices of a graph corresponding to SQS(2p)) are distributed over the columns. The proof is by contradiction. Case IV is most difficult to treat and could only be dealt with by very deep lying means. We have to use an asymptotic formula on the number of lattice points (x,y) with xy 1 mod p (we speak of 1-points) in a rectangle and this formula shows that the 1-points are equidistributed. But even so our claim could not be proved for all intervals of admissible length. Intervals [a,b] with for some m and could not be covered. In the last section we discuss some conclusions which would follow from the non-existence of complete intervals.     

Point Code Minimum Steiner Triple Systems

The point code of a Steiner triple system uniquely determines the system when the number of vectors whose weight equals the replication number agrees with the number of points. The existence of a Steiner triple system with this minimum point code property is established for all v 1,3 (mod 6) with v 15.     

Clique partitions of complements of forests and bounded degree graphs

In this paper, we prove that for any forest F⊂K_n, the edges of E(K_n)?E(F) can be partitioned into O(nlogn) cliques. This extends earlier results on clique partitions of the complement of a perfect matching and of a hamiltonian path in K_n.In the second part of the paper, we show that for n sufficiently large and any ε∈(0,1], if a graph G has maximum degree O(n^1-ε), then the edges of E(K_n)?E(G) can be partitioned into cliques provided there exist certain Steiner systems. Furthermore, we show that there are such graphs G for which Ω(ε²n^2-2ε) cliques are required in every clique partition of E(K_n)?E(G).     

Minimum embedding of Steiner triple systems into -designs I

A (K₄-e)-design on v+w points embeds a Steiner triple system (STS) if there is a subset of v points on which the graphs of the design induce the blocks of a STS. It is established that wv/3, and that when equality is met that such a minimum embedding of an STS(v) exists, except when v=15.     

Cokernel bundles and Fibonacci bundles

We are interested in those bundles C on ?^N which admit a resolution of the form 0 → ?^s ? E ?^t ? F → C → 0. In this paper we prove that, under suitable conditions on (E, F), a generic bundle with this form is either simple or canonically decomposable. As applications we provide an easy criterion for the stability of such bundles on ?² and we prove the stability when E = ??, F = ??(1) and C is an exceptional bundle on ?^N for N ≥ 2. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches

We propose a generalized version of the Prize Collecting Steiner Tree Problem (PCSTP), which offers a fundamental unifying model for several well-known -hard tree optimization problems. The PCSTP also arises naturally in a variety of network design applications including cable television and local access networks. We reformulate the PCSTP as a minimum spanning tree problem with additional packing and knapsack constraints and we explore various nondifferentiable optimization algorithms for solving its Lagrangian dual. We report computational results for nine variants of deflected subgradient strategies, the volume algorithm (VA), and the variable target value method used in conjunction with the VA and with a generalized Polyak–Kelley cutting plane technique. The performance of these approaches is also compared with an exact stabilized constraint generation procedure.     

Configuration distribution and designs of codes in the Johnson scheme

The main goal of this article is to present several connections between perfect codes in the Johnson scheme and designs, and provide new tools for proving Delsarte conjecture that there are no nontrivial perfect Codes in the Johnson scheme. Three topics will be considered. The first is the configuration distribution which is akin to the weight distribution in the Hamming scheme. We prove that if there exists an e‐perfect code in the Johnson scheme then there is a formula which connects the number of vectors at distance i from any codeword in various codes isomorphic to . The second topic is the Steiner systems embedded in a perfect code. We prove a lower bound on the number of Steiner systems embedded in a perfect code. The last topic is the strength of a perfect code. We show two new methods for computing the strength of a perfect code and demonstrate them on 1‐perfect codes. We further discuss how to settle Delsarte conjecture. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 15–34, 2007     

On the number of partial Steiner systems

We give a simple proof of the result of Grable on the asymptotics of the number of partial Steiner systems S(t,k,m). © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 347–352, 2000