Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, March 01, 2005, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Johann A. Makowsky (Technion, Haifa)

Iteration Graphs and their Polynomials

Iteration graphs are graph families G_n : n ∈ N constructed from an initial graph G₀ by the repeated application of a fixed graph operation. Simple examples are the paths on n vertices P_n or the rectangular (m × n)-grids G_m,n for fixed m.

N.L. Biggs, R.M. Damerell and D.A. Sands (1972) initiated the study the behaviour of the Tutte polynomial on specific iteration graphs. They showed that in these cases the polynomials T(G_n) satisfy a linear recurrence relation. M. Noy and A. Ribó (2004) extended this observation to a larger class of iteration graphs.

In our work we show that this phenomenon is shared by a wide class of graph polynomials, the MSOL-definable graph polynomials, which include the matching polynomials, the clique and independent set polynomials, the colored Tutte polynomials and many Farrel polynomials. This also includes the Jones polynomial and the Kauffman brackets for knots. We also show that the class of iteration graphs can be generalized and extended to arbitrary relational structures and corresponding generalizations of graph polynomials.

Joint work with Eldar Fischer.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login