Strongly polynomial sequences as interpretations

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10333125" target="_blank" >RIV/00216208:11320/16:10333125 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1016/j.jal.2016.06.001" target="_blank" >http://dx.doi.org/10.1016/j.jal.2016.06.001</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jal.2016.06.001" target="_blank" >10.1016/j.jal.2016.06.001</a>

Result language

angličtina

Original language name

Strongly polynomial sequences as interpretations

Original language description

A strongly polynomial sequence of graphs (G(n)) is a sequence (G(n))(n is an element of N) 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, Nesetril, Tittmann, Zilber and others, various examples of strongly polynomial sequences and constructions for families of such sequences have been found, leading to analogues of the chromatic polynomial for fractional colourings and acyclic colourings, to choose two interesting examples. 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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Applied Logic

ISSN

1570-8683

e-ISSN

—

Volume of the periodical

18

Issue of the periodical within the volume

November

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

21

Pages from-to

129-149

UT code for WoS article

000384954600006

EID of the result in the Scopus database

2-s2.0-84988423230