Narrow Results

In this paper, we generalize virtual knot theory to multi-virtual knot theory where there are a multiplicity of virtual crossings. Each virtual crossing type can detour over the other virtual crossing types, and over classical or immersed crossings. New invariants of multi-virtual knots and links are introduced and new problems that arise are described. We show how the extensions of the Penrose coloring evaluation for trivalent plane graphs and our generalizations of this to non-planar graphs and arbitrary numbers of colors acts as a motivation for the construction of the multi-virtual theory.

We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O*(1.8494^m) time for 3-regular graphs, and O*(1.9706^m) time for unit interval graphs, where m is the number of edges in the graph and O*-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation.

We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e^2πi/5, e^-2πi/5) is DQC1-complete and at points for some integer k is in BQP.

To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids.

To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones–Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of are alternating links.

It is well known that Jones polynomial (hence, Kauffman bracket polynomial) of links is, in general, hard to compute. By now, Jones polynomials or Kauffman bracket polynomials of many link families have been computed, see [4, 7–11]. In recent years, the computer algebra (Maple) techniques were used to calculate link polynomials for various link families, see [7, 12–14]. In this paper, we try to design a maple program to calculate the explicit expression of the Kauffman bracket polynomial of Montesinos links. We first introduce a family of "ring of tangles" links, which includes Montesinos links as a special subfamily. Then, we provide a closed-form formula of Kauffman bracket polynomial for a "ring of tangles" link in terms of Kauffman bracket polynomials of the numerators and denominators of the tangles building the link. Finally, using this formula and known results on rational links, the Maple program is designed.

We introduce an additional arrow structure on ribbon graphs. We extend the dichromatic polynomial to ribbon graphs with this structure. This extended polynomial satisfies the contraction–deletion relations and behaves naturally with respect to the partial duality of ribbon graphs. From a virtual link, we construct an arrow ribbon graph whose extended dichromatic polynomial specializes to the arrow polynomial of the virtual link recently introduced by H. Dye and L. Kauffman. This result generalizes the classical Thistlethwaite theorem to the arrow polynomial of virtual links.

This paper presents an algorithm to construct a weighted adjacency matrix of a plane bipartite graph obtained from a pretzel knot diagram. The determinant of this matrix after evaluation is shown to be the Jones polynomial of the pretzel knot by way of perfect matchings (or dimers) of this graph. The weights are Tutte's activity letters that arise because the Jones polynomial is a specialization of the signed version of the Tutte polynomial. The relationship is formalized between the familiar spanning tree setting for the Tait graph and the perfect matchings of the plane bipartite graph above. Evaluations of these activity words are related to the chain complex for the Champanerkar–Kofman spanning tree model of reduced Khovanov homology.

This paper contains general formulae for the reduced relative Tutte, Kauffman bracket and Jones polynomials of families of virtual knots and links given in Conway notation and discussion of a counterexample to the Z-move conjecture of Fenn, Kauffman and Manturov.

In a recent paper, Jones introduced a correspondence between elements of the Thompson group $F$ and certain graphs/links. It follows from his work that several polynomial invariants of links, such as the Kauffman bracket, can be reinterpreted as coefficients of certain unitary representations of $F$. We give a somewhat different and elementary proof of this fact for the Kauffman bracket evaluated at certain roots of unity by means of a statistical mechanics model interpretation. Moreover, by similar methods we show that, for some particular specializations of the variables, other familiar link invariants and graph polynomials, namely the number of $N$-colorings and the Tutte polynomial, can be viewed as positive definite functions on $F$.

The Tutte polynomial is originally a bivariate polynomial which enumerates the colorings of a graph and of its dual graph. Ardila extended in 2007 the definition of the Tutte polynomial on the real hyperplane arrangements. He particularly computed the Tutte polynomials of the hyperplane arrangements associated to the classical Weyl groups. Those associated to the exceptional Weyl groups were computed by De Concini and Procesi one year later. This paper has two objectives: On the one side, we extend the Tutte polynomial computing to the complex hyperplane arrangements. On the other side, we introduce a wider class of hyperplane arrangements which is that of the symmetric hyperplane arrangements. Computing the Tutte polynomial of a symmetric hyperplane arrangement permits us to deduce the Tutte polynomials of some hyperplane arrangements, particularly of those associated to the imprimitive reflection groups.

