New constructions of divisible designs

A construction is given for a (p^2a(p+1),p²,p^2a+1(p+1),p^2a+1,p^2a(p+1)) (p a prime) divisible difference set in the group H×Z²_pa+1 where H is any abelian group of order p+1. This can be used to generate a symmetric semi-regular divisible design; this is a new set of parameters for λ₁≠0, and those are fairly rare. We also give a construction for a (p^a−1+p^a−2+…+p+2,p^a+2, p^a(p^a+p^a−1+…+p+1), p^a(p^a−1+…+p+1), p^a−1(p^a+…+p²+2)) divisible difference set in the group H×Z_p2×Z^a_p. This is another new set of parameters, and it corresponds to a symmetric regular divisible design. For p=2, these parameters have λ₁=λ₂, and this corresponds to the parameters for the ordinary Menon difference sets.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

An extension theorem for t-designs

In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an S_λ(t,k,v) such that

then there exists an S_λ(v−t+1)(t,k,v+1) having v+1 pairwise disjoint subdesigns S_λ(t,k,v). Moreover, if B_i and B_j are any two blocks belonging to two distinct such subdesigns, then d|B_i∩B_j|<k−h. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an S_λ(t,k,v) such that

where m=min{s,v−k} and n=min{i,t}, then there exists an

