A logician's view of graph polynomials

Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.     

Jones多项式的零点

利用数论理论证明了纽结的Jones多项式仅有可能的有理根是O,而链环的Jones多项式仅有可能的有理根是0和-1.给出了作为Jones多项式根的所有可能单位根,以及所有可能的具有平凡Mahler测度的Jones多项式.最后指出了交叉数不超过11的纽结中,只有4_1,8_9,9_(42),K11n19的Jones多项式具有平凡的Mahler测度,从而回答了林晓松提出的关于Mahler测度的一个问题.     

On the Location of Roots of Graph Polynomials

Roots of graph polynomials such as the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others are widely studied. In this paper we examine to what extent the location of these roots reflects the graph theoretic properties of the underlying graph.     

Genocchi polynomials associated with the Umbral algebra

The aim of this paper is to study on the Genocchi polynomials of higher order on P, the algebra of polynomials in the single variable x over the field C of characteristic zero and P^∗, the vector spaces of all linear functional on P. By using the action of a linear functional L on a polynomial p(x) Sheffer sequences and Appell sequences, we obtain some fundamental properties of the Genocchi polynomials. Furthermore, we give relations between, the first and second kind Stirling numbers, Euler polynomials of higher order and Genocchi polynomials of higher order.     

A graph-theoretic approach to a partial order of knots and links

We say that a link L₁ is an s-major of a link L₂ if any diagram of L₁ can be transformed into a diagram of L₂ by changing some crossings and smoothing some crossings. This relation is a partial ordering on the set of all prime alternating links. We determine this partial order for all prime alternating knots and links with the crossing number less than or equal to six. The proofs are given by graph-theoretic methods.     

Spectral properties of matrix polynomials in the max algebra

We consider the spectral properties of matrix polynomials over the max algebra. In particular, we show how the Perron-Frobenius theorem for the max algebra extends to such polynomials and illustrate the relevance of this for multistep difference equations in the max algebra. We also present a number of inequalities for the largest max eigenvalue of a matrix polynomial.     

The algebra of linear functionals on polynomials,with applications to Padé approximation

Some results about the algebra of linear functionals on the vector space of complex polynomials are given. These results have applications to Padé-type and Padé approximation. In particular an expression for the relative error is obtained.     

Several improved asymptotic normality criteria and their applications to graph polynomials

As widely regarded, one of the most classical and remarkable tools to measure the asymptotic normality of combinatorial statistics is due to Harper's real-rooted method proposed in 1967. However, this classical theorem exists some obvious shortcomings, for example, it requests all the roots of the corresponding generating function, which is impossible in general.Aiming to overcome this shortcoming in some extent, in this paper we present an improved asymptotic normality criterion, along with several variant versions, which usually just ask for one coefficient of the generating function, without knowing any roots. In virtue of these new criteria, the asymptotic normality of some usual combinatorial statistics can be revealed and extended. Among which, we introduce the applications to matching numbers and Laplacian coefficients in detail. Some relevant conjectures, proposed by Godsil (Combinatorica, 1981) and Wang et al. (J. Math. Anal. Appl., 2017), are generalized and verified as corollaries.     

Application of computer algebra to affinity-binding equations

In this paper we apply computer algebra to obtain informationon the influence of free ligand concentration on the capacityof an affinity chromatography matrix when the protein to beabsorbed shows cooperative binding. In the case of a dimericprotein, we derive, in particular, an explicit expression forthe (total) concentration of soluble ligand that resultsin maximumbinding to the matrix. In the case of a tetrameric protein,we derive an expression that relates the yield to the parametersof the system and solve it numerically.     

Strong coprimality and strong irreducibility of Alexander polynomials

A polynomial f(t) with rational coefficients is strongly irreducible if f(tk) is irreducible for all positive integers k. Likewise, two polynomials f and g are strongly coprime if f(tk) and g(tl) are relatively prime for all positive integers k and l. We provide some sufficient conditions for strong irreducibility and prove that the Alexander polynomials of twist knots are pairwise strongly coprime and that most of them are strongly irreducible. We apply these results to describe the structure of the subgroup of the rational knot concordance group generated by the twist knots and to provide an explicit set of knots which represent linearly independent elements deep in the solvable filtration of the knot concordance group.     

