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.     

On the colored Tutte polynomial of a graph of bounded treewidth

We observe that a formula given by Negami [Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987) 601-622] for the Tutte polynomial of a k-sum of two graphs generalizes to a colored Tutte polynomial. Consequently, an algorithm of Andrzejak [An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39-54] may be directly adapted to compute the colored Tutte polynomial of a graph of bounded treewidth in polynomial time. This result has also been proven by Makowsky [Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math. 145 (2005) 276-290], using a different algorithm based on logical techniques.     

Star partitions and the graph isomorphism problem

A canonical basis of Rⁿ associated with a graph G on n vertices has been defined in [15] in connection with eigenspaces and star partitions of G. The canonical star basis together with eigenvalues of G determines G to an isomorphism. We study algorithms for finding the canonical basis and some of its variations. The emphasis is on the following three special cases; graphs with distinct eigenvalues, graphs with bounded eigenvalue multiplicities and strongly regular graphs. We show that the procedure is reduced in some parts to special cases of some well known combinatorial optimization problems, such as the maximal matching problem. the minimal cut problem, the maximal clique problem etc. This technique provides another proof of a result of L. Babai et al. [2] that isomorphism testing for graphs with bounded eigenvalue multiplicities can be performend in a polynomial time. We show that the canonical basis in strongly regular graphs is related to the graph decomposition into two strongly regular induced subgraphs. Examples of distinguishing between cospectral strongly regular graphs by means of the canonical basis are provided. The behaviour of star partitions of regular graphs under operations of complementation and switching is studied.     

Type-II matrices in weighted Bose–Mesner algebras of ranks 2 and 3

Type-II matrices are nonzero complex matrices that were introduced in connection with spin models for link invariants. Type-II matrices have been found in connection with symmetric designs, sets of equiangular lines, strongly regular graphs, and some distance regular graphs. We investigate weighted complete and strongly regular graphs, and show that type-II matrices arise in this setting as well.     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

The homogenization of the three dimensional skew polynomial algebras of type I

This paper studies a special case of graded central extensions of three dimen-sional Artin-Schelter regular algebras, see [9, §3]. The algebras are homoge-nizations of two classes of three dimensional skew polynomial algebras. We refer to these algebras as Type I and Type II algebras. We describe the non-commutative projective geometry and compute the finite dimensional simple modules for the homogenization of Type I algebras in the case that α is not a primitive root of unity. In this case, all finite dimensional simple modules are quotients of line modules that are homogenizations of Verma modules.     

Cyclotomic Birman–Wenzl–Murakami Algebras,II: Admissibility Relations and Freeness

The cyclotomic Birman-Wenzl-Murakami algebras are quotients of the affine BMW algebras in which the affine generator satisfies a polynomial relation. We study admissibility conditions on the ground ring for these algebras, and show that the algebras defined over an admissible integral ground ring S are free S-modules and isomorphic to cyclotomic Kauffman tangle algebras. We also determine the representation theory in the generic semisimple case, obtain a recursive formula for the weights of the Markov trace, and give a sufficient condition for semisimplicity.     

On the Classification of Extremal Even Formally Self-Dual Codes

Bachoc bachoc has recently introduced harmonic polynomials for binary codes. Computing these for extremal even formally self-dual codes of length 12, she found intersection numbers for such codes and showed that there are exactly three inequivalent [12,6,4] even formally self-dual codes, exactly one of which is self-dual. We prove a new theorem which gives a generator matrix for formally self-dual codes. Using the Bachoc polynomials we can obtain the intersection numbers for extremal even formally self-dual codes of length 14. These same numbers can also be obtained from the generator matrix. We show that there are precisely ten inequivalent [14,7,4] even formally self-dual codes, only one of which is self-dual.     

Symmetric Versus Non-Symmetric Spin Models for Link Invariants

