On the extendability of steiner t-designs

Necessary and sufficient conditions for the extendability of residual designs of Steiner systems S(t,t + 1,v) are studied. In particular, it is shown that a residual design with respect to a single point is uniquely extendable, and the extendability of a residual design with respect to a pair of points is equivalent to a bipartition of the block graph of a related design. © 1993 John Wiley & Sons, Inc.     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

Some characterization of locally resistant BIB designs of degree one

Summary This paper investigates locally resistant balanced incomplete block (LRBIB) designs of degree one. A new necessary condition for the existence of such an LRBIB design is presented. This condition yields a complete characterization of affine α-resolvable LRBIB designs of degree one. Furthermore, regarding construction methods of LRBIB designs of degree one, it is shown that Shah and Gujarathi's method (1977,Sankhy?, B39, 406–408) yields the same parameters as Hedayat and John's method (1974,Ann. Statist.,2, 148–158), but their block structures are different and interesting. Partially supported by Grants 59540043 (C) and 60530014 (C).     

A family of non class-regular symmetric transversal designs of spread type

Many classes of symmetric transversal designs have been constructed from generalized Hadamard matrices and they are necessarily class regular. In (Hiramine, Des Codes Cryptogr 56:21–33, 2010) we constructed symmetric transversal designs using spreads of \mathbbZ_p²ⁿ{\mathbb{Z}_p^{2n}} with p a prime. In this article we show that most of them admit no class regular automorphism groups. This implies that they are never obtained from generalized Hadamard matrices. As far as we know, this is the first infinite family of non class-regular symmetric transversal designs.     

Estimating a bounded parameter for symmetric distributions

For the problem of estimating under squared error loss the parameter of a symmetric distribution which is subject to an interval constraint, we develop general theory which provides improvements on various types of inadmissible procedures, such as maximum likelihood procedures. The applications and further developments given include: (i) symmetric location families such as the exponential power family including double-exponential and normal, Student and Cauchy, a Logistic type family, and scale mixture of normals in cases where the variance is lower bounded; (ii) symmetric exponential families such as those related to a Binomial(n,p) model with bounded |p−1/2| and to a Beta(α + θ, α −θ) model; and (iii) symmetric location distributions truncated to an interval (−c,c). Finally, several of the dominance results are studied with respect to model departures yielding robustness results, and specific findings are given for scale mixture of normals and truncated distributions. Research supported by NSERC of Canada.     

On the structure of 1-designs with at most two block intersection numbers

We introduce the notion of an unrefinable decomposition of a 1-design with at most two block intersection numbers, which is a certain decomposition of the 1-designs collection of blocks into other 1-designs. We discover an infinite family of 1-designs with at most two block intersection numbers that each have a unique unrefinable decomposition, and we give a polynomial-time algorithm to compute an unrefinable decomposition for each such design from the family. Combinatorial designs from this family include: finite projective planes of order n; SOMAs, and more generally, partial linear spaces of order (s, t) on (s + 1)² points; as well as affine designs, and more generally, strongly resolvable designs with no repeated blocks.      

H-designs with the properties of resolvability or (1, 2)-resolvability

An H-design is said to be (1, α)-resolvable, if its block set can be partitioned into α-parallel classes, each of which contains every point of the design exactly α times. When α = 1, a (1, α)-resolvable H-design of type g ⁿ is simply called a resolvable H-design and denoted by RH(g ⁿ ), for which the general existence problem has been determined leaving mainly the case of g ≡ 0 (mod 12) open. When α = 2, a (1, 2)-RH(1 ⁿ ) is usually called a (1, 2)-resolvable Steiner quadruple system of order n, for which the existence problem is far from complete. In this paper, we consider these two outstanding problems. First, we prove that an RH(12 ⁿ ) exists for all n ≥ 4 with a small number of possible exceptions. Next, we give a near complete solution to the existence problem of (1, 2)-resolvable H-designs with group size 2. As a consequence, we obtain a near complete solution to the above two open problems.     

Infinite families of non-embeddable quasi-residual hadamard designs

LetD be a quasi-residual Hadamard design with =(2m + 1)2ⁿ–1, wherem andn are positive integers. IfD contains a pair of blocks intersecting in m2ⁿ⁺¹ points together with a third block intersecting each of the first two blocks in (m + 1)2ⁿ points thenD is non-embeddable. Using this result together with a recursive construction for quasi-residual Hadamard designs the existence of a previously unknown infinite family of non-embeddable quasi-residual Hadamard designs with =5(2ⁿ)–1 is established. An additional infinite family of non-embeddable quasi-residual Hadamard designs is given. This family has = 2ⁿ–1 with each design in the family having a pair of blocks meeting in (3 + 3)/4 points and a third block meeting each of the first two blocks in (5 + 5)/8 points.     

