An Inequality Involving the Local Eigenvalues of a Distance-Regular Graph

Let denote a distance-regular graph with diameter D 3, valency k, and intersection numbers a _i, b _i, c _i. Let X denote the vertex set of and fix x X. Let denote the vertex-subgraph of induced on the set of vertices in X adjacent X. Observe has k vertices and is regular with valency a ₁. Let _{1 2} ··· _k denote the eigenvalues of and observe ₁ = a ₁. Let denote the set of distinct scalars among ₂, ₃, ..., _k . For let mult denote the number of times appears among ₂, ₃,..., _k . Let denote an indeterminate, and let p ₀, p₁, ...,p _D denote the polynomials in [] satisfying p ₀ = 1 andp _i = c _i+1 p _i+1 + (a _i – c _i+1 + c _i)p _i + b _i p _i–1 (0 i D – 1),where p _–1 = 0. We show where we abbreviate = –1 – b ₁(1+)^–1. Concerning the case of equality we obtain the following result. Let T = T(x) denote the subalgebra of Mat _X ( ) generated by A, E*₀, E*₁, ..., E* _D , where A denotes the adjacency matrix of and E* _i denotes the projection onto the ith subconstituent of with respect to X. T is called the subconstituent algebra or the Terwilliger algebra. An irreducible T-module W is said to be thin whenever dimE* _i W 1 for 0 i D. By the endpoint of W we mean min{i|E* _i W 0}. We show the following are equivalent: (i) Equality holds in the above inequality for 1 i D – 1; (ii) Equality holds in the above inequality for i = D – 1; (iii) Every irreducible T-module with endpoint 1 is thin.     

Quadratic spline interpolation on uniform meshes

The interpolation problem at uniform mesh points of a quadratic splines(x _i)=f _i,i=0, 1,...,N ands(x ₀)=f₀ is considered. It is known that s–f=O(h ³) and s–f=O(h ²), whereh is the step size, and that these orders cannot be improved. Contrary to recently published results we prove that superconvergence cannot occur for any particular point independent off other than mesh points wheres=f by assumption. Best error bounds for some compound formulae approximatingf _i andf _i ⁽³⁾ are also derived.     

On theA 0-acceptability of rational approximations to the exponential function with only real poles

We consider rational approximations to the exponential function with real poles, ₁ ^–1 ,..., _m ^–1 , that correspond to implicit Runge-Kutta collocation methods. We show that if _i 1/2,i=1,...,m, the rational approximation isA ₀-acceptable.     

A new smoothing-regularization approach for a maximum-likelihood estimation problem

We consider the problem min _i=1 ^m (aⁱ,x–b_iloga ⁱ, z) subject tox 0 which occurs as a maximum-likelihood estimation problem in several areas, and particularly in positron emission tomography. After noticing that this problem is equivalent to mind(b, Ax) subject tox 0, whered is the Kullback-Leibler information divergence andA, b are the matrix and vector with rows and entriesa ⁱ,b _i, respectively, we suggest a regularized problem mind(b, Ax) + d(v, Sx), where is the regularization parameter,S is a smoothing matrix, andv is a fixed vector. We present a computationally attractive algorithm for the regularized problem, establish its convergence, and show that the regularized solutions, as goes to 0, converge to the solution of the original problem which minimizes a convex function related tod(v, Sx). We give convergence-rate results both for the regularized solutions and for their functional values.The research of A. N. Iusem was partially supported by CNPq Grant No. 301280/86-MA.     

On Connected Resolving Decompositions in Graphs

For an ordered k-decomposition of a connected graph G and an edge e of G, the -code of e is the k-tuple where d(e, G _i) is the distance from e to G _i. A decomposition is resolving if every two distinct edges of G have distinct -codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dim _d (G). A resolving decomposition of G is connected if each G _i is connected for 1 i k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 dim _d (G) cd(G) m for every connected graph G of size m 2. All nontrivial connected graphs of size m with connected decomposition number 2 or m have been characterized. We present characterizations for connected graphs of size m with connected decomposition number m – 1 or m – 2. It is shown that each pair s, t of rational numbers with 0 < s t 1, there is a connected graph G of size m such that dim _d (G)/m = s and cd(G)/m = t.     

