Strongly polynomial sequences as interpretations

DOI10.1016/J.JAL.2016.06.001zbMATH Open1436.05052arXiv1405.2449OpenAlexW2287806834MaRDI QIDQ334158FDOQ334158

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)

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.

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

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

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)

Cites Work

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

Cited In (7)

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