The Graph Polynomials Project in Haifa
UNDER CONSTRUCTION, VISIT REGULARLY!
Last updated: 02.07.2012
Previous update: 12.04.2011
NEW PHD THESIS:
Tomer Kotek, "Definability of combinatorial functions"
PhD Thesis, Haifa, June 2012
download
PHD THESIS:
Ilia Averbouch, "Completeness and Universality Properties
of Graph Invariants and Graph Polynomials", PhD Thesis, Haifa, February 2011
download
So many people today  and even professional scientists  seem to me
like someone has seen thousands of trees but has never seen a forest. A
knowledge of the historical and philosophical background gives that kind
of independence from prejudices of his generation from which most scientists
are suffering. This independence created by philosophical insight
is  in my opinion  the mark of distinction between a mere artisan or
specialist and a real seeker after truth.
A. Einstein (from a letter to Robert Thornton, dated 7 December 1944,
Einstein Archive 61754),
Short description
We aim at developing a general theory of graph polynomials.
We plan to study interreducibilities of
parameterized numeric graph invariants and
graph polynomials. The purpose of this
work is to systematize recent emerging work
on graph polynomials and various partition functions
with respect to their combinatorial expressiveness and
computational complexity.
Our methods are modeltheoretic, algebraic and algorithmic.
Participants
Principal Investigator:
J.A. Makowsky
Graduate students of the project:
I. Averbouch,
T. Kotek,
Other graduate students:
B. Godlin,
A. Matsliah,
Courses and Seminars
Last seminar (Fall 2007 and Spring 2008):
 Graduate Seminar 238901:
Partition functions and graph polynomials
Details are given at the
Seminar homepage.
Previous Courses and Seminars:
Collaborators abroad

Bordeaux, France:
B. Courcelle

B. Courcelle,
"A multivariate interlace polynomial", preprint 2007,
download.

B. Courcelle, J.A. Makowsky, U. Rotics,
"On the fixed parameter complexity of graph enumeration problems definable in monadic secondorder logic",
Discrete Applied Mathematics
Volume 108, Issues 12, 15 February 2001, Pages 2352
download

B. Courcelle, J.A. Makowsky, U. Rotics,
"Linear Time Solvable Optimization Problems on Graphs of Bounded CliqueWidth",
Theory of Computing Systems, Volume 33, Number 2 / April, 2000, 125150.
download

Oxford, England:
B. Zilber, see
also the
Oxford Combinatorics Group .

J.A. Makowsky and B. Zilber,
Polynomial invariants of graphs and totally categorical theories, 2006
preprint

Saarbruecken, Germany:
M. Blaeser,
C. Hoffmann

Markus Blaeser, Holger Dell, "The complexity of the cover polynomial".
Proc. 34th Int. Coll. on Automata, Languages, and Programming (ICALP), LNCS 2007.
download

Markus Blaeser, Christian Hoffmann,
"On the Complexity of the Interlace Polynomial",
arXiv:0707.4565 (2007)
download

Markus Blaeser, Holger Dell, J.A. Makowsky,
"Complexity of the BollobasRiordan Polynomial:
Exceptional points and uniform reductions",
download
Accepted for 3rd International Computer Science Symposium in Russia (CSR 2008)
June 712, 2008, Moscow, Russia.

Berlin, Germany:
M. Grohe,
H. Dell
People with related activities
Here is a sample selection of people working on graph polynomials.
Papers
of the Haifa Group
See also
here
for more preprints, slides, etc.
 NEW: (20.3.2011)
Ilia Averbouch, "Completeness and Universality Properties
of Graph Invariants and Graph Polynomials", PhD Thesis, Haifa, February 2011
download

P. Tittmann, I. Averbouch and J.A. Makowsky
"The Enumeration of Vertex Induced Subgraphs with Respect to the
Number of Components"
preprint,
arXive version,
arxiv.org/pdf/0812.4147

B. Godlin, E. Katz and J.A. Makowsky
"Graph polynomials: From recursive definitions to subset expansion formulas",
arXiv download arXiv:0812.1364
 NEW (16.10.2008):
J.A. Makowsky
"Connection Matrices for MSOLdefinable Structural Invariants",
download,
Published version 1 ,
Published version 2,
in LNCS (LNAI) 5378, Proceedings of the
Third Indian Conference on Logic and its Applications,
January 711, 2009,
Chennai, India, pp. 5164
ICLA 2009,

T. Kotek, J.A. Makowsky and B. Zilber
"On Counting Generalized Colorings",
Preprint version,
Published version,
CSL 2008,
17th EACSL Annual Conference on
Computer Science Logic
15th20th September 2008,
Bertinoro, Italy

B. Godlin, T. Kotek and J.A. Makowsky,
"Evaluations of Graph Polynomials",
download WG 2008, 34th International Workshop on GraphTheoretic Concepts in Computer
Science, to appear in LNCS.

I. Averbouch, B. Godlin and J.A. Makowsky,
"A Most General Edge Elimination Polynomial",
download WG 2008, 34th International Workshop on GraphTheoretic Concepts in Computer
Science, to appear in LNCS.

I. Averbouch, B. Godlin and J.A. Makowsky,
"A most general edge elimination graph polynomial"
submitted,
arXiv download arXiv:0712.3112.

J.A. Makowsky,
"Algorithmic uses of the FefermanVaught Theorem"
Annals of Pure and Applied Logic, 126 (13) April 2004, pp. 159213.
download,
preprint

E. Fischer and J.A. Makowsky,
"Linear Recurrence Relations for Graph Polynomials",
download,
in:
A. Avron, et al. (Eds.), Trakhtenbrot Festschrift, LNCS 4800 (2008), pp. 266279.

J.A. Makowsky
"From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials".
Discrete Applied Mathematics (2007),
online first

D. Aharonov, Z. Landau and J.A. Makowsky
"The quantum FFT can be classically simulated". arXiv:quantph/0611156v1 (2007)
download

E. Fischer, J.A. Makowsky and E.R. Ravve,
Counting truth assignments of formulas of bounded treewidth or cliquewidth,
to appear in Discrete Applied mathematics (2007)
download

J.A. Makowsky
"From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials". In:
Logical Approaches to Computational Barriers,
Second Conference on Computability in Europe, CiE 2006, Swansea, UK, July 2006,
Proceedings, Lecture Notes in Computer Science volume 3988, pp. 330341.
download

J.A. Makowsky, U. Rotics, I. Averbouch and B. Godlin,
"Computing graph polynomials on graphs of bounded cliquewidth"
In: Proceedings of WG06, H. Bodlaender et al. eds, LNCS 4271 (2006) 191204.
download

J.A. Makowsky,
Coloured Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width,
Discrete Applied Mathematics . 145 (2005) pp. 276290.
download
Organized by M. Grohe and J.A. Makowsky.
Funding
Funded by ISFGrant "Model Theoretic Interpretations of Counting Functions" 20072010