THEMATIC PROGRAMS

December 23, 2024
July - August, 2011
Thematic Program on the Mathematics of Constraint Satisfaction

July 11- 15, 2011
Workshop on Graph Homomorphisms

Organized by Pavol Hell (Simon Fraser University)
Claude Tardif (Royal Military College, Kingston)
Xuding Zhu (Zhejiang Normal University)

OVERVIEW:

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)

Tentative Workshop Schedule (talk titles and abstracts)

Monday July 11
8:50 - 9:00 Welcome and Introduction
Fields Director Edward Bierstone and Workshop Organizers
9:00 - 9:50 Xuding Zhu (Zhejiang Normal University)
Circular colouring of graphs
9:50 - 11:20 problem session and contributed talks
11:20 - 12:10 Peter Winkler (Dartmouth)
Random walks and other homomorphisms
12:10 - 2:10 Lunch Break
2:10 - 3:00 Mark Siggers (Kyungpook University)
Semi-lattice polymorphisms on reflexive graphs
3:00 - 3:20 Coffee Break
3:20 - 3:55 possible contributed talk
4:00 - 5:00 Coxeter Lecture Series
Moshe Vardi (Rice University)

And Logic Begat Computer Science: When Giants Roamed the Earth
5:00 - 6:00 Reception
Fields Atrium
Tuesday July 12
9:00 - 9:50 Arash Rafiey (IDSIA, Lugano)
Minimum cost homomorphism problem for digraphs
9:50 - 11:20 problem session and contributed talks
11:20 - 12:10 Patrice Ossona de Mendez (CAMS-CNRS, Paris)
The existence and counting of subgraphs
12:10 - 2:10 Lunch Break
2:10 - 3:00 Jarik Nesetril (Charles University)
On first-order definable H-colorings
3:00 - 3:20 Coffee Break
3:20 - 3:55 possible contributed talk
4:00 - 5:00 Coxeter Lecture Series
Moshe Vardi (Rice University)

From Philosophical to Industrial Logics
Wednesday July 13
9:00 - 9:50 Benoit Larose (Champlain College)
The complexity of the list homomorphism problem for graphs
9:50 - 11:20 problem session and contributed talks
11:20 - 12:10 Pavol Hell (SFU)
Homomorphism dichotomy and graph classes
12:10 - 2:10 Lunch Break
2:10 - 3:00 Daniel Kral (Charles University)
Algorithmic metatheorems
3:00 - 3:20 Coffee Break
3:20 - 3:55 possible contributed talk
4:00 - 5:00 Coxeter Lecture Series
Moshe Vardi (Rice University)

Logic, Automata, Games, and Algorithms
Thursday July 14
9:00 - 9:50 Hamed Hatami (McGill)
Elementary asympototic extremal graph theory is non-trivial
9:50 - 11:20 problem session and contributed talks
11:20 - 12:10 Zdenek Dvorak (Charles University)
Deciding first-order properties for sparse graphs
12:10 - 2:10 Lunch Break
2:10 - 3:00 Andre Raspaud (University Bordeaux I)
Partitions of graphs with bounded maximum average degree
3:00 - 3:20 Coffee Break
3:20 - 3:55 possible contributed talks
Friday July 15
9:00 - 9:50 Jan Foniok (École Polytechnique (ParisTech))
Adjoint functors on digraphs
9:50 - 11:20 problem session and contributed talks
11:20 - 12:10 Claude Tardif (Royal Military College of Canada)
Duality and exponential graphs
12:10 - 2:10 Lunch Break
2:10 - 3:00 possible contributed talks
3:00 - 3:20 Coffee Break
3:20 - 3:55 possible contributed talks

 

Confirmed Participants

Full Name University/Affiliation
Andrews, Rob (no affiliation)
Barto, Libor McMaster University
Bisson, Terrence Canisius College
Bonato, Anthony Ryerson University
Bulatov, Andrei Simon Fraser University
Bulín, Jakub Charles University in Prague
Cameron, Kathleen Wilfrid Laurier University
Capes, Tim University of Toronto
Carvalho, Catarina University of Hertfordshire
Chaplick, Steven University of Toronto
Churchley, Ross University of Victoria
Corneil, Derek University of Toronto
Cranston, Daniel Virginia Commonwealth University
Dalmau, Victor Universitat Pompeu Fabra
Dutle, Aaron University of South Carolina
Dvorak, Zdenek Charles University
Edmonds, Jack  
Failing, David Iowa State University
Fan, Xiaoxia University of Waterloo
Feder, Tomás Stanford University
Foniok, Jan Queen's University
Ghasemloo, Kaveh University of Toronto
Grenet, Bruno École Normale Supérieure de Lyon
Groshaus, Marina Universidad de Buenos Aires
Guenda, Kenza University of Algiers
Hahn, Gena Université de Montréal
Hart, Bradd McMaster University
Hatami, Hamed McGill University
Hell, Pavol Simon Fraser University
Hell, Pavol Simon Fraser University
Horowitz, Jonah McMaster University
Huang, Jing University of Victoria
Huber, Anna Durham University
Hubicka, Jan Institute of theoretical computer science (ITI)
Ieraci, Luciano University of Toronto
Jonsson, Jakob KTH
Kang, Ross Durham University
Kazda, Alexandr Charles University in Prague
Koiran, Pascal ENS Lyon
Král, Daniel Charles University
Larose, Benoit Champlain Regional College
Lemaître, Adrien Université de Montréal
Liang, Yu-chang National Sun Yat-Sen University
Lidický, Bernard Charles University
Lin, Cheyu National Sun Yat-sen University
Loten, Cynthia University of the Fraser Valley
MacGillivray, Gary University of Victoria
Maltais, Elizabeth University of Ottawa
Manuch, Jan University of British Columbia
Medabalimi, Venkatesh University of Toronto
Mehrabian, Abbas University of Waterloo
Mnich, Matthias International Computer Science Institute
Mohammadi Nevisi, Mayssam Simon Fraser University
Montejano, Amanda UNAM (National Autonoous University of Mexico)
Moura, Lucia University of Ottawa
Muise, Christian University of Toronto
Naserasr, Reza Université Bordeaux 1
Nesetril, Jaroslav Charles University
Newman, Mike University of Ottawa
Ossona de Mendez, Patrice CAMS - CNRS UMR 8557
Portier, Natacha ENS Lyon
Protti, Fábio Fluminense Federal University
Rafiey, Arash IDSIA
Raspaud, André University Bordeaux I
Roberson, David University of Waterloo
Siggers, Mark Kyungpook National University
Smedberg, Matthew Vanderbilt University
Strozecki, Yan Université Paris 7
Tardif, Claude Royal Military College of Canada
Tesar, Marek Charles University
Valeriote, Matthew McMaster University
Vardi, Moshe Y. Rice University
Willard, Ross University of Waterloo
Winkler, Peter Dartmouth College
Yeh, Hong-Gwa National Central University
Zhu, Xuding National Sun Yat-sen University

 

Program Researchers

Program Participants requesting support or office space:
All scientific events are open to the mathematical sciences community. Visitors who are interested in office space or funding are requested to apply by filling out the application form.
Fields scientific programs are devoted to research in the mathematical sciences, and enhanced graduate and post-doctoral training opportunities. Part of the mandate of the Institute is to broaden and enlarge the community, and to encourage the participation of women and members of visible minority groups in our scientific programs.


For additional information contact thematic(PUT_AT_SIGN_HERE)fields.utoronto.ca

Back to Top