Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, November 08, 2007, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Jan Foniok

Generating Tree Duality: A Quest for Deltas and Sproinks

Some polynomial cases of the Constraint Satisfaction Problem are characterised by the existence of a suitable complete set of obstructions. One of the polynomial cases is when there exists a complete set of obstructions that are all trees. In this case the template is said to have tree duality. If a digraph H has tree duality, then also its arc-graph delta(H) has tree duality.

A construction called Sproink is developed such that if H has tree duality, then the set of all Sproinks of all the tree obstructions for H is a complete set of tree obstructions for the arc-graph delta(H). Moreover, starting from digraphs with finite duality repeatedly using products and the arc-graph functor generates a class of digraphs with tree duality. These are definitely not all digraphs with tree duality (because all generated digraphs have the near-unanimity function and have bounded height of tree obstructions) but it remains to see what particular subclass this process actually generates.

Joint work with Claude Tardif.

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

Previous talks by year:   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