Ph.D Thesis

Ph.D StudentKotek Tomer
SubjectDefinability of Combinatorial Functions
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Johann Makowsky
Full Thesis textFull thesis text - English Version


In recent years there has been growing interest in graph polynomials, functions from graphs to polynomial rings which are invariant to isomorphism. Graph polynomials encode information about the input graphs e.g. in their evaluations, coefficients, degree and roots.

Many researchers studied specific graph polynomials such as the chromatic polynomial, the Tutte polynomial, the interlace polynomial or the matching polynomial. In this thesis we present a unified logical framework for graph polynomials. Using this framework we compare the definability of graph polynomials which count generalized colorings with that of graph polynomials defined as subset expansions. We show that many graph parameters cannot be evaluations or coefficients of the prominent graph polynomials studied in the literature. We consider the complexity of a specific graph polynomial, the Ising polynomial, as a case study of a conjecture by J.A. Makowsky from 2008 on the complexity of definable graph polynomials.

We also consider the definability of sequences of integers and of polynomials that have recurrence relations. We give a representation theorem for sequences satisfying recurrence relations in terms of positional weights. This theorem extends a theorem by N. Chomsky and M.P. Schutzenberger for sequences of integers satisfying linear recurrence relations with constant coefficients. For P-recursive integer sequences, sequences which satisfy linear recurrences with polynomial coefficients, we give a representation in terms of counting lattice paths in appropriate lattices.