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 61-754),

Short description

We aim at developing a general theory of graph polynomials. We plan to study inter-reducibilities 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 model-theoretic, 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:

Spring 2007: Graduate Seminar 238900 Complexity of Counting
Fall 2006: Graduate Seminar 238900 Graph polynomials and graph decompositions
Spring 2005: Seminar 236601 Logical Methods in Combinatorics
2001: Seminar 236605 Complexity of Combinatorial Counting

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 second-order logic", Discrete Applied Mathematics Volume 108, Issues 1-2, 15 February 2001, Pages 23-52 download
- B. Courcelle, J.A. Makowsky, U. Rotics, "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width", Theory of Computing Systems, Volume 33, Number 2 / April, 2000, 125-150. 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 Bollobas-Riordan Polynomial: Exceptional points and uniform reductions", download Accepted for 3rd International Computer Science Symposium in Russia (CSR 2008) June 7-12, 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 MSOL-definable 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 7-11, 2009, Chennai, India, pp. 51-64 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 15th-20th September 2008, Bertinoro, Italy
B. Godlin, T. Kotek and J.A. Makowsky,
"Evaluations of Graph Polynomials", download WG 2008, 34th International Workshop on Graph-Theoretic 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 Graph-Theoretic 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 Feferman-Vaught Theorem" Annals of Pure and Applied Logic, 126 (1-3) April 2004, pp. 159-213. 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. 266-279.
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:quant-ph/0611156v1 (2007) download
E. Fischer, J.A. Makowsky and E.R. Ravve, Counting truth assignments of formulas of bounded tree-width or clique-width, 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. 330-341. download
J.A. Makowsky, U. Rotics, I. Averbouch and B. Godlin, "Computing graph polynomials on graphs of bounded clique-width" In: Proceedings of WG06, H. Bodlaender et al. eds, LNCS 4271 (2006) 191-204. download
J.A. Makowsky, Coloured Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width, Discrete Applied Mathematics . 145 (2005) pp. 276-290. download

Special session at the AMS-ASL-09 meeting

Organized by M. Grohe and J.A. Makowsky.

Funding

Funded by ISF-Grant "Model Theoretic Interpretations of Counting Functions" 2007-2010