DIMACS/DIMATIA Workshop on Graphs, Morphisms and Statistical Physics

March 19-21, 2001
DIMACS Center, Rutgers University, Piscataway, New Jersey

Organizers:

Jarik Nesetril, DIMATIA, nesetril@kam-enterprise.ms.mff.cuni.cz

Peter Winkler, Bell Labs, pw@lucent.com

Preliminary Program:

Monday, March 19, 2001

8:30-9:00	Breakfast and Registration

9:00-9:15	Opening Remarks:
		Fred Roberts, Jarik Nesetril, Peter Winkler

9:15-10:05	Kickoff Address:
		Large Subgraphs of Random Graphs
		Bela Bollobas		

10:05-10:45	Morning break

10:45-11:25	Homomorphisms: Structure, Extremal and Random
		Jaroslav Nesetril

11:35-12:15	A Phase Transition in the Optimum Partitioning
		Problem
		Jennifer Chayes

12:00-2:00	Lunch and Discussion

2:00-2:40	Counting H-Morphisms
		Josep Diaz

2:50-3:30	List Homomorphisms
		Pavol Hell

3:30-4:00	Afternoon break

4:00-4:40	Information Flow on Trees
		Elchanan Mossel

4:50-5:30	The Pfaffian Approach to the Ising Problem and the
		Dimer Problem in 2-Dimensional and 3-Dimensional
		Lattices
		Martin Loebl

Tuesday, March 20, 2001

8:30-9:00	Breakfast and Registration

9:00-9:40	Potts Antiferromagnet: The Case of Entropic
		Contours?
                Roman Kotecky

9:50-10:20	Threshold Phenomena for Interacting or Constraint
		Particles
		Irene Hueter

10:30-10:45	Morning break

10:45-11:25	Slow Mixing for Random H-Colorings on the
		Hypercubic Lattice
		Christian Borgs

11:35-12:15	The Chromatic Number of the Product
                of Two Graphs is at Least Half the
                Minimum of the Fractional Chromatic
                Numbers of the Factors
		Claude Tardiff

12:15-2:00	Lunch and Discussion

2:00-2:40	Rapid Mixing for Glauber Dynamics Without
		Uniqueness of Gibbs States
		Yuval Peres

2:40-3:30	Compatible Sequences and a Slow Winkler
		Percolation
		Peter Gacs

3:30-4:00	Afternoon break

4:00-4:40	Computational Complexity and Phase Transition?
		Gabriel Istrate

4:50-5:30	Efficient Local Search Near Phase Transitions
		Stefan Boettcher

Wednesday, March 21, 2001

8:30-9:00	Breakfast and Registration

9:00-9:40	Proper Colorings of Regular Trees
                Graham Brightwell

9:50-10:30	Critical Resonance for Nonintersecting
		Lattice Paths
                David Wilson

10:30-10:45	Morning break

10:45-11:25	Cliques and Independent Sets in Graphs
                and Hypergraphs and Applications
                Hanno Lefmann, Technische Universitet Chemnitz

11:35-12:15	Large Independent Sets and 3-Colourings of
		4-Regular Hamiltonian Graphs
                Gert Sabidussi

12:15-2:00	Lunch and Discussion

2:00-2:40	Denial of Service Attacks and the Internet 
		Power Law
		Kihong Park

2:50-3:30	A Sharp Threshold for Network Reliability
		Benny Sudakov

3:30-4:00	Afternoon break

4:00-4:40	On the Solution of a Spin Model
		Jacob Katriel

4:50-5:30	Graph Homomorphisms and Long Range Order
		Peter Winkler

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage