Workshop on Graph Homomorphisms

July 11 - 15, 2011, The Fields Institute

Location: Fields Institute

Description

This workshop will focus on all aspects of graph homomorphisms, from those directly related to constraint satisfaction problems, such as minimum cost and list homomorphisms, versions of projectivity, and polymorphisms, to those related to basic graph theoretic notions such as colourings, tree-width and tree-depth, and those related to notions from category theory, such as adjoint functors, to those related to statistical physics such as counting homomorphisms, and study of connection matrices. The goal is to bring together the main players in all aspects of graph homomorphisms, and share views of new trends and techniques.

Invited Speakers:

Zdenek Dvorak (Charles University)
Jan Foniok (ETH Zurich)
Hamed Hatami (McGill)
Pavol Hell (SFU)
Daniel Kral (Charles University)
Andre Raspaud (University Bordeaux I)
Benoit Larose (Champlain College)
Jarik Nesetril (Charles University)
Patrice Ossona de Mendez (CAMS-CNRS, Paris)
Arash Rafiey (IDSIA, Lugano)
Mark Siggers (Kyungpook University)
Claude Tardif (Royal Military College, Kingston)
Peter Winkler (Dartmouth)
Xuding Zhu (Zhejiang Normal University)

Schedule

Monday, July 11th, 2011
08:50 to 09:00	Welcome and Introductions Pavol Hell, Simon Fraser University, Xuding Zhu, National Sun Yat-sen University, Claude Tardif, Royal Military College of Canada Location:
09:00 to 09:50	Circular colouring of graphs Xuding Zhu, National Sun Yat-sen University Location:
09:50 to 10:20	Problem Session and Contributed Talks Location:
11:20 to 12:10	Random walks and other homomorphisms Peter Winkler, Dartmouth and Dartmouth College Location:
12:10 to 14:10	Lunch Break
14:10 to 15:00	Semi-lattice polymorphisms on reflexive graphs Mark Siggers, Kyungpook National University Location:
15:00 to 15:20	Coffee Break
15:20 to 15:55	Possible Contributed Talks Location:
17:00 to 18:00	Reception

Tuesday, July 12th, 2011
09:00 to 09:50	Minimum cost homomorphism problem for digraphs Arash Rafiey, Indiana State University Location:
09:50 to 10:20	Problem Session and Contributed Talks Location:
11:20 to 12:10	The existence and counting of subgraphs Patrice Ossona de Mendez Location:
12:10 to 14:10	Lunch Break
14:10 to 15:00	On first-order definable H-colorings Jaroslav Nesetril, Charles University Location:
15:00 to 15:20	Coffee Break
15:20 to 15:55	Possible Contributed Talks Location:

Wednesday, July 13th, 2011
09:00 to 09:50	The complexity of the list homomorphism problem for graphs Benoit Larose, Université du Québec à Montréal (UQÀM) Location:
09:50 to 10:20	Problem Session and Contributed Talks Location:
11:20 to 12:10	Homomorphism dichotomy and graph classes Pavol Hell, Simon Fraser University Location:
12:10 to 14:10	Lunch Break
14:10 to 15:00	Algorithmic metatheorems Daniel Kral, Charles University Location:
15:00 to 15:20	Coffee Break
15:20 to 15:55	Possible Contributed Talks Location:

Thursday, July 14th, 2011
09:00 to 09:50	Elementary asympototic extremal graph theory is non-trivial Hamed Hatami, McGill University Location:
09:50 to 10:20	Problem Session and Contributed Talks Location:
11:20 to 12:10	Deciding first-order properties for sparse graphs Zdenek Dvorak, Charles University in Prague Location:
12:10 to 14:10	Lunch Break
14:10 to 15:00	Partitions of graphs with bounded maximum average degree Andre Raspaud, Bordeaux University Location:
15:00 to 15:20	Coffee Break
15:20 to 15:55	Possible Contributed Talks Location:

Friday, July 15th, 2011
09:00 to 09:50	Adjoint functors on digraphs Jan Foniok, Ecole Polytechnique Location:
09:50 to 10:20	Problem Session and Contributed Talks Location:
11:20 to 12:10	Duality and exponential graphs Claude Tardif, Royal Military College of Canada Location:
12:10 to 14:10	Lunch Break
14:10 to 15:00	Possible Contributed Talks Location:
15:00 to 15:20	Coffee Break