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).     

Automorphisms of Association Schemes of Quadratic Forms over a Finite Field of Characteristic Two

Let X_n denote the set of quadratic forms in n variables over a finite field F_q of characteristic 2, and X_n the association scheme on X_n by defining the relations with respect to the type of quadratic forms. We prove that every automorphism of X_n is of the form X P^tXP + Y for all X X_n, where P GL_n(F_q), is an automorphism of F_q, and Y X_n.2000 Mathematics Subject Classification: 05E30Supported by the National Natural Science Foundation of China (10271039), Hobei Natural Science Foundation (102132) and Hebei Education Committee.     

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.     

Distance regularity of Kerdock codes

A code is called distance regular, if for every two codewords x, y and integers i, j the number of codewords z such that d(x, z) = i and d(y, z) = j, with d the Hamming distance, does not depend on the choice of x, y and depends only on d(x, y) and i, j. Using some properties of the discrete Fourier transform we give a new combinatorial proof of the distance regularity of an arbitrary Kerdock code. We also calculate the parameters of the distance regularity of a Kerdock code.     

Semidirect Products of Association Schemes

In his 1996 work developing the theory of association schemes as a generalized group theory, Zieschang introduced the concept of the semidirect product as a possible product operation of certain association schemes. In this paper we extend the semidirect product operation into the entire set of association schemes. We then derive a way to decompose certain association schemes into smaller association schemes. We also investigate to what extent this product helps us to understand and characterize the structure of association schemes. We give some examples to show that the semidirect product produces many schemes that cannot be described as neither the direct product nor the wreath product of smaller schemes.This research was supported by Com²MaC-KOSEF, Korea.     

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 .     

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.     

On Codes Identifying Sets of Vertices in Hamming Spaces

A code is called (t, 2)-identifying if for all the words x, y(x y) and the sets (B _t (x) B _t (y)) C and are nonempty and different. Constructions of such codes and a lower bound on the cardinality of these codes are given. The lower bound is shown to be sharp in some cases. We also discuss a more general notion of -identifying codes and introduce weakly identifying codes.     

Irreducible Representations of Wreath Products of Association Schemes

The wreath product of finite association schemes is a natural generalization of the notion of the wreath product of finite permutation groups. We determine all irreducible representations (the Jacobson radical) of a wreath product of two finite association schemes over an algebraically closed field in terms of the irreducible representations (Jacobson radicals) of the two factors involved.     

Duality Maps of Finite Abelian Groups and Their Applications to Spin Models

Duality maps of finite abelian groups are classified. As a corollary, spin models on finite abelian groups which arise from the solutions of the modular invariance equations are determined as tensor products of indecomposable spin models. We also classify finite abelian groups whose Bose-Mesner algebra can be generated by a spin model.     

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.     

Uniformly Packed Codes and More Distance Regular Graphs from Crooked Functions

Let V and W be n-dimensional vector spaces over GF(2). A function Q : V W is called crooked (a notion introduced by Bending and Fon-Der-Flaass) if it satisfies the following three properties:

特征为2的有限域上二次曲面的结合方案的注记

By using nondegenerate and degenerate quadrics in projective space over finite fields of characteristic 2, some association schemes were constructed and their parameters were computed by the authors (see Adv. in Math., 3(2000), 120-128 and Acta Math. Appl. Sinica, 1(1999), 96-103). In this note, their polynomial properties, eigenmatrices, imprimitivities, association subschemes and related quotient association schemes are studied.     

On Spin Models,Triply Regular Association Schemes,and Duality

Motivated by the construction of invariants of links in 3-space, we study spin models on graphs for which all edge weights (considered as matrices) belong to the Bose-Mesner algebra of some association scheme. We show that for series-parallel graphs the computation of the partition function can be performed by using series-parallel reductions of the graph appropriately coupled with operations in the Bose-Mesner algebra. Then we extend this approach to all plane graphs by introducing star-triangle transformations and restricting our attention to a special class of Bose-Mesner algebras which we call exactly triply regular. We also introduce the following two properties for Bose-Mesner algebras. The planar duality property (defined in the self-dual case) expresses the partition function for any plane graph in terms of the partition function for its dual graph, and the planar reversibility property asserts that the partition function for any plane graph is equal to the partition function for the oppositely oriented graph. Both properties hold for any Bose-Mesner algebra if one considers only series-parallel graphs instead of arbitrary plane graphs. We relate these notions to spin models for link invariants, and among other results we show that the Abelian group Bose-Mesner algebras have the planar duality property and that for self-dual Bose-Mesner algebras, planar duality implies planar reversibility. We also prove that for exactly triply regular Bose-Mesner algebras, to check one of the above properties it is sufficient to check it on the complete graph on four vertices. A number of applications, examples and open problems are discussed.     

Asymmetric Binary Covering Codes

An asymmetric binary covering code of length n and radius R is a subset of the n-cube Q_n such that every vector xQ_n can be obtained from some vector c by changing at most R 1's of c to 0's, where R is as small as possible. K⁺(n,R) is defined as the smallest size of such a code. We show K⁺(n,R)Θ(2ⁿ/n^R) for constant R, using an asymmetric sphere-covering bound and probabilistic methods. We show K⁺(n,n− )= +1 for constant coradius iff n ( +1)/2. These two results are extended to near-constant R and , respectively. Various bounds on K⁺ are given in terms of the total number of 0's or 1's in a minimal code. The dimension of a minimal asymmetric linear binary code ([n,R]⁺-code) is determined to be min{0,n−R}. We conclude by discussing open problems and techniques to compute explicit values for K⁺, giving a table of best-known bounds.     

Independent Sets In Association Schemes

Let X be k-regular graph on v vertices and let τ denote the least eigenvalue of its adjacency matrix A(X). If α(X) denotes the maximum size of an independent set in X, we have the following well known bound:

Association Schemes and Fusion Algebras (An Introduction)

We introduce the concept of fusion algebras at algebraic level, as a purely algebraic concept for the fusion algebras which appear in conformal field theory in mathematical physics. We first discuss the connection between fusion algebras at algebraic level and character algebras, a purely algebraic concept for Bose-Mesner algebras of association schemes. Through this correspondence, we establish the condition when the matrix S of a fusion algebra at algebraic level is unitary or symmetric. We construct integral fusion algebras at algebraic level, from association schemes, in particular from group association schemes, whose matrix S is unitary and symmetric. Finally, we consider whether the modular invariance property is satisfied or not, namely whether there exists a diagonal matrix T satisfying the condition (ST)³ = S ². We prove that this property does not hold for some integral fusion algebras at algebraic level coming from the group association scheme of certain groups of order 64, and we also prove that the (nonintegral) fusion algebra at algebraic level obtained from the Hamming association scheme H(d, q) has the modular invariance property.     

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.     

Hypergraphical Codes Arising from Binary Trades

By considering the null space of incidence matrices of trivial designs over GF(2) (the space of 1- (v,k) trades overGF(2)) we obtain families of codes which are optimal for some v and k. Moreover, by generalizing the concept of bond space, the weight enumerator polynomials for these codes are obtained.