1-Homogeneous Graphs with Cocktail Party μ-Graphs

Let be a graph with diameter d 2. Recall is 1-homogeneous (in the sense of Nomura) whenever for every edge xy of the distance partition{{z V() | (z, y) = i, (x, z) = j} | 0 i, j d}is equitable and its parameters do not depend on the edge xy. Let be 1-homogeneous. Then is distance-regular and also locally strongly regular with parameters (v,k,,), where v = k, k = a ₁, (v – k – 1) = k(k – 1 – ) and c ₂ + 1, since a -graph is a regular graph with valency . If c ₂ = + 1 and c ₂ 1, then is a Terwilliger graph, i.e., all the -graphs of are complete. In [11] we classified the Terwilliger 1-homogeneous graphs with c ₂ 2 and obtained that there are only three such examples. In this article we consider the case c ₂ = + 2 3, i.e., the case when the -graphs of are the Cocktail Party graphs, and obtain that either = 0, = 2 or is one of the following graphs: (i) a Johnson graph J(2m, m) with m 2, (ii) a folded Johnson graph J¯(4m, 2m) with m 3, (iii) a halved m-cube with m 4, (iv) a folded halved (2m)-cube with m 5, (v) a Cocktail Party graph K _{m × 2} with m 3, (vi) the Schläfli graph, (vii) the Gosset graph.     

Rates of convergence for the stability of large order statistics

Forr1 and eachnr, letM _nr be therth largest ofX ₁,X ₂, ...,X _n , where {X _n ,n1} is an i.i.d. sequence. Necessary and sufficient conditions are presented for the convergence of for all >0 and some –1, where {a _n } is a real sequence. Furthermore, it is shown that this series converges for all >–1, allr1 and all >0 if it converges for some >–1, somer1 and all >0.     

Extremes of a Gaussian Process and the Constant H α

Consider a triangular array of standard Gaussian random variables {_n,i, i 0, n 1} such that {_n,i, i 0} is a stationary normal sequence for each n 1. Let _n,k = corr(_n,i,_n,i+k). If (1-_n,k)log n _k (0,) as n for some k, then the locations where the extreme values occur cluster and the limiting distribution of the maxima is still the Gumbel distribution as in the stationary or i.i.d. case, but shifted by a parameter measuring the clustering. Triangular arrays of Gaussian sequences are used to approximate a continuous Gaussian process X(t), t 0. The cluster behavior of the random sequence refers to the behavior of the extremes values of the continuous process. The relation is analyzed. It reveals a new definition of the constants H used for the limiting distribution of maxima of continuous Gaussian processes and provides further understanding of the limit result for these extremes.     

On the Size of a Cap in PG(n,q) with q Even and n ≥ 3

Let m2(n,q), m2(n,q) be, respectively, the maximum value, the second largest value of k for which there exists a complete k-cap in PG(n,q). In this paper, the known upper bound on m2(3,q), q even, q 8, is improved. This new upper bound on m2(3,q) is then used to improve the upper bounds on m2(n,q), q even, q 8 and n 4.     

Some best possible bounds concerning the traces of finite sets II

LetX be ann-element set and be a family of its subsets. Consider the family _x = {F – {x} : F } for a givenx X. We write(m, n) (m – k, n – 1), when for all with || m, there exists an elementx ofX such that| _x| m – k. We show that (m, n) (m – 10,n – 1) for allm 5n and (m, n) (m – 13,n – 1) for allm 29n/5.     

On properties of the probabilistic constrained linear programming problem and its dual

In this paper, the two problems inf{inf{cx:x R ⁿ,A ₁ xy,A ₂ xb}:y suppF R ^m,F(y)p} and sup{inf{uy:y suppF R ^m,F(y)p}+vb:uA ₁+vA ₂=c, (u,v0} are investigated, whereA ₁,A ₂,b,c are given matrices and vectors of finite dimension,F is the joint probability distribution of the random variables ₁,..., _m, and 0<p<1. The first problem was introduced as the deterministic equivalent and the second problem was introduced as the dual of the probabilistic constrained linear programming problem inf{cx:P(A ₁ x)p,A ₂ xb}.b}. Properties of the sets and the functions involved in the two problems and regularity conditions of optimality are discussed.     

On the Embedding of an Affine Space into a Projective Space

Let k, K be fields, and assume that |k| 4 and n, m 2, or |k| = 3 and n 3, m 2. Then, for any embedding of AG(n, k) into PG(m, K), there exists an isomorphism from k into K and an (n+1) × (m+1) matrix B with entries in K such that can be expressed as (x₁,x₂,...,x_n) = [(1,x₁ ,x₂ ,...,x_n )B], where the right-hand side is the equivalence class of (1,x₁ ,x₂ ,...,x_n )B. Moreover, in this expression, is uniquely determined, and B is uniquely determined up to a multiplication of element of K*. Let l 1, and suppose that there exists an embedding of AG(m+l, k) into PG(m, K) which has the above expression. If we put r = dim _k K, then we have r 3 and m > 2 l-1)/(r-2). Conversely, there exists an embedding of AG(l+m, k) into PG(m, K) with the above expression if K is a cyclic extension of k with dim _k K=r 3, and if m 2l/(r-2) with m even or if m 2l/(r-2) +1 with m odd.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

A parallel projection method for overdetermined nonlinear systems of equations

