Some cyclic BIBDs with block size four

In this paper we give some results on cyclic BIBDs with block size 4. It is proved that a cyclic B(4,1;4ⁿ u) exists where u is a product of primes congruent to 1 modulo 6 and n is a positive integer and n ≥ 3. In the case of n = 2, we also give some partial results on the existence of a cyclic B(4,1;4²u) where u is a product of primes congruent to 1 modulo 6. © 2004 Wiley Periodicals, Inc.     

Existence of large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ (denoted by LS (2ⁿ4¹)) were first studied by Schellenberg and Stinson and motivated by their connection with perfect threshold schemes. It is known that such large sets can exist only for n ≡ 0 (mod 3) and do exist for any n ? {12, 36, 48, 144} ∪ {m > 6 : m ≡ 6,30 (mod 36)}. In this paper, we show that an LS (2^{12k + 6}4¹) exists for any k ≠ 2. So, the existence of LS (2ⁿ4¹) is almost solved with five possible exceptions n ∈ {12, 30, 36, 48, 144}. This solution is based on the known existence results of S (3, 4, v)s by Hanani and special S (3, {4, 6}, 6m)s by Mills. Partitionable H (q, 2, 3, 3) frames also play an important role together with a special known LS (2¹⁸4¹) with a subdesign LS (2⁶4¹). © 2004 Wiley Periodicals, Inc.     

Symmetric block bases of sequences with large average growth

We show that if 0<ε≦1, 1≦p<2 andx ₁, …,x _n is a sequence of unit vectors in a normed spaceX such thatE ‖∑ _l ⁿ ε_i x _l‖≧n ^1/p, then one can find a block basisy ₁, …,y _m ofx ₁, …,x _n which is (1+ε)-symmetric and has cardinality at leastγn ^2/p-1(logn)⁻¹, where γ depends on ε only. Two examples are given which show that this bound is close to being best possible. The first is a sequencex ₁, …,x _n satisfying the above conditions with no 2-symmetric block basis of cardinality exceeding 2n ^2/p-1. This sequence is not linearly independent. The second example is a sequence which satisfies a lowerp-estimate but which has no 2-symmetric block basis of cardinality exceedingCn ^2/p-1(logn)^4/3, whereC is an absolute constant. This applies when 1≦p≦3/2. Finally, we obtain improvements of the lower bound when the spaceX containing the sequence satisfies certain type-condition. These results extend results of Amir and Milman in [1] and [2]. We include an appendix giving a simple counterexample to a question about norm-attaining operators.     

Simple 3‐designs of PSL(2, 2n) with block size 7

In this paper, we determine the number of the orbits of 7‐subsets of with a fixed orbit length under the action of PSL(2, 2ⁿ). As a consequence, we determine the distribution of λ for which there exists a simple 3‐(2ⁿ + 1, 7, λ) design with PSL(2, 2ⁿ) as an automorphism group. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 1–17, 2008     

Existence of HPMDs with block size five

In this article, it is shown that the necessary condition for the existence of a holey perfect Mendelsohn design (HPMD) with block size 5 and type hⁿ, namely, n ≥ 5 and n(n - 1)hⁿ ≡ 0 (mod 5), is also sufficient, except possibly for a few cases. The results of this article guarantee the analogous existence results for group divisible designs (GDDs) of group-type hⁿ with block size k = 5 and having index λ = 4. Moreover, some more conclusive results for the existence of (v, 5, 1)-perfect Mendelsohn designs (PMDs) are also mentioned. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 257–273, 1997     

Path numbers of tournaments

A family of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of | | over all path decompositions of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n/2 k n²/4, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)/2 pn(T) (n² − 1)/4. Moreover, if k is an integer satisfying (i) (n + 1)/2 k n − 1 or (ii) n < k (n² − 1)/4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n k < (n² − 1)/4.     

Existence of directed GDDs with block size five

In this article, we construct directed group divisible designs (DGDDs) with block size five, group-type hⁿ, and index unity. The necessary conditions for the existence of such a DGDD are n ≥ 5, (n − 1)h ≡ 0 (mod 2) and n(n − 1)h² ≡ 0 (mod 10). It is shown that these necessary conditions are also sufficient, except possibly for n = 15 where h ≡ 1 or 5 (mod 6) and h ≢ 0 (mod 5), or (n, h) = (15, 9). © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 389–402, 1998     

Symmetric block bases in finite-dimensional normed spaces

It is shown that for 1 ≦p < ∞, any basisC-equivalent to the unit vector basis ofl _p ⁿ has a (1 + ε)-symmetric block basis of cardinality proportional ton/logn. When 1 <p < ∞, an upper bound proportional ton log logn/logn is also obtained. These results extend results of Amir and Milman in [2].     

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     

Further results on large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ were first studied by Schellenberg and Stinson because of their connection with perfect threshold schemes. It is known that such large sets can exist only for n ≡0 (mod 3) and do exist for all odd n ≡ (mod 3) and for even n=24m, where m odd ≥ 1. In this paper, we show that such large sets exist also for n=2^k(3m), where m odd≥ 1 and k≥ 5. To accomplish this, we present two quadrupling constructions and two tripling constructions for a special large set called ^*LS(2ⁿ). © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 24–35, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10032     

