A Proof of the Jungnickel-Tonchev Conjecture on Quasi-Multiple Quasi-Symmetric Designs

A proof of the following conjecture of Jungnickel and Tonchev on quasi-multiple quasi-symmetric designs is given: Let D be a design whose parameter set (v,b,r,k,) equals (v,sv,sk,k, s) for some positive integer s and for some integers v,k, that satisfy (v-1) = k(k-1) (that is, these integers satisfy the parametric feasibility conditions for a symmetric (v,k,)-design). Further assume that D is a quasi-symmetric design, that is D has at most two block intersection numbers. If (k, (s-1)) = 1, then the only way D can be constructed is by taking multiple copies of a symmetric (v,k, )-design.     

Quasi-symmetric 3-designs with triangle-free graph

The following result is proved: Let D be a quasi-symmetric 3-design with intersection numbers x, y(0x<y<k). D has no three distinct blocks such that any two of them intersect in x points if and only if D is a Hadamard 3-design, or D has a parameter set (v, k, ) where v=(+2)(²+4+2)+1, k=²+3+2 and =1,2,..., or D is a complement of one of these designs.     

Designs on vector spaces constructed using quadratic forms

Let N be the set of nonnegative integers, let , t, v be in N and let K be a subset of N, let V be a v-dimensional vector space over the finite field GF(q), and let W _Kbe the set of subspaces of V whose dimensions belong to K. A t-[v, K, ; q]-design on V is a mapping : W _K N such that for every t-dimensional subspace, T, of V, we have (B)=. We construct t-[v, {t, t+1}, ; q-designs on the vector space GF(q ^v) over GF(q) for t2, v odd, and q ^t(q–1)² equal to the number of nondegenerate quadratic forms in t+1 variables over GF(q). Moreover, the vast majority of blocks of these designs have dimension t+1. We also construct nontrivial 2-[v, k, ; q]-designs for v odd and 3kv–3 and 3-[v, 4, q ⁶+q ⁵+q ⁴; q]-designs for v even. The distribution of subspaces in the designs is determined by the distribution of the pairs (Q, a) where Q is a nondegenerate quadratic form in k variables with coefficients in GF(q) and a is a vector with elements in GF(q ^v) such that Q(a)=0.This research was partly supported by NSA grant #MDA 904-88-H-2034.     

Abelian Difference Sets Without Self-conjugacy

We obtain some results that are useful to the study of abelian difference sets and relative difference sets in cases where the self-conjugacy assumption does not hold. As applications we investigate McFarland difference sets, which have parameters of the form v=q^d+1( q^d+ q^d-1 +...+ q+2) ,k=q^d( q^d+q^d-1+...+q+1) , = q^d ( q^(d-1)+q^(d-2)+...+q+1), where q is a prime power andd a positive integer. Using our results, we characterize those abelian groups that admit a McFarland difference set of order k- = 81. We show that the Sylow 3-subgroup of the underlying abelian group must be elementary abelian. Our results fill two missing entries in Kopilovich's table with answer no.     

Sensitivity analysis of the greatest eigenvalue of a symmetric matrix via the ɛ-subdifferential of the associated convex quadratic form

LetA(·) be ann × n symmetric affine matrix-valued function of a parameteruR ^m , and let (u) be the greatest eigenvalue ofA(u). Recently, there has been interest in calculating (u), the subdifferential of atu, which is useful for both the construction of efficient algorithms for the minimization of (u) and the sensitivity analysis of (u), namely, the perturbation theory of (u). In this paper, more generally, we investigate the Legendre-Fenchel conjugate function of (·) and the -subdifferential (u) of atu. Then, we discuss relations between the set (u) and some perturbation bounds for (u).The author is deeply indebted to Professor J. B. Hiriart-Urruty who suggested this study and provided helpful advice and constant encouragement. The author also thanks the referees and the editors for their substantial help in the improvement of this paper.     

Systematic Construction of <Emphasis Type="Italic">q</Emphasis>-Analogs of <Emphasis Type="Italic">t</Emphasis>−(<Emphasis Type="Italic">v</Emphasis>,<Emphasis Type="Italic">k</Emphasis>,λ)-Designs

In the present paper we consider a q-analog of t–(v,k,)-designs. It is canonic since it arises by replacing sets by vector spaces over GF(q), and their orders by dimensions. These generalizations were introduced by Thomas [Geom.Dedicata vol. 63, pp. 247–253 (1996)] they are called t –(v,k,;q)- designs. A few of such q-analogs are known today, they were constructed using sophisticated geometric arguments and case-by-case methods. It is our aim now to present a general method that allows systematically to construct such designs, and to give complete catalogs (for small parameters, of course) using an implemented software package. &nbsp; In order to attack the (highly complex) construction, we prepare them for an enormous data reduction by embedding their definition into the theory of group actions on posets, so that we can derive and use a generalization of the Kramer-Mesner matrix for their definition, together with an improved version of the LLL-algorithm. By doing so we generalize the methods developed in a research project on t –(v,k,)-designs on sets, obtaining this way new results on the existence of t–(v,k,;q)-designs on spaces for further quintuples (t,v,k,;q) of parameters. We present several 2–(6,3,;2)-designs, 2–(7,3,;2)-designs and, as far as we know, the very first 3-designs over GF(q).classification 05B05     

Limit theorems for multitype continuous time Markov branching processes

Summary Let X(t)=(X ₁ (t), X ₂ (t), , X _t (t)) be a k-type (2k<) continuous time, supercritical, nonsingular, positively regular Markov branching process. Let M(t)=((m _ij (t))) be the mean matrix where m _ij (t)=E(X _j (t)¦X _r (0)= _ir for r=1, 2, , k) and write M(t)=exp(At). Let be an eigenvector of A corresponding to an eigenvalue . Assuming second moments this paper studies the limit behavior as t of the stochastic process . It is shown that i) if 2 Re >₁, then · X(t)e{–t¦ converges a.s. and in mean square to a random variable. ii) if 2 Re ₁ then [ · X(t)] f(v · X(t)) converges in law to a normal distribution where f(x)=(x) ^–1 if 2 Re <₁ and f(x)=(x log x)^–1 if 2 Re =₁, ₁ the largest real eigenvalue of A and v the corresponding right eigenvector.Research supported in part under contracts N0014-67-A-0112-0015 and NIH USPHS 10452 at Stanford University.     

