Markov chains on hypercubes: Spectral representations and several majorization relations

Various Markov chains on hypercubes ??are considered and their spectral representations are presentend in terms of Kronecker products. Special attention is given to random walks on the graphs ??(l = 1,n ? 2), where the vertex set is ?? and two vertices are connected if and only if their Hamming distance is at most l. It is shown that λ(??₁)>λ(??₁)>λ(??_n?1)>λ(??_n),l=2,…,n?2, where λ (??_I) is the specturum of the random walk on ??I, and > denotes the majorization ordering. A similar majorization relation is established for graphs V₁ where two veritces are connected if and only if their Hamming distance is exactly l. Some applications to mean times of these random walks are given. © 1993 John Wiley & Sons, Inc.     

Bounds for ratios of eigenvalues using traces

Let A be an n × n matrix with real eigenvalues λ₁ ? … ? λ_n, and let 1 ? k < l ? n. Bounds involving trA and trA² are introduced for λ_k/λ_l, (λ_k ? λ_l)/(λ_k + λ_l), and {kλ_k + (n ? l + 1)λ_l}²/{kλ²_k + (n ? l + 1)λ²_l}. Also included are conditions for λ_l >; 0 and for λ_k + λ_l > 0.     

On the determination of a tridiagonal matrix from its spectrum and a submatrix

Given a set of 2n real numbers λ₁<λ₂<?<λ_2n, the authors describe the set {S} of n × n tridiagonal matrices with the property that each S can be completed to a 2n×2n tridiagonal matrix L with spec(L)={λ₁, λ₂,…,λ_2n}.     

On the inverse and the dual index of a tree

The inverse of a graph with the spectrum λ ₁, λ ₁, …λ _n (λ ₁≠0) is a graph with the spectrum 1/λ₁,1/λ₂,…,1/λ _n ,.We present a purely graph-theoretic construction of the inverse ol a tree with a perfect matening. We apply this method for deriving results concerning the least nonnegative eigenvalue of a tree (called the dual index of a tree), including the best possible upper bound for the dual index of a tree in terms of a the number of its vertices.     

Differentiable Eigenvalues of Perturbed Quadratic Matrix Functions

Let T(λ, ε ) = λ² + λC + λεD + K be a perturbed quadratic matrix polynomial, where C, D, and K are n × n hermitian matrices. Let λ₀ be an eigenvalue of the unperturbed matrix polynomial T(λ, 0). With the falling part of the Newton diagram of det T(λ, ε), we find the number of differentiable eigenvalues. Some results are extended to the general case L(λ, ε) = λ² + λD(ε) + K, where D(ε) is an analytic hermitian matrix function. We show that if K is negative definite on Ker L(λ₀, 0), then every eigenvalue λ(ε) of L(λ, ε) near λ₀ is analytic.     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

New type of block design

We are already familiar with (υ, k, λ)‐difference sets and (υ, k, λ)‐designs. In this paper, we will introduce a new class of difference sets and designs: (υ, k, [λ₁, λ₂, … , λ_m])‐difference sets and (υ, k, [λ₁,λ₂, … , λ_m])‐designs. We will mainly study designs with a relationship we call λ‐equivalence and use them to produce other designs. Some existence or nonexistence theorems will be given. © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 1–23, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10031     

From regular boundary graphs to antipodal distance-regular graphs

Let Γ be a regular graph with n vertices, diameter D, and d + 1 different eigenvalues λ > λ₁ > ··· > λ_d. In a previous paper, the authors showed that if P(λ) > n − 1, then D ≤ d − 1, where P is the polynomial of degree d − 1 which takes alternating values ± 1 at λ₁, …, λ_d. The graphs satisfying P(λ) = n − 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to the study of this case and, as a main result, it is shown that those extremal (D = d) boundary graphs where each vertex have maximum eccentricity are, in fact, 2-antipodal distance-regular graphs. The study is carried out by using a new sequence of orthogonal polynomials, whose special properties are shown to be induced by their intrinsic symmetry. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123–140, 1998     

On the chromaticity of certain subgraphs of a q-tree

We show that a graph G on n ? q + 1 vertices (where q ? 2) has the chromatic polynomial P(G;λ) = λ(λ ? 1) … (λ ? q + 2) (λ ? q + 1)² (λ ? q)^n?q?1 if and only if G can be obtained from a q-tree Ton n vertices by deleting an edge contained in exactly q ? 1 triangles of T. Furthermore, we prove that these graphs are triangulated.     

Large set of P3‐decompositions

Let G=(V(G),E(G)) be a graph. A (n,G, λ)‐GD is a partition of the edges of λK_n into subgraphs (G‐blocks), each of which is isomorphic to G. The (n,G,λ)‐GD is named as graph design for G or G‐decomposition. The large set of (n,G,λ)‐GD is denoted by (n,G,λ)‐LGD. In this work, we obtain the existence spectrum of (n,P₃,λ)‐LGD. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 151–159, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10008     

Asymptotic analysis and estimates of blow‐up time for the radial symmetric semilinear heat equation in the open‐spectrum case

