RECORD
Strongly polynomial sequences as interpretations
Combinatorics · Submitted 10 May 2014
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim This surprisingly easy yet general method encompasses all previous constructions and produces many more.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
A strongly polynomial sequence of graphs $(G_n)$ is a sequence $(G_n)_{n\in\mathbb{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, Ne\v{s}et\v{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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A strongly polynomial sequence of graphs $(G_n)$ is a sequence $(G_n)_{n\in\mathbb{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$). | background 1.00 | 0.09 | 0.03 | asserted 1.00 |
| s1 | 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$. | background 1.00 | 0.11 | 0.02 | asserted 1.00 |
| s2 | In earlier work of de la Harpe and Jaeger, and more recently of Averbouch, Garijo, Godlin, Goodall, Makowsky, Ne\v{s}et\v{r}il, Tittmann, Zilber and others, various examples of strongly polynomial sequences and constructions for families of such sequences have been found. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s3 | 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. | contribution 0.66 | 0.96 | 0.28 | asserted 1.00 |
| s4 | This surprisingly easy yet general method encompasses all previous constructions and produces many more. | result 0.40 | 0.86 | 0.26 | asserted 1.00 |
| s5 | 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). | future work 0.62 | 0.38 | 0.26 | speculative 1.00 |
| s6 | We verify this conjecture for strongly polynomial sequences of graphs with uniformly bounded degree. | result 0.83 | 0.95 | 0.22 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
A strongly polynomial sequence of graphs $(G_n)$ is a sequence $(G_n)_{n\in\mathbb{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, Ne\v{s}et\v{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.
Human review
How the literature uses it
3 arXiv papers cite this in 4 sentences
Papers citing it · 3 sentences without a confident label
Cites it as background 1 paper
-
and in [ref] .
On sequences of polynomials arising from graph invariants · Typical forms of graph polynomials · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.