Covering cliques with spanning bicliques

The edges of the complete graph on n vertices can be covered by ⌈lg n⌉ spanning complete bipartite subgraphs. However, the sum of the number of edges in these subgraphs is roughly (n²/4)lg n, while a cover consisting of n − 1 spanning stars uses only (n − 1)² edges. We will show that the covering by spanning stars has the smallest total number of edges among all coverings of the clique by spanning complete bipartite subgraphs, except when n is 4 or 8. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 223–227, 1998     

Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs

Forn points in three-dimensional Euclidean space, the number of unit distances is shown to be no more thancn ^8/5. Also, we prove that the number of furthest-neighbor pairs forn points in 3-space is no more thancn ^8/5, provided no three points are collinear. Both these results follow from the following incidence relation of spheres and points in 3-space. Namely, the number of incidences betweenn points andt spheres is at mostcn ^4/5 t ^4/5 if no three points are collinear andn ^3/2>t>n ^1/4. The proof is based on a point-and-line incidence relation established by Szemerédi and Trotter. Analogous versions for higher dimensions are also given.     

Balanced incomplete block designs with block size 8

The necessary conditions for the existence of a balanced incomplete block design on υ ≥ k points, with index λ and block size k, are that: For k = 8, these conditions are known to be sufficient when λ = 1, with 38 possible exceptions, the largest of which is υ = 3,753. For these 38 values of υ, we show (υ, 8, λ ) BIBDs exist whenever λ > 1 for all but five possible values of υ, the largest of which is υ = 1,177, and these five υ's are the only values for which more than one value of λ is open. For λ>1, we show the necessary conditions are sufficient with the definite exception of two further values of υ, and the possible exception of 7 further values of υ, the largest of which is υ=589. In particular, we show the necessary conditions are sufficient for all λ> 5 and for λ = 4 when υ ≠ 22. We also look at (8, λ) GDDs of type 7^m. Our grouplet divisible design construction is also refined, and we construct and exploit α ‐ frames in constructing several other BIBDs. In addition, we give a PBD basis result for {n: n ≡ 0, 1; mod 8, n ≥ 8}, and construct a few new TDs with index > 1. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 233–268, 2001     

Large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ have been studied by Schellenberg, Chen, Lindner and Stinson. These large sets have applications in cryptography in the construction of perfect threshold schemes. It is known that such large sets can exist only for n ≡ 0 (mod 3) and do exist for n = 6 and for all n = 3^k, k ≥ 1. In this paper, we present new recursive constructions and use them to show that such large sets exist for all odd n ≡ 0 (mod 3) and for even n = 24m, where m odd ≥ 1. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 285–296, 2001     

Size ramsey numbers of stars versus 4‐chromatic graphs

We investigate the asymptotics of the size Ramsey number î(K_1,nF), where K_1,n is the n‐star and F is a fixed graph. The author 11 has recently proved that r?(K_1,n,F)=(1+o(1))n² for any F with chromatic number χ(F)=3. Here we show that r?(K_1,n,F)≤ n²+o(n²), if χ (F) ≥ 4 and conjecture that this is sharp. We prove the case χ(F)=4 of the conjecture, that is, that r?(K_1,n,F)=(4+o(1))n² for any 4‐chromatic graph F. Also, some general lower bounds are obtained. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 220–233, 2003     

Combinatorics of RNA Hairpins and Cloverleaves

For an abstract single-stranded RNA, a combinatorial analysis is given for two important structures, hairpins and cloverleaves. The number of possible hairpins is O(2ⁿ), while the number of possible three-petal cloverleaves is O(n³2ⁿ), and the number of possible general cloverleaves is O((2.21)ⁿ).     

The complexity of many cells in arrangements of planes and related problems

We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m ^2/3 n logn +n ²); we can calculatem such cells specified by a point in each, in worst-case timeO(m ^2/3 n log³ n+n ² logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m ^2/3 n logn+n ²), but this number is onlyO(m ^3/5– n ^4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m ^3/4– n ^3/4+3 +m) log² n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m ^3/4– n ^3/4+3 +m] log² n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m ^2/3 n ^d/3 logn+n ^d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.     

On the minimality of polygon triangulation

The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simplen-gon is equal ton+2w –d – 2, wherew is the number of holes andd is the maximum number of independent degenerate triangles of then-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-freen-gon. The algorithm takesO(nlog² n+DK ²) time, whereD is the maximum number of vertices lying on the same line in then-gon andK is the number of minimally degenerate triangles of then-gon.     

Three enumeration formulas of standard Young tableaux of truncated shapes

In this paper we consider the enumeration of three kinds of standard Young tableaux (SYT) of truncated shapes by use of the method of multiple integrals. A product formula for the number of truncated shapes of the form (n^m, n ? r)\δ_k–1 is given, which implies that the number of SYT of truncated shape (n², 1)\(1) is the number of level steps in all 2-Motzkin paths. The number of SYT with three rows truncated by some boxes ((n + k)³)\(k) is discussed. Furthermore, the integral representation of the number of SYT of truncated shape (n^m)\(3, 2) is derived, which implies a simple formula of the number of SYT of truncated shape (nⁿ)\(3, 2).