We estimate the blow‐up time for the reaction diffusion equation u_t=Δu+ λf(u), for the radial symmetric case, where f is a positive, increasing and convex function growing fast enough at infinity. Here λ>λ^*, where λ^* is the ‘extremal’ (critical) value for λ, such that there exists an ‘extremal’ weak but not a classical steady‐state solution at λ=λ^* with ∥w(?, λ)∥_∞→∞ as 0<λ→λ^*?. Estimates of the blow‐up time are obtained by using comparison methods. Also an asymptotic analysis is applied when f(s)=e^s, for λ?λ^*?1, regarding the form of the solution during blow‐up and an asymptotic estimate of blow‐up time is obtained. Finally, some numerical results are also presented. Copyright © 2007 John Wiley & Sons, Ltd.     

Local Asymmetry and the Inner Radius of Nodal Domains

Let M be a closed Riemannian manifold of dimension n. Let ?_λ be an eigenfunction of the Laplace–Beltrami operator corresponding to an eigenvalue λ. We show that the volume of {?_λ > 0} ∩ B is ≥C|B|/λ ⁿ , where B is any ball centered at a point of the nodal set. We apply this result to prove that each nodal domain contains a ball of radius ≥C/λ ⁿ . The results in this paper extend previous results of Nazarov, Polterovich, Sodin and of the author.     

Spectral techniques applied to sparse random graphs

We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ₁ ≥ … ≥ λ_n be the eigenvalues of an n‐vertex graph, and let λ = max[λ₂,|λ_n|]. Let c be a large enough constant. For graphs of average degree d = c log n it is well known that λ₁ ≥ d, and we show that . For d = c it is no longer true that , but we show that by removing a small number of vertices of highest degree in G, one gets a graph G′ for which . Our proofs are based on the techniques of Friedman Kahn and Szemeredi from STOC 1989, who proved similar results for regular graphs. Our results are useful for extending the analysis of certain heuristics to sparser instances of NP‐hard problems. We illustrate this by removing some unnecessary logarithmic factors in the density of k‐SAT formulas that are refuted by the algorithm of Goerdt and Krivelevich from STACS 2001. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

On a Question of Glasby,Praeger, and Xia

A Jordan partition λ(m, n, p) = (λ₁, λ₂, … , λ _m ) is a partition of mn associated with the expression of a tensor V _m  ? V _n of indecomposable KG-modules into a sum of indecomposables, where K is a field of characteristic p and G a cyclic group of p-power order. It is standard if λ _i  = m + n ? 2i + 1 for all i. We answer a recent question of Glasby, Praeger, and Xia who asked for necessary and sufficient conditions for λ(m, n, p) to be standard.     

Doubly stochastic matrices with prescribed positive spectrum

We show that for every set Λ={λ₁,λ₂,…,λ_n} of real numbers such that $\text{λ}{}_1\text{=1?λ}{}_2\text{???λ}{}_{\mathrm{n}}\text{\&\#62;0}$, there exists a doubly stochastic matrix with spectrum Λ. We present an explicit construction of such a matrix.     

On c‐Bhaskar Rao designs with block size 4

Several new families of c‐Bhaskar Rao designs with block size 4 are constructed. The necessary conditions for the existence of a c‐BRD (υ,4,λ) are that: (1)λ_min=?λ/3 ≤ c ≤ λ and (2a) c≡λ (mod 2), if υ > 4 or (2b) c≡ λ (mod 4), if υ = 4 or (2c) c≠ λ ? 2, if υ = 5. It is proved that these conditions are necessary, and are sufficient for most pairs of c and λ; in particular, they are sufficient whenever λ?c ≠ 2 for c > 0 and whenever c ? λ_min≠ 2 for c < 0. For c < 0, the necessary conditions are sufficient for υ> 101; for the classic Bhaskar Rao designs, i.e., c = 0, we show the necessary conditions are sufficient with the possible exception of 0‐BRD (υ,4,2)'s for υ≡ 4 (mod 6). © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 361–386, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10009     

Zero distribution of solutions of complex linear differential equations determines growth of coefficients

It is shown that the exponent of convergence λ(f) of any solution f of with entire coefficients A₀(z), …, A_k?2(z), satisfies λ(f) ? λ ∈ [1, ∞) if and only if the coefficients A₀(z), …, A_k?2(z) are polynomials such that for j = 0, …, k ? 2. In the unit disc analogue of this result certain intersections of weighted Bergman spaces take the role of polynomials. The key idea in the proofs is W. J. Kim’s 1969 representation of coefficients in terms of ratios of linearly independent solutions. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

On inverse multiplicative eigenvalue problems for matrices

Let A be an n×n complex-valued matrix, all of whose principal minors are distinct from zero. Then there exists a complex diagonal matrix D, such that the spectrum of AD is a given set σ = {λ₁,…,λ_n} in C. The number of different matrices D is at most n!.     

A constructive approximation theorem for the oblique derivative problem in potential theory

The (exterior) oblique derivative problem of potential theory is considered where l is a C^(1,λ)-vector field on a regular boundary ?G_e in Euclidean space R ³ and the direction l at any point of ?G_e forms with the outside normal n an angle ? (l, n) satisfying cos ? (l, n) ≥ c > 0. An approximation of the uniquely determined solution is given by use of trial functions {Φ_n}_n=0,1,… harmonic in some region containing G _e and suitable for numerical purpose (for instance: solid spherical harmonics, certain sequences of fundamental solutions). The system {l▽Φ_n+hΦ_n}_n=0,1,… defined on ?G_e is shown to be closed and complete in the pre-Hilbert space C^(0,λ)(?G_e) of λ-Hölder continuous functions.