We study spin models as introduced in [20]. Such a spin model can be defined as a square matrix satisfying certain equations, and can be used to compute an associated link invariant. The link invariant associated with a symmetric spin model depends only trivially on link orientation. This property also holds for quasi-symmetric spin models, which are obtained from symmetric spin models by certain gauge transformations preserving the associated link invariant. Using a recent result of [16] which asserts that every spin model belongs to some Bose-Mesner algebra with duality, we show that the transposition of a spin model can be realized by a permutation of rows. We call the order of this permutation the index of the spin model. We show that spin models of odd index are quasi-symmetric. Next, we give a general form for spin models of index 2 which implies that they are associated with a certain class of symmetric spin models. The symmetric Hadamard spin models of [21] belong to this class and this leads to the introduction of non-symmetric Hadamard spin models. These spin models give the first known example where the associated link invariant depends non-trivially on link orientation. We show that a non-symmetric Hadamard spin model belongs to a certain triply regular Bose-Mesner algebra of dimension 5 with duality, and we use this to give an explicit formula for the associated link invariant involving the Jones polynomial.     

The multivariate signed Bollobás-Riordan polynomial

We generalise the signed Bollobás-Riordan polynomial of S. Chmutov and I. Pak [S. Chmutov, I. Pak, The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial, Mos. Math. J. 7(3) (2007), 409-418] to a multivariate signed polynomial Z and study its properties. We prove the invariance of Z under the recently defined partial duality of S. Chmutov [S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial, J. Combin. Theory, Ser. B 99(3) (2009), 617-638. arXiv:0711.3490, doi:10.1016/j.jctb.2008.09.007] and show that the duality transformation of the multivariate Tutte polynomial is a direct consequence of it.     

Graded tensor products

We study the polynomial identities of regular algebras, introduced in [A. Regev, T. Seeman, Z₂-graded tensor products of P.I. algebras, J. Algebra 291 (2005) 274-296]. For example, a finite-dimensional algebra is regular if it has a basis whose multiplication table satisfies some commutation relations. The matrix algebra M_n(F) over the field F is regular, which is closely related to M_n(F) being Z_n-graded. We study the polynomial identities of various types of tensor products of such algebras. In particular, using the theory of Hopf algebras, we prove a far reaching extension of the A⊗B theorem for Z₂-graded PI algebras.     

Galois ring extensions and localized modular rings of invariants of p-groups

We apply recent results on Galois-ring extensions and trace surjective algebras to analyze dehomogenized modular invariant rings of finite p-groups, as well as related localizations. We describe criteria for the dehomogenized invariant ring to be polynomial or at least regular and we show that for regular affine algebras with possibly non-linear action by a p-group, the singular locus of the invariant ring is contained in the variety of the transfer ideal. If V is the regular module of an arbitrary finite p-group, or V is any faithful representation of a cyclic p-group, we show that there is a suitable invariant linear form, inverting which renders the ring of invariants into a “localized polynomial ring” with dehomogenization being a polynomial ring. This is in surprising contrast to the fact that for a faithful representation of a cyclic group of order larger than p, the ring of invariants itself cannot be a polynomial ring by a result of Serre. Our results here generalize observations made by Richman [R] and by Campbell and Chuai [CCH].     

Binary Optimal Odd Formally Self-Dual Codes

In this paper, we study binary optimal odd formallyself-dual codes. All optimal odd formally self-dual codes areclassified for length up to 16. The highest minimum weight ofany odd formally self-dual codes of length up to 24 is determined. We also show that there is a unique linearcode for parameters [16, 8, 5] and [22, 11, 7], up to equivalence.     

Unsigned State Models for the Jones Polynomial

It is a well-known and fundamental result that the Jones polynomial can be expressed as Potts and vertex partition functions of signed plane graphs. Here we consider constructions of the Jones polynomial as state models of unsigned graphs and show that the Jones polynomial of any link can be expressed as a vertex model of an unsigned embedded graph. In the process of deriving this result, we show that for every diagram of a link in S ³ there exists a diagram of an alternating link in a thickened surface (and an alternating virtual link) with the same Kauffman bracket. We also recover two recent results in the literature relating to the Jones and Bollobás-Riordan polynomials and show they arise from two different interpretations of the same embedded graph.     