The interior polynomial is a Tutte-type invariant of bipartite graphs, and a part of the HOMFLY polynomial of a special alternating link coincides with the interior polynomial of the Seifert graph of the link. We extend the interior polynomial to signed bipartite graphs, and we show that, in the planar case, it is equal to the maximal $z$-degree part of the HOMFLY polynomial of a naturally associated link. Note that the latter can be any oriented link. This result fits into a program aimed at deriving the HOMFLY polynomial from Floer homology.

We also establish some other, more basic properties of the signed interior polynomial. For example, the HOMFLY polynomial of the mirror image of $L$ is given by $P_L(-v^{-1},z)$. This implies a mirroring formula for the signed interior polynomial in the planar case. We prove that the same property holds for any bipartite graph and the same graph with all signs reversed. The proof relies on Ehrhart reciprocity applied to the so-called root polytope. We also establish formulas for the signed interior polynomial inspired by the knot theoretical notions of flyping and mutation. This leads to new identities for the original unsigned interior polynomial.

This work presents formulas for the Kauffman bracket and Jones polynomials of three-bridge knots using the structure of Chebyshev knots and their billiard table diagrams. In particular, these give far fewer terms than in the Skein relation expansion. The subject is introduced by considering the easier case of two-bridge knots, where some geometric interpretation is provided, as well, via combinatorial tiling problems.

In a recent paper, we studied the interaction between the automorphism group of a graph and its Tutte polynomial. More precisely, we proved that certain symmetries of graphs are clearly reflected by their Tutte polynomials. The purpose of this paper is to extend this study to other graph polynomials. In particular, we prove that if a graph $G$ has a symmetry of prime order $p$, then its characteristic polynomial, with coefficients in the finite field ${𝔽}_p$, is determined by the characteristic polynomial of its quotient graph $\overline{G}$. Similar results are also proved for some generalization of the Tutte polynomial.

The Tutte polynomial was originally a bivariate polynomial enumerating the colorings of a graph and of its dual graph. But it reveals more of the internal structure of the graph like its number of forests, of spanning subgraphs, and of acyclic orientations. In 2007, Ardila extended the notion of Tutte polynomial to hyperplane arrangements, and computed the Tutte polynomials of the classical root systems for certain prime powers of the first variable at the same time. In this paper, we compute the Tutte polynomial of ideal arrangements. These arrangements were introduced in 2006 by Sommers and Tymoczko, and are defined for ideals of root systems. For the ideals of classical root systems, we bring a slight improvement of the finite field method by showing that it can applied on any finite field whose cardinality is not a minor of the matrix associated to the studied hyperplane arrangement. Computing the minor set associated to an ideal of classical root systems particularly permits us to deduce the Tutte polynomials of the classical root systems. For the ideals of the exceptional root systems of type $G_2$, $F_4$, and $E_6$, we use the formula of Crapo.

The Tutte polynomial, a considerable generalization of the chromatic polynomial, associated with a graph is a classical bivariate polynomial, which gives various interesting information about the graph structure. In this paper, we first present a formula for the Tutte polynomial of a class of special compound graphs. Then as applications, we obtain the Tutte polynomials of some complex network models in the context of statistical physics and the Tutte polynomials of some chemical polycyclic graphs. Moreover, explicit expressions of the number of spanning trees for these considered graphs are determined, respectively.

The Tutte polynomial of graphs is deeply connected to the q-state Potts model in statistical mechanics. In this survey, we describe this connection and show how one can use lattice polytopes and transfer matrices to tackle a special case given by the zero-temperature anti-ferromagnetic Potts model, where computing the Tutte polynomial reduces to computing the chromatic polynomial. We apply the techniques earlier introduced by the authors to this special case. This article can be seen as a brief summary of this work with a view towards statistical mechanics. In particular, we illustrate this procedure by computing the chromatic polynomials of some (families of) graphs. As it turns out, counting integer points in lattice polytopes is one of the key ingredients of these computations.

We study the Tutte polynomial of two infinite families of finite graphs. These are the Schreier graphs associated with the action of two well-known self-similar groups acting on the binary rooted tree by automorphisms: the first Grigorchuk group of intermediate growth, and the iterated monodromy group of the complex polynomial z² - 1 known as the Basilica group. For both of them, we describe the Tutte polynomial and we compute several special evaluations of it, giving further information about the combinatorial structure of these graphs.