Imprimitive Q-polynomial Association Schemes

It is well known that imprimitive P-polynomial association schemes with are either bipartite or antipodal, i.e., intersection numbers satisfy either for all for all . In this paper, we show that imprimitive -polynomial association schemes with are either dual bipartite or dual antipodal, i.e., dual intersection numbers satisfy either .     

Association Schemes with Multiple Q-polynomial Structures

It is well known that an association scheme with has at most two P-polynomial structures. The parametrical condition for an association scheme to have two P-polynomial structures is also known. In this paper, we give a similar result for Q-polynomial association schemes. In fact, if , then we obtain exactly the same parametrical conditions for the dual intersection numbers or Krein parameters.     

On Symmetric Association Schemes with k 1=3

In this paper, we have a classification of primitive symmetric association schemes with k ₁ = 3.     

A characterization of Q-polynomial distance-regular graphs

Let Γ denote a distance-regular graph with diameter D3. Let θ denote a nontrivial eigenvalue of Γ and let denote the corresponding dual eigenvalue sequence. In this paper we prove that Γ is Q-polynomial with respect to θ if and only if the following (i)–(iii) hold:

(i) There exist such that

(1)

(ii) There exist such that the intersection numbers a_i satisfy

for 0iD, where and are the scalars which satisfy Eq. (1) for i=0, i=D, respectively.

(iii) for 1iD.

The Displacement and Split Decompositions for a Q-Polynomial Distance-regular Graph

Let denote a Q-polynomial distance-regular graph with diameter at least three and standard module V. We introduce two direct sum decompositions of V. We call these the displacement decomposition for and the split decomposition for . We describe how these decompositions are related.     

A Distance-Regular Graph with Intersection Array (5, 4, 3, 3; 1, 1, 1, 2) Does Not Exist

We prove that a distance-regular graph with intersection array (5, 4, 3, 3; 1, 1, 1, 2) does not exist. The proof is purely combinatorial and computer-free.     

A Class of Imprimitive Association Schemes

From Burnside's p^αq^β-Theorem, it follows that any nonabelian group of order p^αq^β, where p and q are primes, cannot be simple. As a main result of this article, we state and prove an analog of the mentioned theorem for commutative association schemes.     

Three-Class Association Schemes

We study (symmetric) three-class association schemes. The graphs with four distinct eigenvalues which are one of the relations of such a scheme are characterized. We also give an overview of most known constructions, and obtain necessary conditions for existence. A list of feasible parameter sets on at most 100 vertices is generated.     

Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes

We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.     

Association Schemes of Quadratic Forms and Symmetric Bilinear Forms

Let X _n and Y _n be the sets of quadratic forms and symmetric bilinear forms on an n-dimensional vector space V over , respectively. The orbits of GL _n( ) on X _n × X _n define an association scheme Qua(n, q). The orbits of GL _n( ) on Y _n × Y _n also define an association scheme Sym(n, q). Our main results are: Qua(n, q) and Sym(n, q) are formally dual. When q is odd, Qua(n, q) and Sym(n, q) are isomorphic; Qua(n, q) and Sym(n, q) are primitive and self-dual. Next we assume that q is even. Qua(n, q) is imprimitive; when (n, q) (2,2), all subschemes of Qua(n, q) are trivial, i.e., of class one, and the quotient scheme is isomorphic to Alt(n, q), the association scheme of alternating forms on V. The dual statements hold for Sym(n, q).     

Distance-Regular Graphs of Valency 6 and a1 = 1

We give a complete classification of distance-regular graphs of valency 6 and a₁ = 1.     

Designs in Product Association Schemes

A number of important families of association schemes—such as the Hamming and Johnson schemes—enjoy the property that, in each member of the family, Delsarte t-designs can be characterised combinatorially as designs in a certain partially ordered set attached to the scheme. In this paper, we extend this characterisation to designs in a product association scheme each of whose components admits a characterisation of the above type. As a consequence of our main result, we immediately obtain linear programming bounds for a wide variety of combinatorial objects as well as bounds on the size and degree of such designs analogous to Delsarte's bounds for t-designs in Q-polynomial association schemes.     