Block-Transitive Point-Imprimitive t-Designs

We study block-transitive point-imprimitive t–(v, k, ) designs. It was showed by Cameron and Praeger that in such designs t = 2 or 3. In 1989, Delandtsheer and Doyen proved that a block-transitive point-imprimitive 2-design satisfies v (( ^k ₂)–1)². In this paper, we give a proof of the Cameron–Praeger conjecture which states that for t = 3 the stronger inequality v ( ^k ₂)+1 holds. We find two infinite families of 3-designs for which this bound is met. We also show that the above designs cannot have = 1, and that = 2 is possible only if v attains its maximal value, and various other restrictions are met.     

Difference Sets with n = 2pm

Let D be a (v,k,) difference set over an abelian group G with even n = k - . Assume that t N satisfies the congruences t q _i ^fi (mod exp(G)) for each prime divisor q_i of n/2 and some integer f_i. In [4] it was shown that t is a multiplier of D provided that n > , (n/2, ) = 1 and (n/2, v) = 1. In this paper we show that the condition n > may be removed. As a corollary we obtain that in the case of n= 2p^a when p is a prime, p should be a multiplier of D. This answers an open question mentioned in [2].     

The Lattice of Interpretability Types of Cantor Varieties

For integers 1 m < n, a Cantor variety with m basic n-ary operations _i and n basic m-ary operations _k is a variety of algebras defined by identities _k(₁( ), ... , _m( )) = _k and i(₁( ), ... ,_n( )) = y _i, where = (x ₁., ... , x _n) and = (y ₁, ... , y _m). We prove that interpretability types of Cantor varieties form a distributive lattice, , which is dual to the direct product ₁ × ₂ of a lattice, ₁, of positive integers respecting the natural linear ordering and a lattice, ₂, of positive integers with divisibility. The lattice is an upper subsemilattice of the lattice of all interpretability types of varieties of algebras.     

An Extension of the Roots Separation Theorem

Let T _n be an n×n unreduced symmetric tridiagonal matrix with eigenvalues ₁<₂<< _n and W _k is an (n–1)×(n–1) submatrix by deleting the kth row and the kth column from T _n , k=1,2,...,n. Let _{12 n–1} be the eigenvalues of W _k . It is proved that if W _k has no multiple eigenvalue, then ₁<₁<₂<₂<< _n–1< _n–1< _n ; otherwise if _i = _i+1 is a multiple eigenvalue of W _k , then the above relationship still holds except that the inequality _i < _i+1< _i+1 is replaced by _i = _i+1= _i+1.     

Locally forced critical surface waves in channels of arbitrary cross section

Critical long surface waves forced by locally distributed external pressure applied on the free surface in channels of arbitrary cross section are studied in this paper. The fluid under consideration is inviscid and has constant density. The upstream flow is uniform and the upstream velocity is assumed to be near critical, i.e.,u ₀=u _c ++0(²), where 0<1 andu _c is the critical velocity determined by the geometry of the channel. The external pressure applied on the free surface as the forcing is ² P(x). Then the first order perturbation of the free surface elevation satisfies a forced Korteweg-de Vries equation (fK-dV). It is shown in this paper that: (i) If (supercritical), the stationaryfK-dV has two cusped solitary wave solutions; (ii) if (subcritical), the stationaryfK-dV has a downstream cnoidal wave solution; (iii) when= _L , the unique stationary solution of thefK-dV is a wave free hydraulic fall; (iv) if= _d =– _L , thefK-dV has a jump solution; and (v) if _L << _c , thefK-dV does not have stationary solutions. Some free surface profiles and bifurcation diagrams are presented.     

Small potential corrections for the discrete eigenvalues of the Sturm-Liouville problem