The subconstituent algebra of strongly regular graphs associated with a Latin square

It is well-known that one may construct several strongly regular graphs on the positions of a Latin square, where adjacency corresponds to any subset of the relations on distinct positions of being in the same row, being in the same column, having the same entry, or none of these. We describe the local spectrum and subconstituent (Terwilliger) algebras of such strongly regular graphs.      

The interlace polynomial of a graph

Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable “interlace polynomial” for any graph. The polynomial satisfies a beautiful and unexpected reduction relation, quite different from the cut and fuse reduction characterizing the Tutte polynomial.It emerges that the interlace graph polynomial may be viewed as a special case of the Martin polynomial of an isotropic system, which underlies its connections with the circuit partition polynomial and the Kauffman brackets of a link diagram. The graph polynomial, in addition to being perhaps more broadly accessible than the Martin polynomial for isotropic systems, also has a two-variable generalization that is unknown for the Martin polynomial. We consider extremal properties of the interlace polynomial, its values for various special graphs, and evaluations which relate to basic graph properties such as the component and independence numbers.     

Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

Contractors and connectors of graph algebras

We study generalizations of the “contraction‐deletion” relation of the Tutte polynomial, and other similar simple operations, to other graph parameters. The question can be set in the framework of graph algebras introduced by Freedman at al [Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007), 37–51.] Graph algebras are defined by a graph parameter, and they were introduced in order to study and characterize homomorphism functions. We prove that for homomorphism functions, these graph algebras have special elements called “contractors” and “connectors”. This gives a new characterization of homomorphism functions. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 11–30, 2009     

Triangle-free strongly circular-perfect graphs

Zhu [X. Zhu, Circular-perfect graphs, J. Graph Theory 48 (2005) 186-209] introduced circular-perfect graphs as a superclass of the well-known perfect graphs and as an important χ-bound class of graphs with the smallest non-trivial χ-binding function χ(G)≤ω(G)+1. Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs [M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. (in press)]; in particular, perfect graphs are closed under complementation [L. Lovász, Normal hypergraphs and the weak perfect graph conjecture, Discrete Math. 2 (1972) 253-267]. To the contrary, circular-perfect graphs are not closed under complementation and the list of forbidden subgraphs is unknown.We study strongly circular-perfect graphs: a circular-perfect graph is strongly circular-perfect if its complement is circular-perfect as well. This subclass entails perfect graphs, odd holes, and odd antiholes. As the main result, we fully characterize the triangle-free strongly circular-perfect graphs, and prove that, for this graph class, both the stable set problem and the recognition problem can be solved in polynomial time.Moreover, we address the characterization of strongly circular-perfect graphs by means of forbidden subgraphs. Results from [A. Pêcher, A. Wagler, On classes of minimal circular-imperfect graphs, Discrete Math. (in press)] suggest that formulating a corresponding conjecture for circular-perfect graphs is difficult; it is even unknown which triangle-free graphs are minimal circular-imperfect. We present the complete list of all triangle-free minimal not strongly circular-perfect graphs.     

Non rank 3 strongly regular graphs with the 5-vertex condition

Three new strongly regular graphs on 256, 120, and 135 vertices are described in this paper. They satisfy thet-vertex condition — in the sense of [1] — on the edges and on the nonedges fort=4 but they are not rank 3 graphs. The problem to search for any such graph was discussed on a folklore level several times and was fixed in [2]. Here the graph on 256 vertices satisfies even the 5-vertex condition, and has the graphs on 120 and 135 vertices as its subgraphs. The existence of these graphs was announced in [3] and [4]. [4] contains M. H. Klin's interpretation of the graph on 120 vertices. Further results concerning these graphs were obtained by A. E. Brouwer, cf. [5].