Maximum uniformly resolvable designs with block sizes 2 and 4

A central question in design theory dating from Kirkman in 1850 has been the existence of resolvable block designs. In this paper we will concentrate on the case when the block size k=4. The necessary condition for a resolvable design to exist when k=4 is that v≡4mod12; this was proven sufficient in 1972 by Hanani, Ray-Chaudhuri and Wilson [H. Hanani, D.K. Ray-Chaudhuri, R.M. Wilson, On resolvable designs, Discrete Math. 3 (1972) 343-357]. A resolvable pairwise balanced design with each parallel class consisting of blocks which are all of the same size is called a uniformly resolvable design, a URD. The necessary condition for the existence of a URD with block sizes 2 and 4 is that v≡0mod4. Obviously in a URD with blocks of size 2 and 4 one wishes to have the maximum number of resolution classes of blocks of size 4; these designs are called maximum uniformly resolvable designs or MURDs. So the question of the existence of a MURD on v points has been solved for by the result of Hanani, Ray-Chaudhuri and Wilson cited above. In the case this problem has essentially been solved with a handful of exceptions (see [G. Ge, A.C.H. Ling, Asymptotic results on the existence of 4-RGDDs and uniform 5-GDDs, J. Combin. Des. 13 (2005) 222-237]). In this paper we consider the case when and prove that a exists for all u≥2 with the possible exception of u∈{2,7,9,10,11,13,14,17,19,22,31,34,38,43,46,47,82}.     

Class‐uniformly resolvable designs

We investigate Class‐Uniformly Resolvable Designs, which are resolvable designs in which each of the resolution classes has the same number of blocks of each size. We derive the fully general necessary conditions including a number of extremal bounds. We present two general constructions. We primarily consider the case of block sizes 2 and 3, where we find two infinite extremal families and finish two other infinite families by difference constructions. We present tables showing the current state of knowledge in the case of block size 2 and 3 for all orders up to 200. © 2001 John Wiley & Sons, Inc. J Combin Designs 8: 79–99, 2001     

Constructions for rotational near resolvable block designs

A (ν, k, k?1) near resolvable block design (NRBD) is r‐rotational over a group G if it admits G as an automorphism group of order (ν?1)/r fixing exactly one point and acting semiregularly on the others. We give direct and recursive constructions for rotational NRBDs with particular attention to 1‐rotational ones. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 157–181, 2001     

On the length of the tail of a vector space partition

A vector space partition of a finite dimensional vector space V=V(n,q) of dimension n over a finite field with q elements, is a collection of subspaces U₁,U₂,…,U_t with the property that every non zero vector of V is contained in exactly one of these subspaces. The tail of consists of the subspaces of least dimension d₁ in , and the length n₁ of the tail is the number of subspaces in the tail. Let d₂ denote the second least dimension in .Two cases are considered: the integer q^d₂−d₁ does not divide respective divides n₁. In the first case it is proved that if 2d₁>d₂ then n₁≥q^d₁+1 and if 2d₁≤d₂ then either n₁=(q^d₂−1)/(q^d₁−1) or n₁>2q^d₂−d₁. These lower bounds are shown to be tight and the elements in the subspaces in tails of minimal length will constitute a subspace of V of dimension 2d₁ respectively d₂.In case q^d₂−d₁ divides n₁ it is shown that if d₂<2d₁ then n₁≥q^d₂−q^d₁+q^d₂−d₁ and if 2d₁≤d₂ then n₁≥q^d₂. The last bound is also shown to be tight.The results considerably improve earlier found lower bounds on the length of the tail.     

Uniformly resolvable designs with index one and block sizes three and four — with three or five parallel classes of block size four

Each parallel class of a uniformly resolvable design (URD) contains blocks of only one block size. A URD with v points and with block sizes three and four means that at least one parallel class has block size three and at least one has block size four. Danziger [P. Danziger, Uniform restricted resolvable designs with r=3, ARS Combin. 46 (1997) 161-176] proved that for all there exist URDs with index one, some parallel classes of block size three, and exactly three parallel classes with block size four, except when v=12 and except possibly when . We extend Danziger’s work by showing that there exists a URD with index one, some parallel classes with block size three, and exactly three parallel classes with block size four if, and only if, , v≠12. We also prove that there exists a URD with index one, some parallel classes of block size three, and exactly five parallel classes with block size four if, and only if, , v≠12. New labeled URDs, which give new URDs as ingredient designs for recursive constructions, are the key in the proofs. Some ingredient URDs are also constructed with difference families.     

