Chromatic polynomial, q-binomial counting and colored Jones function

We define a q-chromatic function and q-dichromate on graphs and compare it with existing graph functions. Then we study in more detail the class of general chordal graphs. This is partly motivated by the graph isomorphism problem. Finally we relate the q-chromatic function to the colored Jones function of knots. This leads to a curious expression of the colored Jones function of a knot diagram K as a chromatic operator applied to a power series whose coefficients are linear combinations of long chord diagrams. Chromatic operators are directly related to weight systems by the work of Chmutov, Duzhin, Lando and Noble, Welsh.     

The Alexander polynomial and finite type 3-manifold invariants

Using elementary counting methods, we calculate a universal perturbative invariant (also known as the LMO invariant) of a 3-manifold M, satisfying , in terms of the Alexander polynomial of M. We show that +1 surgery on a knot in the 3-sphere induces an injective map from finite type invariants of integral homology 3-spheres to finite type invariants of knots. We also show that weight systems of degree 2m on knots, obtained by applying finite type 3m invariants of integral homology 3-spheres, lie in the algebra of Alexander-Conway weight systems, thus answering the questions raised in [Ga]. Received: 27 April 1998 / in final form: 8 August 1999     

Two constructions of weight systems for invariants of knots in non-trivial 3-manifolds

A new family of weight systems of finite type knot invariants of any positive degree in orientable 3-manifolds with non-trivial first homology group is constructed. The principal part of the Casson invariant of knots in such manifolds is split into the sum of infinitely many independent weight systems. Examples of knots separated by corresponding invariants and not separated by any other known finite type invariants are presented.     

Interpolatory integration rules and orthogonal polynomials with varying weights

We investigate which types of asymptotic distributions can be generated by the knots of convergent sequences of interpolatory integration rules. It will turn out that the class of all possible distributions can be described exactly, and it will be shown that the zeros of polynomials that are orthogonal with respect to varying weight functions are good candidates for knots of integration rules with a prescribed asymptotic distribution.Research supported by the Deutsche Forschungsgemeinschaft (AZ: Sta 299/4-2).     

Diagram Invariants of Knots and the Kontsevich Integral

This paper is devoted to the solution of the integration problem for higher derivatives of finite-type invariants (so-called weight systems) up to real invariants defined on the space of knots. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 19, Topology and Noncommutative Geometry, 2004.     

Simple Cubature Formulas with High Polynomial Exactness

We study cubature formulas for d -dimensional integrals with arbitrary weight function of tensor product form. We present a construction that yields a high polynomial exactness: for fixed degree, the number of knots depends on the dimension in an order-optimal way. The cubature formulas are universal: the order of convergence is almost optimal for two different scales of function spaces. The construction is simple: a small number of arithmetical operations is sufficient to compute the knots and the weights of the formulas. August 25, 1997. Date revised: December 3, 1998. Date accepted: March 3, 1999.     

Linearly Derived Steiner Triple Systems

We attach a graph to every Steiner triple system. The chromatic number of this graph is related to the possibility of extending the triple system to a quadruple system. For example, the triple systems with chromatic number one are precisely the classical systems of points and lines of a projective geometry over the two-element field, the Hall triple systems have chromatic number three (and, as is well-known, are extendable) and all Steiner triple systems whose graph has chromatic number two are extendable. We also give a configurational characterization of the Hall triple systems in terms of mitres.     

How to build all Chebyshevian spline spaces good for geometric design?

In the present work we determine all Chebyshevian spline spaces good for geometric design. By Chebyshevian spline space we mean a space of splines with sections in different Extended Chebyshev spaces and with connection matrices at the knots. We say that such a spline space is good for design when it possesses blossoms. To justify the terminology, let us recall that, in this general framework, existence of blossoms (defined on a restricted set of tuples) makes it possible to develop all the classical geometric design algorithms for splines. Furthermore, existence of blossoms is equivalent to existence of a B-spline bases both in the spline space itself and in all other spline spaces derived from it by insertion of knots. We show that Chebyshevian spline spaces good for design can be described by linear piecewise differential operators associated with systems of piecewise weight functions, with respect to which the connection matrices are identity matrices. Many interesting consequences can be drawn from the latter characterisation: as an example, all Chebsyhevian spline spaces good for design can be built by means of integral recurrence relations.     

广义Pòlya组合计数方法

文中引入了P-置换图的概念．作为置换群的指标多项式和函数等价类配置多项式的推广形式分别定义了P-置换图的容量指标多项式与色权多项式,并给出了递归公式和相关定理,由此建立了计算P-置换图的色权多项式的一般方法和P-置换图的色轨道多项式的表达公式．Polya计数定理是这一公式当约束图是空图时的特例．最后给出了P-置换图的色权多项式的一些基本性质和两个计算实例．     