Highly linked graphs

A graph with at least 2k vertices is said to bek-linked if, for any choices ₁,...,s _k ,t ₁,...,t _k of 2k distinct vertices there are vertex disjoint pathsP ₁,...,P _k withP _i joinings _i tot _i , 1ik. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds . We show here thatk(G)22k will do.     

On the Fine Structure of Stationary Measures in Systems Which Contract-on-Average

Suppose {f ₁,...,f _m } is a set of Lipschitz maps of ^d . We form the iterated function system (IFS) by independently choosing the maps so that the map f _i is chosen with probability p _i ( ^m _i=1 p _i =1). We assume that the IFS contracts on average. We give an upper bound for the upper Hausdorff dimension of the invariant measure induced on ^d and as a corollary show that the measure will be singular if the modulus of the entropy _i p _i log p _i is less than d times the modulus of the Lyapunov exponent of the system. Using a version of Shannon's Theorem for random walks on semigroups we improve this estimate and show that it is actually attainable for certain cases of affine mappings of .     

Monotone subsequences in (0, 1)-matrices

A (0, 1)-matrix contains anS ₀(k) if it has 0-cells (i, j ₁), (i + 1,j ₂),..., (i + k – 1,j _k) for somei andj ₁ < ... < j_k, and it contains anS ₁(k) if it has 1-cells (i ₁,j), (i ₂,j + 1),...,(i _k ,j + k – 1) for somej andi ₁ < ... <i _k . We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS ₀(k) isk ₀ m, thenM must have anS ₁(k) withk m/(k ₀ + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS ₀(k) (in the cells on or below the main diagonal) isk ₀ m, thenM has anS ₁(k) withk m/(k ₀ + 1). Moreover, these results are best-possible.     

A Note on Regular Near Polygons

Let be a regular near polygon of order (s,t) with s>1 and t3. Let d be the diameter of , and let r:= max{i(c_i,a_i,b_i)=(c₁,a₁,b₁)}. In this note we prove several inequalities for . In particular, we show that s is bounded from above by function in t if We also consider regular near polygons of order (s,3).This work was partly supported by the Grant-in-Aid for Scientific Research (No 14740072), the Ministry of Education, Culture, Sports, Science and Technology, JapanThis work was partly done when the author was at the Com²MaC center at the Pohang University of Science and Technology. He would like to thank the Com²MaC-KOSEF for its support     

A scaling technique for finding the weighted analytic center of a polytope

Let a bounded full dimensional polytope be defined by the systemAx b whereA is anm × n matrix. Leta _i denote theith row of the matrixA, and define theweighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function – _i=1 ^m w _i ln(a _i ^T x –b _i ). The proper selection of weightsw _i can make any desired point in the interior of the polytope become the weighted analytic center. As a result, the weighted analytic center has applications in both linear and general convex programming. For simplicity we assume that the weights are positive integers.If some of thew _i 's are much larger than others, then Newton's method for minimizing the resulting barrier function is very unstable and can be very slow. Previous methods for finding the weighted analytic center relied upon a rather direct application of Newton's method potentially resulting in very slow global convergence. We present a method for finding the weighted analytic center that is based on the scaling technique of Edmonds and Karp and is an enhancement of Newton's method. The scaling algorithm runs in iterations, wherem is the number of constraints defining the polytope andW is the largest weight given on any constraint. Each iteration involves taking a step in the Newton direction and its complexity is dominated by the time needed to solve a system of linear equations.Supported by the Campus Research Board, University of Illinois at Urbana-Champaign.Supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

On quadratic spline interpolation

Using the quadratic spline interpolates(x) fitting the data (x _i,y _i), 0in and satisfying the end conditions_o=y_o, we give formulae approximatingy andy at selected knots by orders up toO(h ⁴).     

Subsets of a Hilbert space,having finite hausdorff dimension

Let X₂, X₂ be Hilbert spaces, X₂ X₁, X₂ is dense in X₁, the imbedding is compact,m X₂, dim_H ⁱ m and h⁽ⁱ⁾(m) are the Hausdorff dimension and the limit capacity (information dimension) of the setm with respect to the metrics of the spaces X_i (i=1, 2). Two examples are constructed. 1) An example of a setm bounded in X₂, such that: a) h⁽¹⁾(m) < (and, consequently, dim_H ¹ m); b)m cannot be covered by a countable collection of sets, compact in X₂ (and, consequently, dim_H ² m=). 2) an Example of a setm, compact in X₂, such that h⁽¹⁾(m) < and h⁽²⁾(m)=.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 163, pp. 154–165, 1987.     