Partial regularity for weak solutions of a nonlinear elliptic equation

For scalar non-linear elliptic equations, stationary solutions are defined to be critical points of a functional with respect to the variations of the domain. We consideru a weak positive solution of −Δu=u ^α in -Δu=u ^α in Ω ⊂ ℝ ⁿ , which is stationary. We prove that the Hausdorff dimension of the singular set ofu is less thann−2α+1/α−1, if α≥n+2/n−2.     

Quasi-symmetric 2, 3, 4-designs

Quasi-symmetric designs are block designs with two block intersection numbersx andy It is shown that with the exception of (x, y)=(0, 1), for a fixed value of the block sizek, there are finitely many such designs. Some finiteness results on block graphs are derived. For a quasi-symmetric 3-design with positivex andy, the intersection numbers are shown to be roots of a quadratic whose coefficients are polynomial functions ofv, k and λ. Using this quadratic, various characterizations of the Witt—Lüneburg design on 23 points are obtained. It is shown that ifx=1, then a fixed value of λ determines at most finitely many such designs.     

Exponential number of quasi-symmetric SDP designs and codes meeting the Grey-Rankin bound

It is shown that quasi-symmetric designs which are derived or residual designs of nonisomorphic symmetric designs with the symmetric difference property are also nonisomorphic. Combined with a result by W. Kantor, this implies that the number of nonisomorphic quasi-symmetric designs with the symmetric difference property grows exponentially. The column spaces of the incidence matrices of these designs provide an exponential number of inequivalent codes meeting the Grey-Rankin bound. A transformation of quasi-symmetric designs by means of maximal arcs is described. In particular, a residual quasi-symmetric design with the symmetric difference property is transformed into a quasi-symmetric design with the same block graph but higher rank over GF(2).Dedicated to Professor Hanfried Lenz on the occasion of his 75th birthday.This paper was written while the author was at the University of Giessen as a Research Fellow of the Alexander von Humboldt Foundation, on leave from the University of Sofia, Bulgaria.     

Simple vertices of maximal minor polytopes

Themaximal minor polytope Π _{m, n} is the Newton polytope of the product of all maximal minors of anm×n matrix of indeterminates. The family of polytopes {Π _{m, n} } interpolates between the symmetric transportation polytope (form=n−1) and the permutohedron (form=2). Both transportation polytope and the permutohedron aresimple polytopes but in general Π _{m, n} is not simple. The main result of this paper is an explicit construction of a class of simple vertices of Π _{m, n} for generalm andn. We call themvertices of diagonal type. For every such vertexv we explicitly describe all the edges and facets of Π _{m, n} which containv. Simple vertices of Π _{m, n} have an interesting algebro-geometric application: they correspond tononsingular extreme toric degenerations of the determinantal variety ofm×n matrices not of full rank. Andrei Zelevinsky was partially supported by the NSF under Grant DMS-9104867.     

On linguistic dynamical systems,families of graphs of large girth,and cryptography

The paper is devoted to the study of a linguistic dynamical system of dimension n ≥ 2 over an arbitrary commutative ring K, i.e., a family F of nonlinear polynomial maps f _α : K ⁿ → K ⁿ depending on “time” α ∈ {K − 0} such that f _α ⁻¹ = f _−αM, the relation f _α1 (x) = f _α2 (x) for some x ∈ Kⁿ implies α₁ = α₂, and each map f _α has no invariant points. The neighborhood {f _α (υ)∣α ∈ K − {0}} of an element v determines the graph Γ(F) of the dynamical system on the vertex set Kⁿ. We refer to F as a linguistic dynamical system of rank d ≥ 1 if for each string a = (α₁, υ, α₂), s ≤ d, where α_i + α_i+1 is a nonzero divisor for i = 1, υ, d − 1, the vertices υ _a = f _α1 × ⋯ × f _αs (υ) in the graph are connected by a unique path. For each commutative ring K and each even integer n ≠= 0 mod 3, there is a family of linguistic dynamical systems L_n(K) of rank d ≥ 1/3n. Let L(n, K) be the graph of the dynamical system L_n(q). If K = F_q, the graphs L(n, F_q) form a new family of graphs of large girth. The projective limit L(K) of L(n, K), n → ∞, is well defined for each commutative ring K; in the case of an integral domain K, the graph L(K) is a forest. If K has zero divisors, then the girth of K drops to 4. We introduce some other families of graphs of large girth related to the dynamical systems L_n(q) in the case of even q. The dynamical systems and related graphs can be used for the development of symmetric or asymmetric cryptographic algorithms. These graphs allow us to establish the best known upper bounds on the minimal order of regular graphs without cycles of length 4n, with odd n ≥ 3. Bibliography: 42 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 214–234.     

Block separation in solvable groups

If π is a set of primes, a finite group G is block π-separated if for every two distinct irreducible complex characters α, β ∈ Irr(G) there exists a prime p ∈ π such that α and β lie in different Brauer p-blocks. A group G is block separated if it is separated by the set of prime divisors of |G|. Given a set π with n different primes, we construct an example of a solvable π-group G which is block separated but it is not separated by every proper subset of π. Received: 22 December 2004     

Cross-ratio distortion and Douady-Earle extension: II. Quasiconformality and asymptotic conformality are local

Let f be an orientation-preserving circle homeomorphism and Φ the Douady-Earle extension of f. In this paper, we show that the quasiconformality and asymptotic conformality of Φ are local properties; i.e., if f is quasisymmetric or symmetric on an arc of the unit circle, then Φ is quasiconformal or asymptotically conformal nearby. Furthermore, our methods enable us to conclude the global quasiconformality and asymptotic conformality from local properties. In the quasiconformal case, our methods also enable us to provide an upper bound for the maximal dilatation of Φ on a neighborhood of the arc in the open unit disk in terms of the cross-ratio distortion norm of f on the arc.     

On Minimal Defining Sets of Full Designs and Self-Complementary Designs, and a New Algorithm for Finding Defining Sets of t-Designs

A defining set of a t-(v, k, λ) design is a partial design which is contained in a unique t-design with the given parameters. A minimal defining set is a defining set, none of whose proper partial designs is a defining set. This paper proposes a new and more efficient algorithm that finds all non-isomorphic minimal defining sets of a given t-design. The complete list of minimal defining sets of 2-(6, 3, 6) designs, 2-(7, 3, 4) designs, the full 2-(7, 3, 5) design, a 2-(10, 4, 4) design, 2-(10, 5, 4) designs, 2-(13, 3, 1) designs, 2-(15, 3, 1) designs, the 2-(25, 5, 1) design, 3-(8, 4, 2) designs, the 3-(12, 6, 2) design, and 3-(16, 8, 3) designs are given to illustrate the efficiency of the algorithm. Also, corrections to the literature are made for the minimal defining sets of four 2-(7, 3, 3) designs, two 2-(6, 3, 4) designs and the 2-(21, 5, 1) design. Moreover, an infinite class of minimal defining sets for 2-((v) || 3){v\choose3} designs, where v ≥ 5, has been constructed which helped to show that the difference between the sizes of the largest and the smallest minimal defining sets of 2-((v) || 3){v\choose3} designs gets arbitrarily large as v → ∞. Some results in the literature for the smallest defining sets of t-designs have been generalized to all minimal defining sets of these designs. We have also shown that all minimal defining sets of t-(2n, n, λ) designs can be constructed from the minimal defining sets of their restrictions when t is odd and all t-(2n, n, λ) designs are self-complementary. This theorem can be applied to 3-(8, 4, 3) designs, 3-(8, 4, 4) designs and the full 3-(8 || 4)3-{8 \choose 4} design using the previous results on minimal defining sets of their restrictions. Furthermore we proved that when n is even all (n − 1)-(2n, n, λ) designs are self-complementary.     

Partial geometries pg (s, t, 2) with an abelian Singer group and a characterization of the van Lint-Schrijver partial geometry

Let be a proper partial geometry pg(s,t,2), and let G be an abelian group of automorphisms of acting regularly on the points of . Then either t≡2±od s+1 or is a pg(5,5,2) isomorphic to the partial geometry of van Lint and Schrijver (Combinatorica 1 (1981), 63–73). This result is a new step towards the classification of partial geometries with an abelian Singer group and further provides an interesting characterization of the geometry of van Lint and Schrijver.The author is Postdoctoral Fellow of the Fund for Scientific Research Flanders (FWO-Vlaanderen).     

Almost Symmetric Cycles in Large Digraphs

We prove that every digraph D with n≥7, n≥+6 vertices and at least (n−k−1)(n−1)+k(k+1) arcs contains all symmetric cycles of length at most n−k−2, an almost symmetric cycle of length n−k−1, and with some exceptions, also an almost symmetric cycle of length n−k. Consequently, D contains all orientations of cycles of length at most n−k, unless D is an exception. The research was partially supported by the AGH University of Science and Technology grant No 11 420 04     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

A family of balanced incomplete‐block designs with repeated blocks on which general linear groups act

We give two constructions of a balanced incomplete‐block design discovered by van Lint: the design has parameters (13,39,15,5,5), and has repeated blocks and an automorphism group of order 240. One of these methods can be generalized to produce a large class of designs with the properties of the title. © 2006 Wiley Periodicals, Inc. J Combin Designs