Small Uniformly Resolvable Designs for Block Sizes 3 and 4

A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k, such a class is denoted k‐pc and for a given k the number of k‐pcs is denoted r_k. In this paper, we consider the case of block sizes 3 and 4 (both existent). We use v to denote the number of points, in this case the necessary conditions imply that v ≡ 0 (mod 12). We prove that all admissible URDs with v < 200 points exist, with the possible exceptions of 13 values of r₄ over all permissible v. We obtain a URD({3, 4}; 276) with r₄ = 9 by direct construction use it to and complete the construction of all URD({3, 4}; v) with r₄ = 9. We prove that all admissible URDs for v ≡ 36 (mod 144), v ≡ 0 (mod 60), v ≡ 36 (mod 108), and v ≡ 24 (mod 48) exist, with a few possible exceptions. Recently, the existence of URDs for all admissible parameter sets with v ≡ 0 (mod 48) was settled, this together with the latter result gives the existence all admissible URDs for v ≡ 0 (mod 24), with a few possible exceptions.     

Variations on seven points: An introduction to the scope and methods of coding theory and finite geometries

We use a simple example (the projective plane on seven points) to give an introductory survey on the problems and methods in finite geometries — an area of mathematics related to geometry, combinatorial theory, algebra, group theory and number theory as well as to applied mathematics (e.g., coding theory, information theory, statistical design of experiments, tomography, cryptography, etc.). As this list already indicates, finite geometries is — both from the point of view of pure mathematics and from that of applications related to computer science and communication engineering — one of the most interesting and active fields of mathematics. It is the aim of this paper to introduce the nonspecialist to some of these aspects.To Professor Günter Pickert on the occasion of his 65th birthday     

Coding into Ramsey sets

In [6] W. T. Gowers formulated and proved a Ramsey-type result which lies at the heart of his famous dichotomy for Banach spaces. He defines the notion of weakly Ramsey set of block sequences of an infinite dimensional Banach space and shows that every analytic set of block sequences is weakly Ramsey. We show here that Gowers’ result follows quite directly from the fact that all G_δ sets are weakly Ramsey, if the Banach space does not contain c₀, and from the fact that all F_σδ sets are weakly Ramsey, in the case of an arbitrary Banach space. We also show that every result obtained by the application of Gowers’ theorem to an analytic set can also be obtained by applying the Theorem to a F_σδ set (or to a G_δ set if the space does not contain c₀). This fact explains why the only known applications of this technique are based on very low-ranked Borel sets (open, closed, F_σ, or G_δ).     

Interpolation properties of linear projections and best approximation

Let P be a bounded linear projection from C[a,b] to a subspace V = span{v ₁…_m}. In this paper we study those projections P with Pf interpolating f at n or more distinct points for all f ∈C[a,6]. The same problem for best approximations is also studied.     

Resolvable Mendelsohn designs with block size 4

Summary Letv andK be positive integers. A (v, k, 1)-Mendelsohn design (briefly (v, k, 1)-MD) is a pair (X,B) whereX is av-set (ofpoints) andB is a collection of cyclically orderedk-subsets ofX (calledblocks) such that every ordered pair of points ofX are consecutive in exactly one block ofB. A necessary condition for the existence of a (v, k, 1)-MD isv(v–1) 0 (modk). If the blocks of a (v, k, 1)-MD can be partitioned into parallel classes each containingv/k blocks wherev ) (modk) or (v – 1)/k blocks wherev 1 (modk), then the design is calledresolvable and denoted briefly by (v, k, 1)-RMD. It is known that a (v, 3,1)-RMD exists if and only ifv 0 or 1 (mod 3) andv 6. In this paper, it is shown that the necessary condition for the existence of a (v, 4, 1)-RMD, namelyv 0 or 1 (mod 4), is also sufficient, except forv = 4 and possibly exceptingv = 12. These constructions are equivalent to a resolvable decomposition of the complete symmetric directed graphK _v ^* onv vertices into 4-circuits.Research supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-5320.     

Differences of Composition Operators between Weighted Banach Spaces of Holomorphic Functions on the Unit Polydisk

We consider differences of composition operators between given weighted Banach spaces H ^∞ _v or H ⁰ _v of analytic functions defined on the unit polydisk D ^N with weighted sup-norms and give estimates for the distance of these differences to the space of compact operators. We also study boundedness and compactness of the operators. This paper is an extension of [6] where the one-dimensional case is treated. Received: May 15, 2007. Revised: October 8, 2007.     

A few more Kirkman squares and doubly near resolvable BIBDs with block size 3