A class of path-valued Markov processes and its applications to superprocesses

Summary Let ( _s ) be a continuous Markov process satisfying certain regularity assumptions. We introduce a path-valued strong Markov process associated with ( _s ), which is closely related to the so-called superprocess with spatial motion ( _s ). In particular, a subsetH of the state space of ( _s ) intersects the range of the superprocess if and only if the set of paths that hitH is not polar for the path-valued process. The latter property can be investigated using the tools of the potential theory of symmetric Markov processes: A set is not polar if and only if it supports a measure of finite energy. The same approach can be applied to study sets that are polar for the graph of the superprocess. In the special case when ( _s ) is a diffusion process, we recover certain results recently obtained by Dynkin.     

Convex interpolating splines of arbitrary degree II

For given data {(x _i ,y _i )} _i=0 ⁿ , (x ₀<x ₁<...<x _n ) we consider the possibility of finding a spline functions of arbitrary degreek+1 (k 1) with preassigned smoothnessl, where 1 l [(k+1)/2]. The splines should be such thats(x _i )=y _i ,i=0, 1,...,n ands is increasing and convex on [x ₀,x _n ]. Sufficient conditions which guarantee the existence ofs and an explicit formula for this function are derived.     

Some coinductive graphs

Summary LetT be a universal theory of graphs such that Mod(T) is closed under disjoint unions. Let _T be a disjoint union _i such that each _i is a finite model ofT and every finite isomorphism type in Mod(T) is represented in{ _i i<3}. We investigate under what conditions onT, Th( _T ) is a coinductive theory, where a theory is called coinductive if it can be axiomatizated by -sentences. We also characterize coinductive graphs which have quantifier-free rank 1.     

Bounds of eigenvalues of a graph

LetG be a simple graph withn vertices. We denote by _i(G) thei-th largest eigenvalue ofG. In this paper, several results are presented concerning bounds on the eigenvalues ofG. In particular, it is shown that –1₂(G)(n–2)/2, and the left hand equality holds if and only ifG is a complete graph with at least two vertices; the right hand equality holds if and only ifn is even andG2K _n/2.     

Convergence in Distribution of Products of I.I.D. Nonnegative Matrices

Let (X _i) be a sequence of m × m i.i.d. stochastic matrices with distribution . Then ⁿ is the distribution of X _n X _n–1 ...X ₁. Simple sufficient conditions for the weak convergence of ( ⁿ ) are presented here. An extremely simple (and verifiable) necessary and sufficient condition is provided for m= 3. The method for m= 3 works for m> 3 even though calculations are more involved for higher values of m. We also discuss the purity of the limit distribution for m2.     

Une famille remarquable de suites recurrentes lineaires

Letu(n) be a recurrent sequence of rational integers, i.e.,u(n+s)+a _s–1 u(n+s–1)+...+a ₀ u(n)=0,n0,a _i,i=0,...,s–1. The polynomialP(x)=x ^s +a _s–1x^s +...+a ₀ is the companion or the characteristic polynomial of the recurrence. It is known that if none of the ratios of the roots ofP is a root of unity, then the setA={n,u(n)=0} is finite. A recent result of F. Beukers shows that ifs=3, then the setA has at most 6 elements and there exists, up to trivial transformations, only one recurrence of order 3 with 6 zeros, found by J. Berstel. In this paper, we construct for eachs, s2 a recurrent sequence of orders, with at leasts ²/2+s/2–1 zeroes, which generalize Berstel's sequence.