Two dimensional coordinate polynomials and dominant maps

A polynomial in n variables is called a coordinate polynomial if it is a component of a polynomial automorphism of n-space. For n=2 and a ground field of characteristic zero, we show that a polynomial is a coordinate polynomial if its composition with a dominant endomorphism of 2-space is a coordinate polynomial.     

Polynomial Fibonacci–Hessenberg matrices

A Fibonacci–Hessenberg matrix with Fibonacci polynomial determinant is referred to as a polynomial Fibonacci–Hessenberg matrix. Several classes of polynomial Fibonacci–Hessenberg matrices are introduced. The notion of two-dimensional Fibonacci polynomial array is introduced and three classes of polynomial Fibonacci–Hessenberg matrices satisfying this property are given.     

The Las Vergnas polynomial for embedded graphs

The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion–contraction relations, its specialisation to cellularly embedded graphs does not. Here we extend the Las Vergnas polynomial to graphs in pseudo-surfaces. We show that in this setting we can define deletion and contraction for embedded graphs consistently with the deletion and contraction of the underlying matroid perspective, thus yielding a version of the Las Vergnas polynomial with complete recursive definition. This also enables us to obtain a deeper understanding of the relationships among the Las Vergnas polynomial, the Bollobás–Riordan polynomial, and the Krushkal polynomial. We also take this opportunity to extend some of Las Vergnas’ results on Eulerian circuits from graphs in surfaces of low genus to graphs in surfaces of arbitrary genus.     

多项式方程组的主项解耦消元法

本文提出多项式组符号求解的主项解耦 (主项只含主元 )消元法 :视多项式为变元不同幂积的线性组合 ,以主项解耦三角型多项式组 DTS为引导 ,用逐项伪除求余式 ,将多项式组 PS化为与其同解的 DTS.内容涉及 :消元算法、DTS的存在性与结构特性、零点集结构公式等 .亦对 Grobner基法、吴文俊消元法与本文方法之间的相互联系、区别以及特点进行了比较 .研究表明主项解耦消元法适用于一般多项式组且效率较高     

A certain polynomial of a graph and graphs with an extremal number of trees

The polynomial we consider here is the characteristic polynomial of a certain (not adjacency) matrix associated with a graph. This polynomial was introduced in connection with the problem of counting spanning trees in graphs [8]. In the present paper the properties of this polynomial are used to construct some classes of graphs with an extremal numbers of spanning trees.     

Relations Between M?bius and Coboundary Polynomials

It is known that, in general, the coboundary polynomial and the M?bius polynomial of a matroid do not determine each other. Less is known about more specific cases. In this paper, we will investigate if it is possible that the M?bius polynomial of a matroid, together with the M?bius polynomial of the dual matroid, define the coboundary polynomial of the matroid. In some cases, the answer is affirmative, and we will give two constructions to determine the coboundary polynomial in these cases.     

Laws of large numbers for polynomial hypergroups and some applications

There are introduced moments on polynomial hypergroups. These moments are used to prove strong laws of large number (SSLLNs) for random walks on the nonnegative integers that are homogeneous with respect to a polynomial hypergroup where SLLNs of different kind appear for polynomial hypergroups thth different properties. Furthermore, we discuss polynomial hypergroups that are associated with some discrete semigroups in a canonical way, and, using SLLNs for polynomial hypergroups, we get SLLNs for isotropic random walks on some discrete semigroups.     

Average case tractability of non-homogeneous tensor product problems with the absolute error criterion

We study average case tractability of non-homogeneous tensor product problems with the absolute error criterion. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For general non-homogeneous tensor product problems, we obtain the matching necessary and sufficient conditions for strong polynomial tractability in terms of the one-dimensional eigenvalues. We give some examples to show that strong polynomial tractability is not equivalent to polynomial tractability, and polynomial tractability is not equivalent to quasi-polynomial tractability. But for non-homogeneous tensor product problems with decreasing eigenvalues, we prove that strong polynomial tractability is always equivalent to polynomial tractability, and strong polynomial tractability is even equivalent to quasi-polynomial tractability when the one-dimensional largest eigenvalues are less than one. In particular, we find an example that quasi-polynomial tractability with the absolute error criterion is not equivalent to that with the normalized error criterion even if all the one-dimensional largest eigenvalues are one. Finally we consider a special class of non-homogeneous tensor product problems with improved monotonicity condition of the eigenvalues.     