A Kirkman square with index λ, latinicity μ, block size k, and v points, KS_k(v;μ,λ), is a t×t array (t=λ(v-1)/μ(k-1)) defined on a v-set V such that (1) every point of V is contained in precisely μ cells of each row and column, (2) each cell of the array is either empty or contains a k-subset of V, and (3) the collection of blocks obtained from the non-empty cells of the array is a (v,k,λ)-BIBD. In a series of papers, Lamken established the existence of the following designs: KS₃(v;1,2) with at most six possible exceptions [E.R. Lamken, The existence of doubly resolvable (v,3,2)-BIBDs, J. Combin. Theory Ser. A 72 (1995) 50-76], KS₃(v;2,4) with two possible exceptions [E.R. Lamken, The existence of KS₃(v;2,4)s, Discrete Math. 186 (1998) 195-216], and doubly near resolvable (v,3,2)-BIBDs with at most eight possible exceptions [E.R. Lamken, The existence of doubly near resolvable (v,3,2)-BIBDs, J. Combin. Designs 2 (1994) 427-440]. In this paper, we construct designs for all of the open cases and complete the spectrum for these three types of designs. In addition, Colbourn, Lamken, Ling, and Mills established the spectrum of KS₃(v;1,1) in 2002 with 23 possible exceptions. We construct designs for 11 of the 23 open cases.     

Eigenvalues,geometric expanders,sorting in rounds,and ramsey theory

Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices. These graphs enable us to improve previous results on a parallel sorting problem that arises in structural modeling, by describing an explicit algorithm to sortn elements ink time units using parallel processors, where, e.g., α₂=7/4, α₃=8/5, α₄=26/17 and α₅=22/15. Our approach also yields several applications to Ramsey Theory and other extremal problems in combinatorics.     

Balancing vectors in the max norm

Let v₁, ..., v _n be vectors inR ⁿ of max norm at most one. It is proven that there exists a choice of signs for which all partial sums have max norm at mostKn ^1/2. It is further shown that such a choice of signs must be anticipatory—there is no way to choose thei-th sign without knowledge of v _j forj>i.     

4n − 10

We show that the maximal number K₂(n) of splits in a 2-compatible split system on an n-set is exactly 4n – 10, for every n > 3.Since K₂(n) = CF₃(n)/2 where CF₃(n) is the maximal number of members in any 3-cross-free collection of (proper) subsets of an n-set, this gives a definitive answer to a question raised in 1979 by A. Karzanov who asked whether CF₃(n) is, as a function of n, of type O(n).Karzanovs question was answered first by P. Pevzner in 1987 who showed K₂(n) 6n, a result that was improved by T. Fleiner in 1998 who showed K₂(n) 5n.The argument given in the paper below establishes that the even slightly stronger inequality K₂(n) 4n – 10 holds for every n > 3; the identity K₂(n) = 4n – 10 (n > 3) then follows in conjunction with a result from a previous paper that implies K₂(n) 4n – 10. In that paper, it was also mentioned that—in analogy to well known results regarding maximal weakly compatible split systems—2-compatible split systems of maximal cardinality 4n – 10 should be expected to be cyclic. Luckily, our approach here permits us also to corroborate this expectation. As a consequence, it is now possible to generate all 2-compatible split systems on an n-set (n > 3) that have maximal cardinality 4n – 10 (or, equivalently, all 3-cross-free set systems that have maximal cardinality 8n – 20) in a straight forward, systematic manner.Received March 19, 2003     

Finite line-transitive linear spaces: Theory and search strategies

The paper summarises existing theory and classifications for finite line-transitive linear spaces, develops the theory further, and organises it in a way that enables its effective application. The starting point is a theorem of Camina and the fifth author that identifies three kinds of line-transitive automorphism groups of linear spaces. In two of these cases the group may be imprimitive on points, that is, the group leaves invariant a nontrivial partition of the point set. In the first of these cases the group is almost simple with point-transitive simple socle, and may or may not be point-primitive, while in the second case the group has a non-trivial point-intransitive normal subgroup and hence is definitely point-imprimitive. The theory presented here focuses on point-imprimitive groups. As a non-trivial application a classification is given of the point-imprimitive, line-transitive groups, and the corresponding linear spaces, for which the greatest common divisor gcd（k, v - 1） ≤ 8, where v is the number of points, and k is the line size. Motivation for this classification comes from a result of Weidong Fang and Huffing Li in 1993, that there are only finitely many non-trivial point-imprimitive, linetransitive linear spaces for a given value of gcd（k, v - 1）. The classification strengthens the classification by Camina and Mischke under the much stronger restriction k ≤ 8： no additional examples arise. The paper provides the backbone for future computer-based classifications of point-imprimitive, line- transitive linear spaces with small parameters. Several suggestions for further investigations are made.     

On some new generalized difference sequence spaces defined by a sequence of moduli

In this paper, we define the new generalized difference sequence spaces [V, λ, F, p, q]₀(Δ _v ^m ), [V, λ, F, p, q]₁(Δ _v ^m ) and [V, λ, F, p, q]_∞(Δ _v ^m ). We also study some inclusion relations between these spaces.     

