A logician's view of graph polynomials

Annals of Pure and Applied Logic 170 (9):1030-1069 (2019)
  Copy   BIBTEX

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. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this 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. It 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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Algorithmic uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
Symmetric and nonsymmetric Macdonald polynomials.Daniel Graham Marshall - 1999 - Annals of Combinatorics 3 (2-4):385-415.
Graph-theoretic Models of Dispositional Structures.Matthew Tugby - 2013 - International Studies in the Philosophy of Science 27 (1):23-39.
Random generations of the countable random graph.Su Gao & A. Vershik - 2006 - Annals of Pure and Applied Logic 143 (1-3):79-86.
Isomorphisms and nonisomorphisms of graph models.Harold Schellinx - 1991 - Journal of Symbolic Logic 56 (1):227-249.
Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Graph Spectra for Communications in Biological and Carbon Nanotube Networks.Stephen F. Bush & Sanjay Goel - forthcoming - Ieee Journal on Selected Areas in Communications:1--10.
On graph-theoretic fibring of logics.A. Sernadas, C. Sernadas, J. Rasga & M. Coniglio - 2009 - Journal of Logic and Computation 19 (6):1321-1357.

Analytics

Added to PP
2019-04-13

Downloads
17 (#742,076)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Algorithmic uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
Finite Model Theory.Heinz-Dieter Ebbinghaus & Torg Flum - 1997 - Studia Logica 58 (2):332-335.

Add more references