The spectrum of α‐resolvable designs with block size four

Abstact: An α‐resolvable BIBD is a BIBD with the property that the blocks can be partitioned into disjoint classes such that every class contains each point of the design exactly α times. In this paper, we show that the necessary conditions for the existence of α‐resolvable designs with block size four are sufficient, with the exception of (α, ν, λ) = (2, 10, 2). © 2000 John Wiley & Sons, Inc. J Combin Designs 9: 1–16, 2001     

Partitions of finite vector spaces into subspaces

Let V_n(q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V_n(q) is a partition of V_n(q) if every nonzero element of V_n(q) is contained in exactly one element of . Suppose there exists a partition of V_n(q) into x_i subspaces of dimension n_i, 1 ≤ i ≤ k. Then x₁, …, x_k satisfy the Diophantine equation . However, not every solution of the Diophantine equation corresponds to a partition of V_n(q). In this article, we show that there exists a partition of V_n(2) into x subspaces of dimension 3 and y subspaces of dimension 2 if and only if 7x + 3y = 2ⁿ ? 1 and y ≠ 1. In doing so, we introduce techniques useful in constructing further partitions. We also show that partitions of V_n(q) induce uniformly resolvable designs on qⁿ points. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 329–341, 2008     

Uniformly resolvable designs with index one, block sizes three and five and up to five parallel classes with blocks of size five

Each parallel class of a uniformly resolvable design (URD) contains blocks of only one block size k (denoted k-pc). The number of k-pcs is denoted r_k. The necessary conditions for URDs with v points, index one, blocks of size 3 and 5, and r₃,r₅>0, are . If r_k>1, then v≥k², and r₃=(v−1−4⋅r₅)/2. For r₅=1 these URDs are known as group divisible designs. We prove that these necessary conditions are sufficient for r₅=3 except possibly v=105, and for r₅=2,4,5 with possible exceptions (v=105,165,285,345) New labeled frames and labeled URDs, which give new URDs as ingredient designs for recursive constructions, are the key in the proofs.     

On t‐designs and s‐resolvable t‐designs from hyperovals

Hyperovals in projective planes turn out to have a link with t‐designs. Motivated by an unpublished work of Lonz and Vanstone, we present a construction for t‐designs and s‐resolvable t‐designs from hyperovals in projective planes of order $2^n$. We prove that the construction works for $t\le 5$. In particular, for $t=5$ the construction yields a family of 5‐ $\left(2^n+2,8,70\left(2^{n?2}?1\right)\right)$ designs. For $t=4$ numerous infinite families of 4‐designs on $2^n+2$ points with block size $2k$ can be constructed for any $k\ge 4$. The construction assumes the existence of a 4‐ $\left(2^{n?1}+1,k,\lambda \right)$ design, called the indexing design, including the complete 4‐ $\left(2^{n?1}+1,k,\left(\genfrac{}{}{0ex}{}{2^{n?1}?3}{k?4}\right)\right)$ design. Moreover, we prove that if the indexing design is s‐resolvable, then so is the constructed design. As a result, many of the constructed designs are s‐resolvable for $s=2,3$. We include a short discussion on the simplicity or non‐simplicity of the designs from hyperovals.     

On uniformly resolvable designs with 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. The cases r ₃ = 1 and r ₄ = 1 correspond to Resolvable Group Divisible Designs (RGDD). We prove that if a 4-RGDD of type h ^u exists then all admissible {3, 4}-URDs with 12hu points exist. In particular, this gives existence for URD with v ≡ 0 (mod 48) points. We also investigate the case of URDs with a fixed number of k -pc. In particular, we show that URDs with r ₃ = 4 exist, and that those with r ₃ = 7, 10 exist, with 11 and 12 possible exceptions respectively, this covers all cases with 1 < r ₃ ≤ 10. Furthermore, we prove that URDs with r ₄ = 7 exist and that those with r ₄ = 9 exist, except when v = 12, 24 and possibly when v = 276. In addition, we prove that there exist 4-RGDDs of types 2 ¹⁴², 2 ³⁴⁶ and 6 ⁵⁴. Finally, we provide four {3,5}-URDs with 105 points.     

Constructions for near resolvable designs and BIBDs

The purpose of this article is twofold. First, it is shown that classical inversive planes of even order can be used to construct a class of 2—(2²ⁿ + 1, 2ⁿ, 2ⁿ—1) near resolvable designs, in which any two blocks have at most 2 points in common. Secondly, it is shown that a recursive construction method for BIBDs using resolvable BIBDs due to Shrikhande and Raghavarao can be extended by using near resolvable designs. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 227–231, 1999     

The alternating algorithm in a uniformly convex and uniformly smooth Banach space

Let X   be a uniformly convex and uniformly smooth Banach space. Assume that the _Mi$M_i$, i=1,…,r$i=1,\dots ,r$, are closed linear subspaces of X  , _PMi$P_{M_i}$ is the best approximation operator to the linear subspace _Mi$M_i$, and M:=_M1+?+_Mr$M:=M_1+?+M_r$. We prove that if M is closed, then the alternating algorithm given by repeated iterations of

(I−_PMr)(I−_PMr−1)?(I−_PM1)$(I-P_{M_r})(I-P_{M_{r-1}})?(I-P_{M_1})$

applied to any x∈X$x\in X$ converges to x−_PMx$x-P_{M}x$, where _PM$P_M$ is the best approximation operator to the linear subspace M  . This result, in the case r=2$r=2$, was proven in Deutsch [4].     

Graphs with the n‐e.c. adjacency property constructed from resolvable designs

Only recently have techniques been introduced that apply design theory to construct graphs with the n‐e.c. adjacency property. We supply a new random construction for generating infinite families of finite regular n‐e.c. graphs derived from certain resolvable Steiner 2‐designs. We supply an extension of our construction to the infinite case, and thereby give a new representation of the infinite random graph. We describe a family of deterministic graphs in infinite affine planes which satisfy the 3‐e.c. property. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 294–306, 2009     

Geometrical constructions of class‐uniformly resolvable structure

We use arcs, ovals, and hyperovals to construct class‐uniformly resolvable structures. Many of the structures come from finite geometries, but we also use arcs from non‐geometric designs. Most of the class‐uniformly resolvable structures constructed here have block size sets that have not been constructed before. We construct CURDs with a variety of block sizes, including many with block sizes 2 and 4. In addition, these constructions give the first systematic way of constructing infinite families of CURDs with three block sizes. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:329‐344, 2011     

区组大小为 4 的二重超单可分解的可分组设计

自 1992 年 Gronau 和 Mullin 提出超单设计的概念以来, 很多研究者参与了超单设计的研究. 超单设计在编码等方面也有广泛的应用. 超单可分组设计是超单设计的重要组成部分. 本文我们主要研究区组大小为4 的二重超单可分解的可分组设计, 并基本解决了此类设计的存在性问题.     

Approximate range searching using binary space partitions

We show how any BSP tree for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size for the segments themselves, such that the range-searching efficiency remains almost the same. We apply this technique to obtain a BSP tree of size O(nlogn) such that -approximate range searching queries with any constant-complexity convex query range can be answered in O(min_>0{(1/)+k}logn) time, where k is the number of segments intersecting the -extended range. The same result can be obtained for disjoint constant-complexity curves, if we allow the BSP to use splitting curves along the given curves.We also describe how to construct a linear-size BSP tree for low-density scenes consisting of n objects in such that -approximate range searching with any constant-complexity convex query range can be done in O(logn+min_>0{(1/^d−1)+k}) time.     

A note on the duality mapping of a locally uniformly convex Banach space

Let X be a real locally uniformly convex Banach space with normalized duality mapping J:X→2^X*. The purpose of this note is to show that for every R>0 and every x₀X there exists a function , which is nondecreasing and such that (r)>0 for r>0,(0)=0 and

for all . Simply, it is shown that the necessity part of the proof of the original analogous necessary and sufficient condition of Prüß, for real uniformly convex Banach spaces, goes over equally well in the present setting. This is a natural setting for the study of many existence problems in accretive and monotone operator theories.     

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.     

A two-dimensional inequality and uniformly continuous retractions

We prove a new inequality valid in any two-dimensional normed space. As an application, it is shown that the identity mapping on the unit ball of an infinite-dimensional uniformly convex Banach space is the mean of n uniformly continuous retractions from the unit ball onto the unit sphere, for every n?3. This last result allows us to study the extremal structure of uniformly continuous function spaces valued in an infinite-dimensional uniformly convex Banach space.