Graphs whose normalized Laplacian has three eigenvalues

We give a combinatorial characterization of graphs whose normalized Laplacian has three distinct eigenvalues. Strongly regular graphs and complete bipartite graphs are examples of such graphs, but we also construct more exotic families of examples from conference graphs, projective planes, and certain quasi-symmetric designs.     

The generalized Fibonomial matrix

The Fibonomial coefficients are known as interesting generalizations of binomial coefficients. In this paper, we derive a (k+1)th recurrence relation and generating matrix for the Fibonomial coefficients, which we call generalized Fibonomial matrix. We find a nice relationship between the eigenvalues of the Fibonomial matrix and the generalized right-adjusted Pascal matrix; that they have the same eigenvalues. We obtain generating functions, combinatorial representations, many new interesting identities and properties of the Fibonomial coefficients. Some applications are also given as examples.     

On the transcendence of real numbers with a regular expansion

We apply the Ferenczi-Mauduit combinatorial condition obtained via a reformulation of Ridout's theorem to prove that a real number whose b-ary expansion is the coding of an irrational rotation on the circle with respect to a partition in two intervals is transcendental. We also prove the transcendence of real numbers whose b-ary expansion arises from a non-periodic three-interval exchange transformation.     

Structure of three-interval exchange transformations II: a combinatorial description of the tranjectories

Astract  We describe an algorithm for generating the symbolic sequences which code the orbits of points under an interval exchange transformation on three intervals. The algorithm has two components. The first is an arithmetic division algorithm applied to the lengths of the intervals. This arithmetic construction was originally introduced by the authors in an earlier paper and may be viewed as a two-dimensional generalization of the regular continued fraction. The second component is a combinatorial algorithm which generates the bispecial factors of the associated symbolic subshift as a function of the arithmetic expansion. As a consequence, we obtain a complete characterization of those sequences of block complexity 2n+1 which are natural codings of orbits of three-interval exchange transformations, thereby answering an old question of Rauzy. Partially supported by NSF grant INT-9726708.     

Covering numbers: Arithmetics and dynamics for rotations and interval exchanges

We study a particular case of the two-dimensional Steinhaus theorem, giving estimates of the possible distances between points of the formkα andkα+β on the unit circle, through an approximation algorithm of β by the pointskα. This allows us to compute covering numbers (maximal measures of Rokhlin stacks having certain prescribed regularity properties) for the symbolic dynamical systems associated to the rotation of argument α, acting on the partition of the circle by the points 0, β. We can the compute topological and measure-theoretic covering numbers for exchange of three intervals; in this way, we prove that every ergodic exchange of three intervals has simple spectrum and build a new class of three-interval exchanges which are not of rank one.     

Cutting sequences on square-tiled surfaces

We characterize cutting sequences of infinite geodesics on square-tiled surfaces by considering interval exchanges on specially chosen intervals on the surface. These interval exchanges can be thought of as skew products over a rotation, and we convert cutting sequences to symbolic trajectories of these interval exchanges to show that special types of combinatorial lifts of Sturmian sequences completely describe all cutting sequences on a square-tiled surface. Our results extend the list of families of surfaces where cutting sequences are understood to a dense subset of the moduli space of all translation surfaces.     

Accurate solutions of fourth order Sturm-Liouville problems

Recently we introduced a new method which we call the Extended Sampling Method to compute the eigenvalues of second order Sturm-Liouville problems with eigenvalue dependent potential. We shall see in this paper how we use this method to compute the eigenvalues of fourth order Sturm-Liouville problems and present its practical use on a few examples.     

Dynamical generalizations of the lagrange spectrum

We compute two invariants of topological conjugacy, the upper and lower limits of the inverse of Boshernitzan??s ne _n , where e _n is the smallest measure of a cylinder of length n, for three families of symbolic systems: the natural codings of rotations, three-interval exchanges, and Arnoux-Rauzy systems. The sets of values of these invariants for a given family of systems generalize the Lagrange spectrum, which is what we obtain for the family of rotations with the upper limit of 1/ne _n.     

Integrable discrete hungry systems and their related matrix eigenvalues

Recently, some of the authors designed an algorithm, named the dhLV algorithm, for computing complex eigenvalues of a certain class of band matrix. The recursion formula of the dhLV algorithm is based on the discrete hungry Lotka–Volterra (dhLV) system, which is an integrable system. One of the authors has proposed an algorithm, named the multiple dqd algorithm, for computing eigenvalues of a totally nonnegative (TN) band matrix. In this paper, by introducing a theorem on matrix eigenvalues, we first show that the eigenvalues of a TN matrix are also computable by the dhLV algorithm. We next clarify the asymptotic behavior of the discrete hungry Toda (dhToda) equation, which is also an integrable system, and show that a similarity transformation for a TN matrix is given through the dhToda equation. Then, by combining these properties of the dhToda equation, we design a new algorithm, named the dhToda algorithm, for computing eigenvalues of a TN matrix. We also describe the close relationship among the above three algorithms and give numerical examples.     

A law of large numbers for finite‐range dependent random matrices

We consider random Hermitian matrices in which distant above‐diagonal entries are independent but nearby entries may be correlated. We find the limit of the empirical distribution of eigenvalues by combinatorial methods. We also prove that the limit has an algebraic Stieltjes transform by an argument based on dimension theory of Noetherian local rings. © 2008 Wiley Periodicals, Inc.     

Spectra of Cayley graphs of complex reflection groups

Renteln proved that the eigenvalues of the distance matrix of a Cayley graph of a real reflection group with respect to the set of all reflections are integral and provided a combinatorial formula for some such spectra. We prove the eigenvalues of the distance, adjacency, and codimension matrices of Cayley graphs of complex reflection groups with connection sets consisting of all reflections are integral and provide a combinatorial formula for the codimension spectra for a family of monomial complex reflection groups.     

Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution

The prefix exchange distance of a permutation is the minimum number of exchanges involving the leftmost element that sorts the permutation. We give new combinatorial proofs of known results on the distribution of the prefix exchange distance for a random uniform permutation. We also obtain expressions for the mean and the variance of this distribution, and finally, we show that the normalised prefix exchange distribution converges in distribution to the standard normal distribution.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Biregular graphs with three eigenvalues

We consider nonregular graphs having precisely three distinct eigenvalues. The focus is mainly on the case of graphs having two distinct valencies and our results include constructions of new examples, structure theorems, valency constraints, and a classification of certain special families of such graphs. We also present a new example of a graph with three valencies and three eigenvalues of which there are currently only finitely many known examples.     

A Harnack inequality for Dirichlet eigenvalues

We prove a Harnack inequality for Dirichlet eigenfunctions of abelian homogeneous graphs and their convex subgraphs. We derive lower bounds for Dirichlet eigenvalues using the Harnack inequality. We also consider a randomization problem in connection with combinatorial games using Dirichlet eigenvalues. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 247–257, 2000     

Algorithm for min-range multiplication of affine forms

We consider an approximate method based on the alternate trapezoidal quadrature for the eigenvalue problem given by a periodic singular Fredholm integral equation of second kind. For some convolution-type integral kernels, the eigenvalues of the discrete eigenvalue problem provided by the alternate trapezoidal quadrature method have multiplicity at least two, except up to two eigenvalues of multiplicity one. In general, these eigenvalues exhibit some symmetry properties that are not necessarily observed in the eigenvalues of the continuous problem. For a class of Hilbert-type kernels, we provide error estimates that are valid for a subset of the discrete spectrum. This subset is further enlarged in an improved quadrature method presented herein. The results are illustrated through numerical examples.     

Subset representations and eigenvalues of the universal intertwining matrix

We solve a combinatorial question concerning eigenvalues of the universal intertwining endomorphism of a subset representation.     

Invariant Differential Operators on Symmetric Cones and Hermitian Symmetric Spaces

We give a brief survey on the study of constructions of invariant differential operators on Riemannian symmetric spaces and of combinatorial and analytical properties of their eigenvalues, and pose some open questions.     

Combinatorial criteria for uniqueness of Gibbs measures

We generalize previously known conditions for uniqueness of the Gibbs measure in statistical physics models by presenting conditions of any finite size for models on any underlying graph. We give two dual conditions, one requiring that the total influence on a site is small, and the other that the total influence of a site is small. Our proofs are combinatorial in nature and use tools from the analysis of discrete Markov chains, in particular the path coupling method. The implications of our conditions for the mixing time of natural Markov chains associated with the models are discussed as well. We also present some examples of models for which the conditions hold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005