Strongly polynomial sequences as interpretations

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Strongly polynomial sequences as interpretations

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Strongly polynomial sequences as interpretations

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název periodika

Journal of Applied Logic

ISSN

1570-8683

e-ISSN

—

Svazek periodika

18

Číslo periodika v rámci svazku

November

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

21

Strana od-do

129-149

Kód UT WoS článku

000384954600006

EID výsledku v databázi Scopus

2-s2.0-84988423230