On \pi-hyperbolic knots with the same 2-fold branched coverings

We consider the following problem from the Kirby's list (Problem 3.25): Let K be a knot in and M(K) its 2-fold branched covering space. Describe the equivalence class [K] of K in the set of knots under the equivalence relation if is homeomorphic to . It is known that there exist arbitrarily many different hyperbolic knots with the same 2-fold branched coverings, due to mutation along Conway spheres. Thus the most basic class of knots to investigate are knots which do not admit Conway spheres. In this paper we solve the above problem for knots which do not admit Conway spheres, in the following sense: we give upper bounds for the number of knots in the equivalence class [K] of a knot K and we describe how the different knots in the equivalence class of K are related. Received: 3 August 1998 / in final form: 17 June 1999     

Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems

Point-to-Multipoint systems are a kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities. J. L. Marenco: This work supported by UBACYT Grant X036, CONICET Grant 644/98 and ANPCYT Grant 11-09112. A. K. Wagler: This work supported by the Deutsche Forschungsgemeinschaft (Gr 883/9–1).     

Construction of non-alternating knots

We investigate the behaviour of Rasmussen's invariant  under the sharp operation on knots and obtain a lower bound for the sharp unknotting number. This bound leads us to an interesting move that transforms arbitrary knots into non-alternating knots.

     

On composite twisted unknots

Following Mathieu, Motegi and others, we consider the class of possible composite twisted unknots as well as pairs of composite knots related by twisting. At most one composite knot can arise from a particular -twisting of an unknot; moreover a twisting of the unknot cannot be composite if we have applied more than a single full twist. A pair of composite knots can be related through at most one full twist for a particular -twisting, or one summand was unaffected by the twist, or the knots were the right and left handed granny knots. Finally a conjectured characterization of all composite twisted unknots that do arise is given.

     

Polynomial splittings of metabelian von Neumann rho-invariants of knots

We show that if the connected sum of two knots with coprime Alexander polynomials has vanishing von Neumann -invariants associated with certain metabelian representations, then so do both knots. As an application, we give a new example of an infinite family of knots which are linearly independent in the knot concordance group.

     

Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number*

For a graph G and a tree‐decomposition of G, the chromatic number of is the maximum of , taken over all bags . The tree‐chromatic number of G is the minimum chromatic number of all tree‐decompositions of G. The path‐chromatic number of G is defined analogously. In this article, we introduce an operation that always increases the path‐chromatic number of a graph. As an easy corollary of our construction, we obtain an infinite family of graphs whose path‐chromatic number and tree‐chromatic number are different. This settles a question of Seymour (J Combin Theory Ser B 116 (2016), 229–237). Our results also imply that the path‐chromatic numbers of the Mycielski graphs are unbounded.     

Star chromatic numbers of some planar graphs

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551–559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of planar graphs. More precisely, the first family of planar graphs has star chromatic numbers consisting of two alternating infinite decreasing sequences between 3 and 4; the second family of planar graphs has star chromatic numbers forming an infinite decreasing sequence between 3 and 4; and the third family of planar graphs has star chromatic number 7/2. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 33–42, 1998     

All frame-spun knots are slice

Frame-spun knots are constructed by spinning a knot of lower dimension about a framed submanifold of . We show that all frame-spun knots are slice (null-cobordant).

     

Some Examples Related to 4-Genera, Unknotting Numbers and Knot Polynomials

The paper gives examples of knots with equal knot polynomials,but distinct signatures, 4-genera, double branched cover homologygroups and unknotting numbers. This generalizes some examplesgiven by Lickorish and Millett. It is also shown that thereare knots with minimal (crossing number) diagrams of differentunknotting number (thus answering a question of Bleiler), andan alternative proof is given of Rudolph's result that thereare knots of 15n crossings with unit Alexander polynomial and4-genus or unknotting number n.     

A maximal zero-free interval for chromatic polynomials of bipartite planar graphs

It is well known that (-∞,0) and (0,1) are two maximal zero-free intervals for all chromatic polynomials. Jackson [A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993), 325-336] discovered that is another maximal zero-free interval for all chromatic polynomials. In this note, we show that is actually a maximal zero-free interval for the chromatic polynomials of bipartite planar graphs.     

On list coloring Steiner triple systems

We study the list chromatic number of Steiner triple systems. We show that for every integer s there exists n₀=n₀(s) such that every Steiner triple system on n points STS(n) with n≥n₀ has list chromatic number greater than s. We also show that the list chromatic number of a STS(n) is always within a log n factor of its chromatic number. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 314–322, 2009