A logician's view of graph polynomials

Autor: Tomer Kotek, Elena V. Ravve, Johann A. Makowsky
Rok vydání: 2019
Předmět:
Zdroj: Annals of Pure and Applied Logic. 170:1030-1069
ISSN: 0168-0072
DOI: 10.1016/j.apal.2019.04.007
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: