Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEuler characteristic reciprocity for chromatic, flow and order polynomials
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The Euler characteristic of a semialgebraic set can be considered as a generalization of the cardinality of a finite set. An advantage of semialgebraic sets is that we can define negative sets to be the sets with negative Euler characteristics. Applying this idea to posets, we introduce the notion of semialgebraic posets. Using negative posets, we establish Stanleys reciprocity theorems for order polynomials at the level of Euler characteristics. We also formulate the Euler characteristic reciprocities for chromatic and flow polynomials.
rate research
Read More
We compute the compactly supported Euler characteristic of the space of degree $d$ irreducible polynomials in $n$ variables with real coefficients and show that the values are given by the digits in the so-called balanced binary expansion of the number of variables $n$.
In this paper, we present some properties on chromatic polynomials of hypergraphs which do not hold for chromatic polynomials of graphs. We first show that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers. We then prove that for any multigraph $G=(V,E)$, the number of totally cyclic orientations of $G$ is equal to the value of $|P(H,-1)|$, where $P(H,lambda)$ is the chromatic polynomial of a hypergraph $H$ which is constructed from $G$. Finally we show that the multiplicity of root $0$ of $P(H,lambda)$ may be at least $2$ for some connected hypergraphs $H$, and the multiplicity of root $1$ of $P(H,lambda)$ may be $1$ for some connected and separable hypergraphs $H$ and may be $2$ for some connected and non-separable hypergraphs $H$.
The aim of the article is to understand the combinatorics of snake graphs by means of linear algebra. In particular, we apply Kasteleyns and Temperley--Fishers ideas about spectral properties of weighted adjacency matrices of planar bipartite graphs to snake graphs. First we focus on snake graphs whose set of turning vertices is monochromatic. We provide recursive sequences to compute the characteristic polynomials; they are indexed by the upper or the lower boundary of the graph and are determined by a neighbour count. As an application, we compute the characteristic polynomials for L-shaped snake graphs and staircases in terms of Fibonacci product polynomials. Next, we introduce a method to compute the characteristic polynomials as convergents of continued fractions. Finally, we show how to transform a snake graph with turning vertices of two colours into a graph with the same number of perfect matchings to which we can apply the results above.
We give a local Euler-Maclaurin formula for rational convex polytopes in a rational euclidean space . For every affine rational polyhedral cone C in a rational euclidean space W, we construct a differential operator of infinite order D(C) on W with constant rational coefficients, which is unchanged when C is translated by an integral vector. Then for every convex rational polytope P in a rational euclidean space V and every polynomial function f (x) on V, the sum of the values of f(x) at the integral points of P is equal to the sum, for all faces F of P, of the integral over F of the function D(N(F)).f, where we denote by N(F) the normal cone to P along F.
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious colorings, convex colorings, mcc_t-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial $chi(G;X)$ is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcc_t-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
