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.     

The bivariate Ising polynomial of a graph

In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial.     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

Gale duality bounds for roots of polynomials with nonnegative coefficients

We bound the location of roots of polynomials that have nonnegative coefficients with respect to a fixed but arbitrary basis of the vector space of polynomials of degree at most d. For this, we interpret the basis polynomials as vector fields in the real plane, and at each point in the plane analyze the combinatorics of the Gale dual vector configuration. This approach permits us to incorporate arbitrary linear equations and inequalities among the coefficients in a unified manner to obtain more precise bounds on the location of roots. We apply our technique to bound the location of roots of Ehrhart and chromatic polynomials. Finally, we give an explanation for the clustering seen in plots of roots of random polynomials.     

Degenerate difference-differential equations: Algebraic theory

In this paper we consider the algebraic aspects of the theory of degenerate difference-differential equations. It will be shown that the fundamental algebraic concepts to be used are module theoretic. We have to consider similarity of polynomial matrices in one or more indeterminates. In the case of systems with commensurable lags the underlying modules have a simple structure, because the corresponding ring of scalars is the principal ideal domain of polynomials in one indeterminate. This fact makes it possible to prove a structure theorem for degenerate difference-differential equations with commensurable lags. This theorem shows that degenerate systems of this type essentially are trivial in the sense of Henry [15], i.e., the characteristic quasipolynomial is a polynomial. Further it is shown that coordinate transforms with “time lag” play an essential role for the construction of degenerate equations. The power of the method is demonstrated by some examples, some of which are equations with incommensurable lags.     

A family of Bell transformations

We introduce a family of sequence transformations, defined via partial Bell polynomials, that may be used for a systematic study of a wide variety of problems in enumerative combinatorics. This family includes some of the transformations listed in the paper by Bernstein & Sloane, now seen as transformations under the umbrella of partial Bell polynomials. Our goal is to describe these transformations from the algebraic and combinatorial points of view. We provide functional equations satisfied by the generating functions, derive inverse relations, and give a convolution formula. While the full range of applications remains unexplored, in this paper we show a glimpse of the versatility of Bell transformations by discussing the enumeration of several combinatorial configurations, including rational Dyck paths, rooted planar maps, and certain classes of permutations.     

Algebraic Cayley graphs over finite local rings

In this work, we define and study the algebraic Cayley directed graph over a finite local ring. Its vertex set is the unit group of a finite extension of a finite local ring R and its adjacency condition is that the quotient is a monic primary polynomial. We investigate its connectedness and diameter bound, and we also show that our graph is an expander graph. In addition, if a local ring has nilpotency two, then we obtain a better view of our graph from the lifting of the graph over its residue field.     

A class of highly symmetric graphs,symmetric cylindrical constructions and their spectra

In this article, we introduce the algebra of block-symmetric cylinders and we show that symmetric cylindrical constructions on base-graphs admitting commutative decompositions behave as generalized tensor products. We compute the characteristic polynomial of such symmetric cylindrical constructions in terms of the spectra of the base-graph and the cylinders in a general setting. This gives rise to a simultaneous generalization of some well-known results on the spectra of a variety of graph amalgams, as various graph products, graph subdivisions and generalized Petersen graph constructions. While our main result introduces a connection between spectral graph theory and commutative decompositions of graphs, we focus on commutative cyclic decompositions of complete graphs and tree-cylinders along with a subtle group labeling of trees to introduce a class of highly symmetric graphs containing the Petersen and the Coxeter graphs. Also, using techniques based on recursive polynomials we compute the characteristic polynomials of these highly symmetric graphs as an application of our main result.     

Identities involving Narayana polynomials and Catalan numbers

We first establish the result that the Narayana polynomials can be represented as the integrals of the Legendre polynomials. Then we represent the Catalan numbers in terms of the Narayana polynomials by three different identities. We give three different proofs for these identities, namely, two algebraic proofs and one combinatorial proof. Some applications are also given which lead to many known and new identities.     

A conjecture on the algebraic connectivity of connected graphs with fixed girth

In this paper, we completely solve a conjecture on the minimum algebraic connectivity of connected graphs with fixed girth (see [S. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74]).     

Coconvex approximation in the uniform norm: the final frontier

Summary The paper deals with approximation of a continuous function, on a finite interval, which changes convexity finitely many times, by algebraic polynomials which are coconvex with it. We give final answers to open questions concerning the validity of Jackson type estimates involving the weighted Ditzian-Totik moduli of smoothness.     

ADDITIVE POLYNOMIALS AND PRIMITIVE ROOTS OVER FINITE FIELDS

We prove existence of primitive roots with a prescribed non-zero image using the arithmetic of algebraic function fields for a class of polynomials over sufficiently large finite fields.     

Local permutation polynomials and the action of e-Klenian groups