Polynomial Reproduction in Subdivision

We study conditions on the matrix mask of a vector subdivision scheme ensuring that certain polynomial input vectors yield polynomial output again. The conditions are in terms of a recurrence formula for the vectors which determine the structure of polynomial input with this property. From this recurrence, we obtain an algorithm to determine polynomial input of maximal degree. The algorithm can be used in the design of masks to achieve a high order of polynomial reproduction.     

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.     

Construction of polynomial solutions to some boundary value problems for Poisson’s equation

A polynomial solution of the inhomogeneous Dirichlet problem for Poisson’s equation with a polynomial right-hand side is found. An explicit representation of the harmonic functions in the Almansi formula is used. The solvability of a generalized third boundary value problem for Poisson’s equation is studied in the case when the value of a polynomial in normal derivatives is given on the boundary. A polynomial solution of the third boundary value problem for Poisson’s equation with polynomial data is found.     

A note on the matching numbers of triangle-free graphs

For the sake of brevity the absolute values of the coefficients of the matching polynomial of a graph are called matching numbers in this note. It is shown that for a triangle-free graph these numbers coincide with the coefficients of the chromatic polynomial of its complement when this polynomial is written in factorial form. As an application it is mentioned that the coefficients of every rook polynomial are at the same time coefficients of some chromatic polynomial.     

A note on the complexity of a phaseless polynomial interpolation

In this paper we revisit the classical problem of polynomial interpolation, with a slight twist; namely, polynomial evaluations are available up to a group action of the unit circle on the complex plane. It turns out that this new setting allows for a phaseless recovery of a polynomial in a polynomial time.     

Survey of polynomial transformations between NP-complete problems

This paper aims at being a guide to understand polynomial transformations and polynomial reductions between NP-complete problems by presenting the methodologies for polynomial reductions/transformations and the differences between reductions and transformations. To this end the article shows examples of polynomial reductions/transformations and the restrictions to reduce/transform between NP-complete problems. Finally, this paper includes a digraph with the historical reductions/transformations between instances of NP-complete problems and introduces the term family of polynomial transformations.     

Uniform Approximation by the Highest Defect Continuous Polynomial Splines: Necessary and Sufficient Optimality Conditions and Their Generalisations

In this paper necessary and sufficient optimality conditions for uniform approximation of continuous functions by polynomial splines with fixed knots are derived. The obtained results are generalisations of the existing results obtained for polynomial approximation and polynomial spline approximation. The main result is two-fold. First, the generalisation of the existing results to the case when the degree of the polynomials, which compose polynomial splines, can vary from one subinterval to another. Second, the construction of necessary and sufficient optimality conditions for polynomial spline approximation with fixed values of the splines at one or both borders of the corresponding approximation interval.     

A relation between the LG polynomial and the Kauffman polynomial

We give an explicit formula for the fact given by Links and Gould that a one variable reduction of the LG polynomial coincides with a one variable reduction of the Kauffman polynomial. This implies that the crossing number of an adequate link may be obtained from the LG polynomial by using a result of Thistlethwaite. We also give some evaluations of the LG polynomial.     

Construction of polynomial solutions to the Dirichlet problem for the polyharmonic equation in a ball

An algorithm is proposed for the analytical construction of a polynomial solution to Dirichlet problem for an inhomogeneous polyharmonic equation with a polynomial right-hand side and polynomial boundary data in the unit ball.     

Solving polynomial least squares problems via semidefinite programming relaxations

A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial semidefinite programs to reduce degrees of the polynomials are discussed. Computational efficiency of solving the original polynomial least squares problem and the transformed polynomial semidefinite programs is compared. Numerical results on selected polynomial least square problems show better computational performance of a transformed polynomial semidefinite program, especially when degrees of the polynomials are larger.     

Trivalent orbit polynomial graphs

We introduce orbit polynomial graphs, and discuss their connections with distance- transitive, distance-regular, and distance polynomial graphs. After some general results, we classify all of the nonsymmetric trivalent orbit polynomial graphs.     

Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations

In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples.