Strongly polynomial sequences as interpretations

DOI10.1016/J.JAL.2016.06.001MaRDI QIDQ334158zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. Ossona de Mendez, Andrew Goodall

Publication date 31 October 2016

Published in Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2449

zbMATH Keywords

graph polynomialgraph homomorphismrelational structureinterpretation scheme

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Model theory of finite structures (03C13) Coloring of graphs and hypergraphs (05C15) Applications of model theory (03C98)

Abstract: A strongly polynomial sequence of graphs $(G_n)$ is a sequence $(G_n{)}_{ninmathbbN}$ of finite graphs such that, for every graph $F$, the number of homomorphisms from $F$ to $G_n$ is a fixed polynomial function of $n$ (depending on $F$). For example, $(K_n)$ is strongly polynomial since the number of homomorphisms from $F$ to $K_n$ is the chromatic polynomial of $F$ evaluated at $n$. In earlier work of de la Harpe and Jaeger, and more recently of Averbouch, Garijo, Godlin, Goodall, Makowsky, Nev{s}etv{r}il, Tittmann, Zilber and others, various examples of strongly polynomial sequences and constructions for families of such sequences have been found. We give a new model-theoretic method of constructing strongly polynomial sequences of graphs that uses interpretation schemes of graphs in more general relational structures. This surprisingly easy yet general method encompasses all previous constructions and produces many more. We conjecture that, under mild assumptions, all strongly polynomial sequences of graphs can be produced by the general method of quantifier-free interpretation of graphs in certain basic relational structures (essentially disjoint unions of transitive tournaments with added unary relations). We verify this conjecture for strongly polynomial sequences of graphs with uniformly bounded degree.

Recommendations

• Polynomial graph invariants from homomorphism numbers
• Polynomial graph invariants from homomorphism numbers
• Revisiting chromatic polynomials of some sequences of graphs.
• Homomorphisms and Polynomial Invariants of Graphs
• Linear Recurrence Relations for Graph Polynomials

Cites work

• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Acyclic colorings of planar graphs
• Chromatic invariants for finite graphs: Theme and polynomial variations
• Counting graph homomorphisms
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Model theory without pain
• On counting generalized colorings
• Polynomial graph invariants from homomorphism numbers
• Quasi-carousel tournaments
• Regularity partitions and the topology of graphons
• The enumeration of vertex induced subgraphs with respect to the number of components

Cited in

(7)

• In praise of homomorphisms
• First-order limits, an analytical perspective
• A logician's view of graph polynomials
• On sequences of polynomials arising from graph invariants
• Polynomial graph invariants from homomorphism numbers
• Regular partitions of gentle graphs
• How I got to like graph polynomials

This page was built for publication: Strongly polynomial sequences as interpretations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334158)