کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4662877 1345202 2016 21 صفحه PDF ندارد دانلود رایگان
عنوان انگلیسی مقاله
Strongly polynomial sequences as interpretations
ترجمه فارسی عنوان
توالی به شدت چند جمله ای به عنوان تفسیر
کلمات کلیدی
همریخت نمودار؛ چند جمله ای نمودار؛ ساختار رابطه ای. طرح تفسیر
Graph homomorphism; Graph polynomial; Relational structure; Interpretation scheme
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

A strongly polynomial sequence of graphs (Gn)(Gn) is a sequence (Gn)n∈N(Gn)n∈N of finite graphs such that, for every graph F, the number of homomorphisms from F   to GnGn is a fixed polynomial function of n (depending on F  ). For example, (Kn)(Kn) is strongly polynomial since the number of homomorphisms from F   to KnKn 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šetřil, 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Applied Logic - Volume 18, November 2016, Pages 129–149
نویسندگان
, , ,