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.

For each graph and each positive integer n, we define a chain complex whose graded Euler characteristic is equal to an appropriate n-specialization of the dichromatic polynomial. This also gives a categorification of n-specializations of the Tutte polynomial of graphs. Also, for each graph and integer n ≤ 2, we define the different one-variable n-specializations of the dichromatic polynomial, and for each polynomial, we define graded chain complex whose graded Euler characteristic is equal to that polynomial. Furthermore, we explicitly categorify the specialization of the Tutte polynomial for graphs which corresponds to the Jones polynomial of the appropriate alternating link.

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

R. Bott defined two combinatorial invariants for finite cell complexes in the 1950's [2]. As described in [3], they fit beautifully into a state model framework. Recently, it has been observed that for finite graphs, the coefficients of this polynomial are the same set of invariants as defined by H. Whitney in [5]. In section 1, we define the Bott-Whitney polynomial and prove some of its basic properties. In section 2, we show that for a planar connected graph, the Bott-Whitney polynomial is essentially the chromatic polynomial of its dual graph. In section 3, an interpretation of the coefficients of the Bott-Whitney polynomial is given following Whitney [5]. In section 4, we study more general Bott polynomials.

A few years ago the so-called oriented subgroup $\overrightarrow{F}$ of the Thompson group $F$ was introduced by V. Jones while investigating the connections between subfactors and conformal field theories. In the coding of links and knots by elements of $F$ it corresponds exactly to the oriented ones. Thanks to the work of Golan and Sapir, $\overrightarrow{F}$ provided the first example of a maximal subgroup of infinite index in $F$ different from the parabolic subgroups that fix a point in $(0,1)$. In this paper we investigate possible analogues of $\overrightarrow{F}$ in higher Thompson groups $F_k,k\ge 2$, with $F=F_2$, introduced by Brown. Most notably, we study algebraic properties of the oriented subgroup ${\overrightarrow{F}}_3$ of $F_3$, as described recently by Jones, and prove in particular that it gives rise to a non-parabolic maximal subgroup of infinite index in $F_3$ and that the corresponding quasi-regular representation is irreducible.

The injective chromatic number χ_i(G) [G. Hahn, J. Kratochvil, J. Siran and D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256(1–2) (2002) 179–192] of a graph G is the minimum number of colors needed to color the vertices of G such that two vertices with a common neighbor are assigned distinct colors. The nature of the coefficients of injective chromatic polynomials of complete graphs, wheel graphs and cycles is studied. Injective chromatic polynomial on operations like union, join, product and corona of graphs is obtained.

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.

For each δ > 0, we introduce a natural generalization of planar graphs called δ-near-planar graphs. We compare and contrast the δ-near-planar graphs with the class of graphs of genus ≤ g (for any integer g ≥ 0). We observe that a number of NP-complete problems, that are polynomial time solvable for planar graphs(more generally for the graphs of genus g), remain NP-complete for δ-near-planar graphs. We also show that δ-near-planar graphs do not have an efficient recursively applicable O(n^r) separator theorem for any r < 1. However, we show that a number of problems for δ-near-planar graphs, including polynomial time solvable and NP-hard problems, are solvable in time bounded by linear functions of the best known bounds on the times of the corresponding problems for planar graphs. Examples include the following:

1. The problems of solving a δ-near-planar system of linear equations and for solving the single source shortest path problem, for δ-near-planar graphs, are solvable using O(n^3/2) operations.

2. The all-pairs shortest path problem, for δ-near-planar graphs, is solvable using O(n²logn) operations.

3. The problems 3SAT, max-3SAT and #-SAT, etc. restricted to formulas f whose associated interaction graphs are δ-near-planar are solvable using only operations and low level polynomial space, where n is the number of variables of f.

4. The Hamiltonian Circuit problem is solvable and the chromatic polynomial is computable in operations and low level polynomial space for n-vertex δ-near-planar graphs.

Discovering signaling pathways in protein interaction networks is a key ingredient in understanding how proteins carry out cellular functions. These interactions however can be uncertain events that may or may not take place depending on many factors including the internal factors, such as the size and abundance of the proteins, or the external factors, such as mutations, disorders and drug intake. In this paper, we consider the problem of finding causal orderings of nodes in such protein interaction networks to discover signaling pathways. We adopt color coding technique to address this problem. Color coding method may fail with some probability. By allowing it to run for sufficient time, however, its confidence in the optimality of the result can converge close to 100%. Our key contribution in this paper is elimination of the key conservative assumptions made by the traditional color coding methods while computing its success probability. We do this by carefully establishing the relationship between node colors, network topology and success probability. As a result our method converges to any confidence value much faster than the traditional methods. Thus, it is scalable to larger protein interaction networks and longer signaling pathways than existing methods. We demonstrate, both theoretically and experimentally that our method outperforms existing methods.