having pairwise disjoint subdesigns S_λ(t,k,v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Inverse geophysical problems for some noncompactly supported inhomogeneities

Let[²+k²n(x₁,x₃)]u(x₁,x₂,x₃)=−δ(x₁,y₁δ(x₂,y₂)δ(x₃,y₃) in R³₊. Assume that u(x₁,x₂,x₃=0,y₁,y₂=0,y₃=0,k) is measured at the plane P {x:x₃=0} for all positions of the source on the line y = (y₁,y₂ = 0,y₃ = 0), -∞ < y₁ < ∞, and receiver on the plane(x₁,x₂,x₃ − <x₁,x₂ < ∞, and for low-frequencies 0 < k <k₀, k₀ > 0 is an arbitrary small wave number. Assume thatn(x₁,x₃) is an arbitrary bounded piecewise-continuous function. The basic result is: the above low-frequency surface data determinen(x₁,x₃)uniquely.     

k-Lucas numbers and associated bipartite graphs

For a positive integer k2, the k-Fibonacci sequence {g_n^(k)} is defined as: g₁^(k)==g_k−2^(k)=0, g_k−1^(k)=g_k^(k)=1 and for n>k2, g_n^(k)=g_n−1^(k)+g_n−2^(k)++g_n−k^(k). Moreover, the k-Lucas sequence {l_n^(k)} is defined as l_n^(k)=g_n−1^(k)+g_n+k−1^(k) for n1. In this paper, we consider the relationship between g_n^(k) and l_n^(k) and 1-factors of a bipartite graph.     

Multiple positive solutions for one-dimensional p-Laplacian boundary value problems

By means of the Leggett-Williams fixed-point theorem, criteria are developed for the existence of at least three positive solutions to the one-dimensional p-Laplacian boundary value problem, ((y′))′ + g(t)f(t,y) = 0, y(0) - B₀(y′(0)) = 0, y(1) + B₁(y′(1)) = 0, where (v) |v|^p−2v, p > 1.     

The range of the p-Laplacian

We prove that for λ ≥ 0, p ≥ 3, there exists an open ball B L²(0,1) such that the problem

− (|u′|^p−2 u′)′ − λ|u|^p−2u = f, in (0,1)

, subject to certain separated boundary conditions on (0,1), has a solution for f B.     

The W-convexity and normal structure in banach spaces

Let X be a Banach space, S(X) - x ε X : #x02016; = 1 be the unit sphere of X.The parameter, modulus of W^*-convexity, W^*(ε) = inf <(x − y)/2, f_x> : x, y S(X), x − y ≥ ε, f_x Δ_x , where 0 ≤ ε ≤ 2 and Δ_x S(X^*) be the set of norm 1 supporting functionals of S(X) at x, is investigated_ The relationship among uniform nonsquareness, uniform normal structure and the parameter W^*(ε) are studied, and a known result is improved. The main result is that for a Banach space X, if there is ε, where 0 < ε < 1/2, such that W^*(1 + ε) > ε/2 where W^*(1 + ε) = lim_→ε W^* (1 + ), then X has normal structure.     

ContributionsThe existence of perfect Mendelsohn designs with block size 7

Necessary conditions for existence of a (v,k,λ) perfect Mendelsohn design (or PMD) are v k and λv(v − 1) ≡ 0 mod k. When k = 7, this condition is satisfied if v ≡ 0 or 1 mod 7 and v 7 when λ 0 mod 7 and for all v 7 when λ ≡ 0 mod 7. Bennett, Yin and Zhu have investigated the existence problem for k = 7, λ = 1 and λ even; here we provide several improvements on their results and also investigate the situation for λ odd. We reduce the total number of unknown (v,7,λ)-PMDs to 36,31 for λ = 1 and 5 for λ > 1. In particular, v = 294 is the largest unknown case for λ = 1, and the only unknown cases for λ > 1 are for v = 42, λ [2,3,5,9] and v = 18, λ = 7.     

Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ₁. We consider the power method, i.e. that of choosing a vector v₀ and setting v_k = A^kv₀; then the Rayleigh quotients R_k = (Av_k, v_k)/(v_k, v_k) usually converge to λ₁ as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close R_k is to λ₁. They are both based on a bound on λ₁ − R_k involving the difference of two consecutive Rayleigh quotients and a quantity ω_k. While we do not know how to directly calculate ω_k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ₁ − R_k which is proportional to (λ₂/λ₁)^2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).     

Two theorems on Euclidean distance matrices and Gale transform

We present a characterization of those Euclidean distance matrices (EDMs) D which can be expressed as D=λ(E−C) for some nonnegative scalar λ and some correlation matrix C, where E is the matrix of all ones. This shows that the cones

where is the elliptope (set of correlation matrices) and is the (closed convex) cone of EDMs.

The characterization is given using the Gale transform of the points generating D. We also show that given points , for any scalars λ₁,λ₂,…,λ_n such that

∑_j=1ⁿλ_jp^j=0, ∑_j=1ⁿλ_j=0,

we have

∑_j=1ⁿλ_jpⁱ−p^j2= forall i=1,…,n,

for some scalar independent of i.     

A doubly cyclic channel assignment problem

A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦³) steps.     

Near vector spaces over GF(q) and (v,q+1,1)-BIBD''s

The usual construction of (v,q+1,1)−BIBD's from vector spaces over GF(q) is generalized to the class of near vector spaces over GF(q). It is shown that every (v,q+1,1)−BIBD can be constructed from a near vector space over GF(q). Some corollaries are: Given a (v₁,q+1,1)−BIBD P₁,B₁ and a (v₂,q+1,1)−BIBD P₂,B₂, there is a ((q−1)v₁v₂+v₁+v₂,q+1,1)−BIBD P₃,B₃ containing P₁,B₁ and P₂,B₂ as disjoint subdesigns. If there is a (v,q+1,1)−BIBD then there is a ((q−1)v+1,q,1)−BIBD. Every finite partial (v,q,1)−BIBD can be embedded in a finite (v′,q+1,1)−BIBD.     

q-distributions and Markov processes

We consider a sequence of integer-valued random variables X_n, n 1, representing a special Markov process with transition probability λ_{n, l}, satisfying P_{n, l} = (1 − λ_{n, l}) P_{n−1, l} + λ_{n, l−1} P_{n−1, l−1}. Whenever the transition probability is given by λ_{n, l} = q^{n + βl + γ} and λ_{n, l} = 1 − q^n+βl+γ, we can find closed forms for the distribution and the moments of the corresponding random variables, showing that they involve functions such as the q-binomial coefficients and the q-Stirling numbers. In general, it turns out that the q-notation, up to now mainly used in the theory of q-hypergeometrical series, represents a powerful tool to deal with these kinds of problems. In this context we speak therefore about q-distributions. Finally, we present some possible, mainly graph theoretical interpretations of these random variables for special choices of , β and γ.     

The growth of laguerre matrix polynomials on bounded intervals

Let A be a matrix in ^r×r such that Re(z) > −1/2 for all the eigenvalues of A and let {π_n^(A,1/2) (x)} be the normalized sequence of Laguerre matrix polynomials associated with A. In this paper, it is proved that π_n^(A,1/2) (x) = O(n^(A)/2ln^r−1(n)) and π_n+1^(A,1/2) (x) − π_n^(A,1/2) (x) = O(n^((A)−1)/2ln^r−1(n)) uniformly on bounded intervals, where (A) = max{Re(z); z eigenvalue of A}.     

Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

On the surface viscosity at the boundary between phases

The equations of motion of the interphase boundary are considered. It is shown that the conditions at the surface separating the phases obtained in /1, 2/ by different methods, are identical. The study of the dynamics of the fluid-fluid interface was initiated by Bussinesq /3/ who postulated a linear relationship between the surface stress tensor T_β and the strain rate tensor S_β, assigning two viscosity coefficients to the surface, the dilatation coefficient k (the analog of volume viscosity) and the two-dimensional shear viscosity . In the three-dimensional coordinate system two of whose axes u¹ and usu2 coincide with the axes of any coordinate system at the surface and whose third axis u³ is perpendicular to the surface, his results have the form Tβ = [γ + (k - )θ]a_β + S_β , θ = a^βS_β, V_{, β} = r_{. β} — v_sb_β,      

Non-neutrality of the Stiefel manifolds Vn,k II

The Stiefel manifolds V_2^m−1,k are shown to be non-neutral for m5, 2^m−1+2k=2ℓ<2^m−2.     

Analytic solutions of an iterative functional differential equation

This paper is concerned with a functional differential equation x^′(z)=1/x(az+bx(z)), where a, b are two complex numbers. By constructing a convergent power series solution y(z) of a auxiliary equation of the form b²y^′(z)=(y(μ²z)−ay(μz))(μy^′(μz)−ay^′(z)), analytic solutions of the form for the original differential equation are obtained.