A logician's view of graph polynomials
From MaRDI portal
Publication:2273013
DOI10.1016/J.APAL.2019.04.007zbMATH Open1477.03122OpenAlexW2963691321WikidataQ128116912 ScholiaQ128116912MaRDI QIDQ2273013FDOQ2273013
Authors: E. Ravve, Tomer Kotek, Johann A. Makowsky 
Publication date: 18 September 2019
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Abstract: 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. We discuss how to represent and compare graph polynomials by their distinctive power. We introduce the class of graph polynomials definable using Second Order Logic which 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 and 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.
Full work available at URL: https://arxiv.org/abs/1703.02297
Recommendations
generating functionsgraph polynomialsgraph invariantschromatic polynomialsdistinguishing powerzeros of graph polynomials
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Contribution to the Theory of Chromatic Polynomials
- A computational framework for the study of partition functions and graph polynomials
- A criterion for the half-plane property
- A weighted graph polynomial from chromatic invariants of knots
- Algorithmic uses of the Feferman-Vaught theorem
- An extension of the bivariate chromatic polynomial
- Application of logic to combinatorial sequences and their recurrence relations
- Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products
- Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
- Chromatic Roots are Dense in the Whole Complex Plane
- Chromatic invariants for finite graphs: Theme and polynomial variations
- Clique polynomials and independent set polynomials of graphs
- Clique polynomials have a unique root of smallest modulus
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Connection matrices and the definability of graph parameters
- Connections between the matching and chromatic polynomials
- Elements of finite model theory.
- Evaluations of Graph Polynomials
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Graph polynomials and their applications. I: The Tutte polynomial
- Graph polynomials: from recursive definitions to subset expansion formulas
- Homogeneous multivariate polynomials with the half-plane property
- Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
- Hyperbolicity and stable polynomials in combinatorics and probability
- Lee-Yang theorems and the complexity of computing averages
- Linear matrix inequality representation of sets
- Matching theory
- Multivariate stable polynomials: theory and applications
- Necessary and sufficient conditions for the Hurwitz and Schur stability of interval matrices
- Negative dependence and the geometry of polynomials
- On Counting Generalized Colorings
- On counting generalized colorings
- On sequences of polynomials arising from graph invariants
- On the complexity of generalized chromatic polynomials
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- On the location of roots of graph polynomials
- On the location of roots of independence polynomials
- On the roots of edge cover polynomials of graphs
- On the theory of the matching polynomial
- Polynomial graph invariants from homomorphism numbers
- Polynomials with the half-plane property and matroid theory
- Semantic equivalence of graph polynomials definable in second order logic
- Spectra of graphs
- Strongly polynomial sequences as interpretations
- The equivalence of two graph polynomials and a symmetric function
- The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
- The roots of the independence polynomial of a clawfree graph
- The universal edge elimination polynomial and the dichromatic polynomial
- Theory of monomer-dimer systems
- Tutte Polynomials and Link Polynomials
- Tutte-Whitney polynomials: some history and generalizations
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
Cited In (9)
- Weakly distinguishing graph polynomials on addable properties
- Almost unimodal and real-rooted graph polynomials
- Planar polynomial of the graphs
- Harary polynomials
- Graph polynomials: from recursive definitions to subset expansion formulas
- Evaluations of Graph Polynomials
- Semantic equivalence of graph polynomials definable in second order logic
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Logical Approaches to Computational Barriers
This page was built for publication: A logician's view of graph polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2273013)