On Connected [g,f +1]-Factors in Graphs

Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G), and g and f two positive integral functions from V (G) to Z⁺-{1} such that g(v) ≤ f(v) ≤ d_G(v) for all v ∈V (G), where d_G(v) is the degree of the vertex v. It is shown that every graph G, including both a [g,f]-factor and a hamiltonian path, contains a connected [g,f +1]-factor. This result also extends Kano’s conjecture concerning the existence of connected [k,k+1]-factors in graphs. * The work of this author was supported by NSFC of China under Grant No. 10271065, No. 60373025. † The work of these authors was also supported in part by the US Department of Energy’s Genomes to Life program (http://doegenomestolife.org/) under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org) and by National Science Foundation (NSF/DBI-0354771,NSF/ITR-IIS-0407204).     

On the maximum number of fixed points in automorphisms of prime order of 2-(v,k,1) designs

In this paper, we study 2-(v, k, 1) designs with automorphisms of prime orderp, having the maximum possible number of fixed points. We prove an upper bound on the number of fixed points, and we study the structure of designs in which this bound is met with equality (such a design is called ap-MFP(v, k)). Several characterizations and asymptotic existence results forp-MFP(v, k) are obtained. For (p, k)=(3,3), (5,5), (2,3) and (3,4), necessary and sufficient conditions onv are obtained for the existence of ap-MFP(v, k). Further, for 3≤k≤5 and for any primep≡1 modk(k−1), we establish necessary and sufficient conditions onv for the existence of ap-MFP(v, k).     

Diskontinuierliche Bewegungsgruppen verschiedenen Grades in metrischen Räumen

Because of new applications, the research of discontinuous groups with respect to different geometries has made considerable progress. One can state that conditions which all characterize the same discontinuous motion groups in Euclidean spaces of the same finite dimension define different classes of discontinuous transformation groups in other geometries. Moreover in the following section 2, sixteen conditions are discribed which define only eight conditions in metric spaces (section 3). Finally, there are results about new classes of so-called D_i — and D _i -discontinuous motion groups of the Euclidean geometry.     

A short proof of Totten's classification of restricted linear spaces

A restricted linear space is one which satisfies (b–v)²v, where b is the number of lines and v is the number of points. In 1976, Totten classified all restricted linear spaces as being of essentially three types. In this paper we give a short, self-contained proof of this result. Our approach is greatly simplified by the use of techniques from linear algebra.This work was supported in part by National Science Foundation Grant MCS-8217596.     

Graph Connectivity After Path Removal

Let G be a graph and u, v be two distinct vertices of G. A u—v path P is called nonseparating if G—V(P) is connected. The purpose of this paper is to study the number of nonseparating u—v path for two arbitrary vertices u and v of a given graph. For a positive integer k, we will show that there is a minimum integer (k) so that if G is an (k)-connected graph and u and v are two arbitrary vertices in G, then there exist k vertex disjoint paths P ₁[u,v], P ₂[u,v], . . ., P _k [u,v], such that G—V (P _i [u,v]) is connected for every i (i = 1, 2, ..., k). In fact, we will prove that (k) 22k+2. It is known that (1) = 3.. A result of Tutte showed that (2) = 3. We show that (3) = 6. In addition, we prove that if G is a 5-connected graph, then for every pair of vertices u and v there exists a path P[u, v] such that G—V(P[u, v]) is 2-connected.* Supported by NSF grant No. DMS-0070059 Supported by ONR grant N00014-97-1-0499 Supported by NSF grant No. 9531824     

Distance and fractional isomorphism in Steiner triple systems

In [8], Quattrochi and Rinaldi introduced the idea ofn ⁻¹-isomorphism between Steiner systems. In this paper we study this concept in the context of Steiner triple systems. The main result is that for any positive integerN, there existsv ₀(N) such that for all admissiblev≥v ₀(N) and for each STS(v) (sayS), there exists an STS(v) (sayS′) such that for somen>N, S is strictlyn ⁻¹-isomorphic toS′. We also prove that for all admissiblev≥13, there exist two STS(v)s which are strictly 2⁻¹-isomorphic. Define the distance between two Steiner triple systemsS andS′ of the same order to be the minimum volume of a tradeT which transformsS into a system isomorphic toS′. We determine the distance between any two Steiner triple systems of order 15 and, further, give a complete classification of strictly 2⁻¹-isomorphic and 3⁻¹-isomorphic pairs of STS(15)s.     

A recursive construction for Room designs

It is shown that if there is a Room design of sidev ₁ and a Room design of sidev ₂ containing a subdesign of sidev ₃, then there exists a design of side v₁ (v₂ — v₃)+v₃, provided thats = v ₂ — v₃ 6. Further, ifs 0, each of the 3 initial designs is isomorphic to a subdesign of the resultant design. It is also shown that there exist Room designs of sidev for all Fermat primesv > 65537.     

Point-primitive linear spaces with number of points being a product of two primes

This work is a part of the general program to classify point-primitive finite linear spaces. Let 𝒮 be a non-trivial finite regular linear space with mp points and G≤Aut(𝒮) be point-primitive, here m and p are two primes with m≤p. In this paper, we give a classification of the pairs (G,𝒮). For a small positive integer k≥3 and a non-regular transitive group G on 𝒫, where |𝒫| = v, we also present an algorithm to sift all 2-(v,k,1) designs with point-set 𝒫, and admitting G as an automorphism group.