On sequences of Hurwitz polynomials related to orthogonal polynomials

ABSTRACT

In this contribution, we explore the well-known connection between Hurwitz and orthogonal polynomials. Namely, given a Hurwitz polynomial, it is shown that it can be decomposed into two parts: a polynomial that is orthogonal with respect to some positive measure supported in the positive real axis and its corresponding second-kind polynomial. Conversely, given a sequence of orthogonal polynomials with respect to a positive measure supported in the positive real axis, a sequence of Hurwitz polynomials can be constructed. Based on that connection, we construct sequences of Hurwitz polynomials that satisfy a recurrence relation, in a similar way as the orthogonal polynomials do. Even more, we present a way to construct families of Hurwitz polynomials using two sequences of parameters and a recurrence relation that constitutes an analogue of Favard's theorem in the theory of orthogonal polynomials.     

Graded central polynomials for the matrix algebra of order two

Let K be an infinite integral domain, and let A = M ₂(K) be the matrix algebra of order two over K. The algebra A can be given a natural -grading by assuming that the diagonal matrices are the 0-component while the off-diagonal ones form the 1-component. In this paper we study the graded identities and the graded central polynomials of A. We exhibit finite bases for these graded identities and central polynomials. It turns out that the behavior of the graded identities and central polynomials in the case under consideration is much like that in the case when K is an infinite field of characteristic 0 or p > 2. Our proofs are characteristic-free so they work when K is an infinite field, char K = 2. Thus we describe finite bases of the graded identities and graded central polynomials for M ₂(K) in this case as well. A. Krasilnikov has been partially supported by CNPq and FINATEC.     

The relation of the d-orthogonal polynomials to the Appell polynomials

We are dealing with the concept of d-dimensional orthogonal (abbreviated d-orthogonal) polynomials, that is to say polynomials verifying one standard recurrence relation of order d + 1. Among the d-orthogonal polynomials one singles out the natural generalizations of certain classical orthogonal polynomials. In particular, we are concerned, in the present paper, with the solution of the following problem (P): Find all polynomial sequences which are at the same time Appell polynomials and d-orthogonal. The resulting polynomials are a natural extension of the Hermite polynomials.

A sequence of these polynomials is obtained. All the elements of its (d + 1)-order recurrence are explicitly determined. A generating function, a (d + 1)-order differential equation satisfied by each polynomial and a characterization of this sequence through a vectorial functional equation are also given. Among such polynomials one singles out the d-symmetrical ones (Definition 1.7) which are the d-orthogonal polynomials analogous to the Hermite classical ones. When d = 1 (ordinary orthogonality), we meet again the classical orthogonal polynomials of Hermite.     

A class of matrix-valued polynomials generalizing Jacobi polynomials

A hierarchy of matrix-valued polynomials which generalize the Jacobi polynomials is found. Defined by a Rodrigues formula, they are also products of a sequence of differential operators. Each class of polynomials is complete, satisfies a three term recurrence relation, integral inter-relations, and weak orthogonality relations.     

On the roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

关于勒让德多项式与契贝谢夫多项式间的关系

主要研究勒让德多项式与契贝谢夫多项式之间的关系的性质,利用生成函数和函数级数展开的方法,得出了勒让德多项式与契贝谢夫多项式之间的一个重要关系,这对勒让德多项式与契贝谢夫多项式的研究有一定的推动作用．     

On multivariate polynomials in Bernstein-Bézier form and tensor algebra

The Bernstein-Bézier representation of polynomials is a very useful tool in computer aided geometric design. In this paper we make use of (multilinear) tensors to describe and manipulate multivariate polynomials in their Bernstein-Bézier form. As an application we consider Hermite interpolation with polynomials and splines.