We consider overdetermined nonlinear systems of equationsF(x)=0, whereF: ^{n m} ,mn. For this type of systems we define weighted least square distance (WLSD) solutions, which represent an alternative to classical least squares solutions and to other solutions based on residual normas. We introduce a generalization of the classical method of Cimmino for linear systems and we prove local convergence results. We introduce a practical strategy for improving the global convergence properties of the method. Finally, numerical experiments are presented.Work supported by FAPESP (Grant 90/3724/6), FINEP, CNPq and FAEP-UNICAMP.     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

Taut Distance-Regular Graphs of Odd Diameter

Let denote a bipartite distance-regular graph with diameter D 4, valency k 3, and distinct eigenvalues ₀ > ₁ > ··· > _D. Let M denote the Bose-Mesner algebra of . For 0 i D, let E _i denote the primitive idempotent of M associated with _i . We refer to E ₀ and E _D as the trivial idempotents of M. Let E, F denote primitive idempotents of M. We say the pair E, F is taut whenever (i) E, F are nontrivial, and (ii) the entry-wise product E F is a linear combination of two distinct primitive idempotents of M. We show the pair E, F is taut if and only if there exist real scalars , such that _{i + 1 i + 1} – _{i – 1 i – 1} = _i ( _{i + 1} – _{i – 1}) + _i ( _{i + 1} – _{i – 1}) + (1 i D – 1)where ₀, ₁, ..., _D and ₀, ₁, ..., _D denote the cosine sequences of E, F, respectively. We define to be taut whenever has at least one taut pair of primitive idempotents but is not 2-homogeneous in the sense of Nomura and Curtin. Assume is taut and D is odd, and assume the pair E, F is taut. We show

On a Singular Semilinear Elliptic Boundary Value Problem and the Boundary Harnack Principle

On a bounded C ²-domain we consider the singular boundary-value problem 1/2u=f(u) in D, u _D =, where d3, f:(0,)(0,) is a locally Hölder continuous function such that f(u) as u0 at the rate u ^–, for some (0,1), and is a non-negative continuous function satisfying certain growth assumptions. We show existence of solutions bounded below by a positive harmonic function, which are smooth in D and continuous in . Such solutions are shown to satisfy a boundary Harnack principle.     

Arithmetic Properties of Summands of Partitions

Let d d, d2 2. We prove that for almost all partitions of an integer the parts are well distributed in residue classes mod d. The limitations of the uniformity of this distribution are also studied.     

On the number of nowhere zero points in linear mappings

LetA be a nonsingularn byn matrix over the finite fieldGF _q ,k=n/2,q=p ^a ,a1, wherep is prime. LetP(A,q) denote the number of vectorsx in (GF _q ) ⁿ such that bothx andAx have no zero component. We prove that forn2, and ,P(A,q)[(q–1)(q–3)] ^k (q–2) ^n–2k and describe all matricesA for which the equality holds. We also prove that the result conjectured in [1], namely thatP(A,q)1, is true for allqn+23 orqn+14.     

On complexity of subset interconnection designs

Given a setX and subsetsX ₁,...,X _m, we consider the problem of finding a graphG with vertex setX and the minimum number of edges such that fori=1,...,m, the subgraphG _i; induced byX _i is connected. Suppose that for any pointsx ₁,...,x X, there are at mostX _i 's containing the set {x₁,...,x }. In the paper, we show that the problem is polynomial-time solvable for ( 2, 2) and is NP-hard for (3,=1), (=l,6), and (2,3).Support in part by the NSF under grant CCR-9208913 and CCR-8920505.Part work was done while this author was visiting at DIMACS and on leave from Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing.     

On the optimality of a characterization theorem for the gamma function using the multiplication formula

Summary The following Artin type characterization of : _{+ +} is proved: Assume thatf: _{+ +} satisfies the Gauss multiplication formula for some fixedp 2,f is absolutely continuous on [l/p, 1 + ] for some > 0 and lim _{x 0} xf(x) = 1. Thenf(x) = (x) forx > 0.The optimality of this result is checked by means of counterexamples. For instance, it is shown that the result is no longer true, if f is absolutely continuous is replaced by f is continuous and of finite variation.     

On the smoothness of the moduli space of mathematical instanton bundles

In this paper we prove that the moduli spaces MI _2n+1(k) of mathematical instanton bundles on ²ⁿ⁺¹ with quantum number k are singular for n 2 and k 3 ,giving a positive answer to a conjecture made by Ancona and Ottaviani in 1993.     

Complete stability of large order statistics

Fix an integerr1. For eachnr, letM _nr be the rth largest ofX ₁,...,X _n, where {X _n,n1} is a sequence of i.i.d. random variables. Necessary and sufficient conditions are given for the convergence of _n=r n P[|M _nr /a _n –1|<] for every >0, where {a _n} is a real sequence and –1. Moreover, it is shown that if this series converges for somer1 and some >–1, then it converges for everyr1 and every >–1.     

The Logarithmic Frequency of Values of Additive Functions

We consider the weak convergence of distribution functions (_mx 1/ m)^-1 _{m x},f_x(m)x is a set (x 2) of strongly additive functions such that f_x(p){0,1} for each prime number p.     

Convolution semigroups and central limit theorem associated with a dual convolution structure

We consider hypergroups associated with Jacobi functions ⁽⁾ (x), (–1/2). We prove the existence of a dual convolution structure on [0,+[i(]0,s ₀]{{) =++1,s ₀=min(,–+1). Next we establish a Lévy-Khintchine type formula which permits to characterize the semigroup and the infinitely divisible probabilities associated with this dual convolution, finally we prove a central limit theorem.