Permutation polynomials of finite fields have many applications in Coding Theory, Cryptography and Combinatorics. In the first part of this paper we present a new family of local permutation polynomials based on a class of symmetric subgroups without fixed points, the so called e-Klenian groups. In the second part we use the fact that bivariate local permutation polynomials define Latin Squares, to discuss several constructions of Mutually Orthogonal Latin Squares (MOLS) and, in particular, we provide a new construction of MOLS on size a prime power.     

Reductions of the graph reconstruction conjecture

In this note we shall show that the Graph Reconstruction Conjecture (also called the Kelly-Ulam conjecture [1, p. 11]) is equivalent to a conjecture about the algebraic properties of certain directed trees and their homomorphic images. We shall show the the Greph Reconstruction Conjecture is equivalent to recognizing the (abstract) group of a graph from the tree (generalized “deck”) of the graph.     

The polynomial Fourier transform with minimum mean square error for noisy data

In 2006, Naoki Saito proposed a Polyharmonic Local Fourier Transform (PHLFT) to decompose a signal f∈L²(Ω) into the sum of a polyharmonic componentu and a residualv, where Ω is a bounded and open domain in R^d. The solution presented in PHLFT in general does not have an error with minimal energy. In resolving this issue, we propose the least squares approximant to a given signal in L²([−1,1]) using the combination of a set of algebraic polynomials and a set of trigonometric polynomials. The maximum degree of the algebraic polynomials is chosen to be small and fixed. We show in this paper that the least squares approximant converges uniformly for a Hölder continuous function. Therefore Gibbs phenomenon will not occur around the boundary for such a function. We also show that the PHLFT converges uniformly and is a near least squares approximation in the sense that it is arbitrarily close to the least squares approximant in L² norm as the dimension of the approximation space increases. Our experiments show that the proposed method is robust in approximating a highly oscillating signal. Even when the signal is corrupted by noise, the method is still robust. The experiments also reveal that an optimum degree of the trigonometric polynomial is needed in order to attain the minimal l² error of the approximation when there is noise present in the data set. This optimum degree is shown to be determined by the intrinsic frequency of the signal. We also discuss the energy compaction of the solution vector and give an explanation to it.     

On Bellissima’s construction of the finitely generated free Heyting algebras, and beyond

We study finitely generated free Heyting algebras from a topological and from a model theoretic point of view. We review Bellissima’s representation of the finitely generated free Heyting algebra; we prove that it yields an embedding in the profinite completion, which is also the completion with respect to a naturally defined metric. We give an algebraic interpretation of the Kripke model used by Bellissima as the principal ideal spectrum and show it to be first order interpretable in the Heyting algebra, from which several model theoretic and algebraic properties are derived. In particular, we prove that a free finitely generated Heyting algebra has only one set of free generators, which is definable in it. As a consequence its automorphism group is the permutation group over its generators.     

A note on immersion minors and planarity

Graph minors play an important role in graph theory. The focus of this paper is on immersion minors and their relationship to planarity. In general, planar graphs can have non-planar immersion minors. This paper shows that by placing a simple restriction on the immersion-minor operations, all immersion minors of a planar graph are planar. This then allows one to easily obtain a characterization of planar graphs using immersion minors. A dual form of this characterization, as well as an extension to binary matroids, are also considered.     

A Branch-and-Cut algorithm for graph coloring

In this paper a Branch-and-Cut algorithm, based on a formulation previously introduced by us, is proposed for the Graph Coloring Problem. Since colors are indistinguishable in graph coloring, there may typically exist many different symmetrical colorings associated with a same number of colors. If solutions to an integer programming model of the problem exhibit that property, the Branch-and-Cut method tends to behave poorly even for small size graph coloring instances. Our model avoids, to certain extent, that bottleneck. Computational experience indicates that the results we obtain improve, in most cases, on those given by the well-known exact solution graph coloring algorithm Dsatur.     

Nonzero Component Graph of a Finite Dimensional Vector Space

In this article, we introduce a graph structure, called a nonzero component graph on finite dimensional vector spaces. We show that the graph is connected and find its domination number and independence number. We also study the inter-relationship between vector space isomorphisms and graph isomorphisms, and it is shown that two graphs are isomorphic if and only if the corresponding vector spaces are so. Finally, we determine the degree of each vertex in case the base field is finite.     

Maximizing Algebraic Connectivity Over Unicyclic Graphs

We consider the class of unicyclic graphs on n vertices with girth g, and over that class, we attempt to determine which graph maximizes the algebraic connectivity. When g is fixed, we show that there is an N such that for each n>N, the maximizing graph consists of a g cycle with n?g pendant vertices adjacent to a common vertex on the cycle. We also provide a bound on N. On the other hand, when g is large relative to n, we show that this graph does not maximize the algebraic connectivity, and we give a partial discussion of the nature of the maximizing graph in that situation.