Summary The inverse Sturm-Liouville problem is the problem of finding a good approximation of a potential functionq such that the eigenvalue problem (^*)–y +qy=y holds on (0, ) fory(0)=y()=0 and a set of given eigenvalues . Since this problem has to be solved numerically by discretization and since the higher discrete eigenvalues strongly deviate from the corresponding Sturm-Liouville eigenvalues , asymptotic corrections for the 's serve to get better estimates forq. Let _k (1kn) be the first eigenvalues of (^*), let _k be the corresponding discrete eigenvalues obtained by the finite element method for (^*) and let _{k k} for the special caseq=0. Then, starting from an asymptotic correction technique proposed by Paine, de Hoog and Anderssen, new estimates for the errors of the corrected discrete eigenvalues are obtained and confirm and improve the knownO(kh ²)(h:=/(n+1)) behaviour. The estimates are based on new Sobolev inequalities and on Fourier analysis and it is shown that for 4+c ₂ k(n+1)/2, wherec ₁ andc ₂ are constants depending onq which tend to 0 for vanishingq.     

A technique for constructing divisible difference sets

An (m, n, k, ₁,₂) divisible difference set in a groupG of ordermn relative to a subgroupN of ordern is ak-subsetD ofG such that the list {xy^–1:x, y D} contains exactly ₁ copies of each nonidentity element ofN and exactly ₂ copies of each element ofG N. It is called semi-regular ifk > ₁ and k²=mn₂. We develop a method for constructing a divisible difference set as a product of a difference set and a relative difference set or a difference set and a subset ofG which we call a relative divisible difference set. The method results in several parametrically new families of semi-regular divisible difference sets.     

On eigenfunctions of nonlinear heat generation

Summary We consider the equation u+ expu=0, >0,u(boundary)0 in the formv= exp (K,v), whereK ^–1=–. We give bounds on for the latter equation to be solvable by the contraction mapping principle, and estimate theL ² norm of the solution so obtained. We also give a bound on for the topological index of the solution to be non-zero and apply Krasnoselskii's results to the least squares method of approximating the solution.

---

Sommario Consideriamo l'equazione u+ expu=0, >0,u(frontiera)=0 nella formav= exp (Kv), doveK ^–1=–. In questo lavoro diamo limitazioni per per cui la seconda equazione e risolubile col metodo delle contrazioni, e diamo una stima della norma inL ² della soluzione cosi ottenuta. Diamo anche una limitazione per per cui l'indice topologico della soluzione diventa non zero, e applichiamo i risultati di Krasnoselskii al metodo dei minimi quadrati per approssimare la soluzione.

     

A survey of pseudo (v,k, λ)-designs

This work is an attempt to give a complete survey of all known results about pseudo (v, k, )-designs. In doing this, the author hopes to bring more attention to his conjecture given in Section 6; an affirmative answer to this conjecture would settle completely the existence and construction problem for a pseudo (v, k, )-design in terms of the existence of an appropriate (v, k, )-design.     

A nonlinear equation for linear programming

We present a characterization of the normal optimal solution of the linear program given in canonical form max{c ^tx: Ax = b, x 0}. (P) We show thatx ^* is the optimal solution of (P), of minimal norm, if and only if there exists anR > 0 such that, for eachr R, we havex ^* = (rc – A^t_r)₊. Thus, we can findx ^* by solving the following equation for _r A(rc – A^t_r)₊ = b. Moreover,(1/r) _r then converges to a solution of the dual program.On leave from The University of Alberta, Edmonton, Canada. Research partially supported by the National Science and Engineering Research Council of Canada.     

On graphical partitions

An integer partition {₁,₂,..., _v } is said to be graphical if there exists a graph with degree sequence _i . We give some results corcerning the problem of deciding whether or not almost all partitions of even integer are non-graphical. We also give asymptotic estimates for the number of partitions with given rank.     

Estimation of the Intensity of the Flow of Nonmonotone Refusals in the Queuing System (≤ λ)/G/m

We consider a queuing system ()/G/m, where the symbol () means that, independently of prehistory, the probability of arrival of a call during the time interval dtdoes not exceed dt. The case where the queue length first attains the level r m+ 1 during a busy period is called the refusal of the system. We determine a bound for the intensity ₁(t) of the flow of homogeneous events associated with the monotone refusals of the system, namely, ₁(t) = O( ^{r+ 1}₁ ^{m– 1} _{r– m+ 1}), where _k is the kth moment of the service-time distribution.     

A preconditioner for constrained and weighted least squares problems with Toeplitz structure

We study methods for solving the constrained and weighted least squares problem min _x by the preconditioned conjugate gradient (PCG) method. HereW = diag (₁, , _m ) with _{1 m} 0, andA ^T = [T ₁ ^T , ,T _k ^T ] with Toeplitz blocksT _l R ^{n × n} ,l = 1, ,k. It is well-known that this problem can be solved by solving anaugmented linear 2 × 2 block linear systemM +Ax =b, A ^T = 0, whereM =W ^–1. We will use the PCG method with circulant-like preconditioner for solving the system. We show that the spectrum of the preconditioned matrix is clustered around one. When the PCG method is applied to solve the system, we can expect a fast convergence rate.Research supported by HKRGC grants no. CUHK 178/93E and CUHK 316/94E.