An explicit height bound for the classical modular polynomial

For a prime l, let Φ _l be the classical modular polynomial, and let h(Φ _l ) denote its logarithmic height. By specializing a theorem of Cohen, we prove that \(h(\Phi_{l})\le 6l\log l+16l+14\sqrt{l}\log l\). As a corollary, we find that h(Φ _l )≤6llog?l+18l also holds. A table of h(Φ _l ) values is provided for l≤3600.     

Finding minimum height elimination trees for interval graphs in polynomial time

The elimination tree plays an important role in many aspects of sparse matrix factorization. The height of the elimination tree presents a rough, but usually effective, measure of the time needed to perform parallel elimination. Finding orderings that produce low elimination is therefore important. As the problem of finding minimum height elimination tree orderings is NP-hard, it is interesting to concentrate on limited classes of graphs and find minimum height elimination trees for these efficiently. In this paper, we use clique trees to find an efficient algorithm for interval graphs which make an important subclass of chordal graphs. We first illustrate this method through an algorithm that finds minimum height elimination for chordal graphs. This algorithm, although of exponential time complexity, is conceptionally simple and leads to a polynomial-time algorithm for finding minimum height elimination trees for interval graphs.This work was supported by grants from the Norwegian Research Council.     

Multiplication of a Schubert polynomial by a Schur polynomial

Schur polynomials are a special case of Schubert polynomials. In this paper, we give an algorithm to compute the product of a Schubert polynomial with a Schur polynomial on the basis of Schubert polynomials. This is a special case of the general problem of the multiplication of two Schubert polynomials, where the corresponding algorithm is still missing. The main tools for the given algorithm is a factorization property of a special class of Schubert polynomials and the transition formula for Schubert polynomials.     

On the derivative of a polynomial

For an entire function f(z), let . If p(z) is a polynomial of degree n, then, in general, it is difficult to obtain a lower bound for M(p′, 1). But if the zeros of the polynomial are close to the origin, then various lower bounds for M(p′, 1) have been obtained in the past. In this paper, we have considered polynomials having all their zeros in ⋎z⋎≤k(k≥1), with a possible zero of order m(m≥0) at the origin and have obtained a lower bound for M(p′, 1), which is better than most of the known lower bounds. Our bound is sharp for m=0.     

The characteristic polynomial and the matchings polynomial of a weighted oriented graph

Let $G^{\sigma }$ be a weighted oriented graph with skew adjacency matrix $S(G^{\sigma })$. Then $G^{\sigma }$ is usually referred as the weighted oriented graph associated to $S(G^{\sigma })$. Denote by $?(G^{\sigma }\text{;}\lambda )$ the characteristic polynomial of the weighted oriented graph $G^{\sigma }$, which is defined as$?(G^{\sigma }\text{;}\lambda )=\mathit{det}(\lambda I_n-S(G^{\sigma }))=\sum _{i=0}^n{a}_i(G^{\sigma }){\lambda }^{n-i}\text{.}$In this paper, we begin by interpreting all the coefficients of the characteristic polynomial of an arbitrary real skew symmetric matrix in terms of its associated oriented weighted graph. Then we establish recurrences for the characteristic polynomial and deduce a formula on the matchings polynomial of an arbitrary weighted graph. In addition, some miscellaneous results concerning the number of perfect matchings and the determinant of the skew adjacency matrix of an unweighted oriented graph are given.     

On the zeros of a polynomial

For a polynomial of degree n, we have obtained an upper bound involving coefficients of the polynomial, for moduli of its p zeros of smallest moduli, and then a refinement of the well-known Eneström-Kakeya theorem (under certain conditions).     

On the polynomial of a path

Let A(P_n) be the adjacency matrix of the path on n vertices. Suppose that r(λ) is a polynomial of degree less than n, and consider the matrix M = r(A>/(P_n)). We determine all polynomials for which M is the adjacency matrix of a graph.     

Inequalities for the derivative of a polynomial

Let P(z) be a polynomial of degreen which does not vanish in ¦z¦ <k, wherek > 0. Fork ≤ 1, it is known that

$$\mathop {\max }\limits_{|z| = 1} |P'(z)| \leqslant \frac{n}{{1 + k^n }}\mathop {\max }\limits_{|z| = 1} |P(z)|$$

, provided ¦P’(z)¦ and ¦Q’(z)¦ become maximum at the same point on ¦z¦ = 1, where\(Q(z) = z^n \overline {P(1/\bar z)} \). In this paper we obtain certain refinements of this result. We also present a refinement of a generalization of the theorem of Tu?an.

     

On the hermite matrix of a polynomial

We investigate the location of the eigenvalues of the Hermite matrix of a given complex polynomial, the question under what conditions a given polynomial and the characteristic polynomial of its Hermite matrix are identical, and the question under what conditions the Hermite matrix has only one distinct eigenvalue.     

On the minimal polynomial of a resolvent

We derive the connection between the minimal polynomial of an operator and the minimal polynomial of its resolvent. An analogous result is obtained for the minimal polynomials of the iterated resolvents.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

On a polynomial inequality

Let p(z)=a₀+?+anzn and q(z)=b₀+? be polynomials of degree respectively n and less than n such that

     

Bounds on a polynomial

Methods are given for isolating and approximating the maxima, minima, and real roots of a polynomial with real coefficients. The methods are based on a variation diminishing property of the Bernstein coefficients of the polynomial and use of a recursive bisection technique.     

Finding the number of factors of a polynomial

Because computing modulo small primes is so cheap there is a common hope that global properties of polynomials might be easily deduced from such computations. The number of factors can be found, assuming suitable Riemann hypotheses, but in many interesting cases it is not possible to find the Galois group.     

On the ratio of values of a polynomial

For given positive integersa andb, the equationa(x + 1)… (x + k) =b(y+1)… (y + k) in positive integers is considered. More general equations are also considered.     

Simultaneous inclusion of the zeros of a polynomial

Summary A family of inclusion sets for the zeros of a complex polynomial is derived from the Lagrangean interpolation formulas. The optimization of the inclusion leads to a special type of matrix eigenvalue problem previously considered by several authors in connection with minimal Gershgorin discs.