Random walks on highly symmetric graphs

We consider uniform random walks on finite graphs withn nodes. When the hitting times are symmetric, the expected covering time is at least 1/2n logn-O(n log logn) uniformly over all such graphs. We also obtain bounds for the covering times in terms of the eigenvalues of the transition matrix of the Markov chain. For distance-regular graphs, a general lower bound of (n-1) logn is obtained. For hypercubes and binomial coefficient graphs, the limit law of the covering time is obtained as well.     

On the chromatic number of certain highly symmetric graphs

For 1 ⩽ k ⩽ n, let V(n, k) denote the set of n(n − 1) … (n − k + 1) sequences of k distinct elements from {1, …, n}. Let us define the graph Γ(n, k) on the vertex set V(n, k) by joining two sequences if they differ at exactly one place. We investigate the chromatic number and another related parameter of these graphs. We give a sharp answer for some infinite families, using the theory of sharply transitive permutation groups. The problems discussed are related to a question of Henkin, Monk and Tarski in mathematical logic.     

A class of highly symmetric graphs,symmetric cylindrical constructions and their spectra

In this article, we introduce the algebra of block-symmetric cylinders and we show that symmetric cylindrical constructions on base-graphs admitting commutative decompositions behave as generalized tensor products. We compute the characteristic polynomial of such symmetric cylindrical constructions in terms of the spectra of the base-graph and the cylinders in a general setting. This gives rise to a simultaneous generalization of some well-known results on the spectra of a variety of graph amalgams, as various graph products, graph subdivisions and generalized Petersen graph constructions. While our main result introduces a connection between spectral graph theory and commutative decompositions of graphs, we focus on commutative cyclic decompositions of complete graphs and tree-cylinders along with a subtle group labeling of trees to introduce a class of highly symmetric graphs containing the Petersen and the Coxeter graphs. Also, using techniques based on recursive polynomials we compute the characteristic polynomials of these highly symmetric graphs as an application of our main result.     

Self-complementary symmetric graphs

The class of self-complementary symmetric graphs is characterized using the classification of finite simple group.     

N-extendability of symmetric graphs

It is proved that a cyclically (k ? 1)(2n ? 1)-edge-connected edge transitive k-regular graph with even order is n-extendable, where k ≥ 3 and k ? 1 ≥ n ≥ ?(k + 1)/2?. The bound of cyclic edge connectivity is sharp when k = 3. © 1993 John Wiley & Sons, Inc.     

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some “weights” (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights “regularize” the graph, and hence allow us to define a kind of regular partition, called “pseudo-regular,” intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity Θ^* of a connected graph Γ, with n vertices and (adjacency matrix) eigenvalues λ₁ > λ₂ … λ_n, satisfies

where Θ is the (standard) Shannon capacity and v is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived.     

Eigenvalue pinching theorems on compact symmetric spaces

We prove two first eigenvalue pinching theorems for Riemannian symmetric spaces (Theorems 1 and 2). As their application, we answer negatively a question raised by Elworthy and Rosenberg, who proposed to show that for every compact simple Lie group with a bi-invariant Riemannian metric on with respect to , being the Killing form of the Lie algebra , the first eigenvalue would satisfy

for all orthonormal bases of tangent spaces of (cf. Corollary 3). This problem arose in an attempt to give a spectral geometric proof that for a Lie group .

     

Characteristic polynomials of symmetric graphs

In this paper, we study the characteristic polynomials of graphs which admit semifree actions of an abelian group. Using the method of group matrices, we are able to show that the characteristic polynomial of a such a graph is factorized into a product of a polynomial associated to the orbit of the action and a polynomial associated to the free part of the action.     

Hyperbolic boundary value problems for symmetric systems with variable multiplicities

We extend the Kreiss-Majda theory of stability of hyperbolic initial-boundary-value and shock problems to a class of systems, notably including the equations of magnetohydrodynamics (MHD), for which Majda's block structure condition does not hold: namely, simultaneously symmetrizable systems with characteristics of variable multiplicity, satisfying at points of variable multiplicity either a “totally nonglancing” or a “nonglancing and linearly splitting” condition. At the same time, we give a simple characterization of the block structure condition as “geometric regularity” of characteristics, defined as analyticity of associated eigenprojections. The totally nonglancing or nonglancing and linearly splitting conditions are generically satisfied in the simplest case of crossings of two characteristics, and likewise for our main physical examples of MHD or Maxwell equations for a crystal. Together with previous analyses of spectral stability carried out by Gardner-Kruskal and Blokhin-Trakhinin, this yields immediately a number of new results of nonlinear inviscid stability of shock waves in MHD in the cases of parallel or transverse magnetic field, and recovers the sole previous nonlinear result, obtained by Blokhin-Trakhinin by direct “dissipative integral” methods, of stability in the zero-magnetic field limit. We also discuss extensions to the viscous case.     

Viscous boundary value problems for symmetric systems with variable multiplicities

Extending investigations of Métivier and Zumbrun in the hyperbolic case, we treat stability of viscous shock and boundary layers for viscous perturbations of multidimensional hyperbolic systems with characteristics of variable multiplicity, specifically the construction of symmetrizers in the low-frequency regime where variable multiplicity plays a role. At the same time, we extend the boundary-layer theory to “real” or partially parabolic viscosities, Neumann or mixed-type parabolic boundary conditions, and systems with nonconservative form, in addition proving a more fundamental version of the Zumbrun-Serre-Rousset theorem, valid for variable multiplicities, characterizing the limiting hyperbolic system and boundary conditions as a nonsingular limit of a reduced viscous system. The new effects of viscosity are seen to be surprisingly subtle; in particular, viscous coupling of crossing hyperbolic modes may induce a destabilizing effect. We illustrate the theory with applications to magnetohydrodynamics.     

Bicoset groups and symmetric graphs

In this paper, we construct a functor from the set of bicoset multivalued groups with one Hermitian generator to the set of symmetric graphs. The functor makes it possible to describe the set of bicoset multivalued groups with one Hermitian generator as a sum of categories. The categories are indexed by pairs (^U,G^U), where ^U is a universal symmetric graph and G^U is a subgroup of Aut(^U). Bibliography: 5 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 292, 2002, pp. 161–174.This revised version was published online in April 2005 with a corrected cover date and article title.     

Eigenvalue bracketing for discrete and metric graphs

We develop eigenvalue estimates for the Laplacians on discrete and metric graphs using various types of boundary conditions at the vertices of the metric graph. Via an explicit correspondence of the equilateral metric and discrete graph spectrum (also in the “exceptional” values of the metric graph corresponding to the Dirichlet spectrum) we carry over these estimates from the metric graph Laplacian to the discrete case. We apply the results to covering graphs and present examples where the covering graph Laplacians have spectral gaps.     

Eigenvalue estimates of the p-Laplacian on finite graphs

In this paper, we study the eigenvalue of p-Laplacian on finite graphs. Under generalized curvature dimensional condition, we obtain a lower bound of the first nonzero eigenvalue of p-Laplacian. Moreover, a upper bound of the largest p-Laplacian eigenvalue is derived.     

On symmetric graphs of valency five

A graph X, with a subgroup G of the automorphism group of X, is said to be (G,s)-transitive, for some s≥1, if G is transitive on s-arcs but not on (s+1)-arcs, and s-transitive if it is -transitive. Let X be a connected (G,s)-transitive graph, and G_v the stabilizer of a vertex v∈V(X) in G. If X has valency 5 and G_v is solvable, Weiss [R.M. Weiss, An application of p-factorization methods to symmetric graphs, Math. Proc. Camb. Phil. Soc. 85 (1979) 43-48] proved that s≤3, and in this paper we prove that G_v is isomorphic to the cyclic group Z₅, the dihedral group D₁₀ or the dihedral group D₂₀ for s=1, the Frobenius group F₂₀ or F₂₀×Z₂ for s=2, or F₂₀×Z₄ for s=3. Furthermore, it is shown that for a connected 1-transitive Cayley graph of valency 5 on a non-abelian simple group G, the automorphism group of is the semidirect product , where R(G) is the right regular representation of G and .     

Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs

Letk _t(G) be the number of cliques of ordert in the graphG. For a graphG withn vertices let \(c_t (G) = \frac{{k_t (G) + k_t (\bar G)}}{{\left( {\begin{array}{*{20}c} n \\ t \\ \end{array} } \right)}}\) . Letc _t(n)=Min{c _t(G)∶?G?=n} and let \(c_t = \mathop {\lim }\limits_{n \to \infty } c_t (n)\) . An old conjecture of Erdös [2], related to Ramsey's theorem states thatc _t=2^1-(t/2). Recently it was shown to be false by A. Thomason [12]. It is known thatc _t(G)≈2^1-(t/2) wheneverG is a pseudorandom graph. Pseudorandom graphs — the graphs “which behave like random graphs” — were inroduced and studied in [1] and [13]. The aim of this paper is to show that fort=4,c _t(G)≥2^1-(t/2) ifG is a graph arising from pseudorandom by a small perturbation.     

Finite graphs have unique symmetric products

Let X be a metric continuum and let Fn(X) be the nth symmetric product of X (Fn(X) is the hyperspace of nonempty subsets of X with at most n points). In this paper we prove that if Fn(X) is homeomorphic to Fn(Y), where X is a finite graph and Y is a continuum, then X is homeomorphic to Y.     

A note on labeled symmetric graphs

By using the known results of groups and graphs, we determine the number of labeled symmetric graphs with a prime number of vertices.     

Irreducible subfactors from some symmetric graphs

This work was performed during the author's stay at Mathematics Institute, University of Copenhagen