The Construction of Association Schemes by Parameter Amendment

Association scheme is a structure on a finite set that has some special relations among elements in the set. These relations are usually hidden in other relations, so how to derive them out is a problem. The paper gives a constructing method of mending parameters of the association schemes, and a new family of association schemes is obtained： quasiFmetric association scheme.     

Distance-Regular Graphs with Strongly Regular Subconstituents

In [3] Cameron et al. classified strongly regular graphs with strongly regular subconstituents. Here we prove a theorem which implies that distance-regular graphs with strongly regular subconstituents are precisely the Taylor graphs and graphs with a ₁ = 0 and a _i {0,1} for i = 2,...,d.     

关于Sumner-Blitch猜想的一个注记

设G是一个图。G的最小度，连通度，控制数，独立控制数和独立数分别用δ，k，γ，i和α表示，图G是3－γ-临界的，如果γ=3，而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想：任意连通的3－γ临界图满足i=3，本文证明了如果G是使α＝k 1≤δ的连通3－γ-临界图，那么Sumner-Blitch猜想成立。     

Commutative Association Schemes Whose Symmetrizations Have Two Classes

If a symmetric association scheme of class two is realized as the symmetrization of a commutative association scheme, then it either admits a unique symmetrizable fission scheme of class three or four, or admits three fission schemes, two of which are class three and one is of class four. We investigate the classification problem for symmetrizable (commutative) association schemes of two-class symmetric association schemes. In particular, we give a classification of association schemes whose symmetrizations are obtained from completely multipartite strongly regular graphs in the notion of wreath product of two schemes. Also the cyclotomic schemes associated to Paley graphs and their symmetrizable fission schemes are discussed in terms of their character tables.     

Association Schemes with at Most Two Nonlinear Irreducible Characters and Applications to Finite Groups

An irreducible character χ of an association scheme is called nonlinear if the multiplicity of χ is greater than 1. The main result of this paper gives a characterization of commutative association schemes with at most two nonlinear irreducible characters. This yields a characterization of finite groups with at most two nonlinear irreducible characters. A class of noncommutative association schemes with at most two nonlinear irreducible character is also given.     

Polynomial Properties on Large Symmetric Association Schemes

In this paper we characterize “large” regular graphs using certain entries in the projection matrices onto the eigenspaces of the graph. As a corollary of this result, we show that “large” association schemes become P-polynomial association schemes. Our results are summarized as follows. Let G = (V, E) be a connected k-regular graph with d +1 distinct eigenvalues \({k = \theta_{0} > \theta_{1} > \cdots > \theta_{d}}\). Since the diameter of G is at most d, we have the Moore bound

$$|V| \leq M(k,d) = 1 + k \sum^{d-1}_{i=0} (k-1)^{i}.$$

Note that if |V| > M(k, d ? 1) holds, the diameter of G is equal to d. Let E _i be the orthogonal projection matrix onto the eigenspace corresponding to θ _i . Let ?(u, v) be the path distance of u, v ∈V.

Theorem. Assume \({|V| > M(k, d - 1)}\) holds. Then for x, y ∈V with \({\partial (x, y) = d}\), the (x, y) -entry of E _i is equal to

$$-\frac{1}{|V|} \prod _{j=1,2,...,d, j \neq i} \frac{\theta_{0}-\theta_{j}}{\theta_{i}-\theta_{j}}.$$

If a symmetric association scheme \({\mathfrak{X} = (X, \{R_{i}\}^{d}_{i=0})}\) has a relation R _i such that the graph (X, R _i ) satisfies the above condition, then \({\mathfrak{X}}\) is P-polynomial. Moreover we show the “dual” version of this theorem for spherical sets and Q-polynomial association schemes.