DIMACS/DIMATIA/Renyi Tripartite Partnership
This conference is being held in conjunction with the Conference on Probabilistic Combinatorics & Algorithms: a Conference in Honor of Joel Spencer's 60th Birthday, April 24 - 25, 2006, and conference participants are urged to consider attending both meetings. More information about the Conference on Probabilistic Combinatorics & Algorithms: a Conference in Honor of Joel Spencer's 60th Birthday is available at http://dimacs.rutgers.edu/Workshops/Spencer/.
Wednesday, April 26, 2006
Session: Algebraic and Geometric Methods in Combinatorics
8:30 - 9:00 Breakfast and Registration
9:00 - 9:10 Welcome and Introduction
Fred Roberts, DIMACS Director
9:10 - 9:45 Homomorphisms: Logic vrs. Combinatorics
Jaroslav Nesetril, Charles University
9:50 - 10:25 Controlling the Spread of Viruses on Power-Law Networks
Jennifer Chayes, Microsoft
10:30 - 11:00 break and discussion
11:00 - 12:00 Subsums of a finite sum and extreme sets of vertices of the hypercube
Dezso Miklos, Alfréd Rényi Institute
Tracing a single user
Vera Asodi, Tel-Aviv University
On the chromatic number of a random 5-regular graph
Graeme Kemkes, University of Waterloo
12:00 - 1:30 lunch and discussion
1:30 - 2:10 Excluded submatrices in 0-1 matrices
Balazs Keszegh, Alfréd Rényi Institute
Distinguishing Chromatic Number of Cartesian Products of Graphs
Hemanshu Kaul, University of Illinois at Urbana-Champaign
2:15 - 2:50 Faster solving, counting, and sampling
Greg Sorkin, IBM Research
2:55 - 3:30 break and discussion
3:30 - 4:05 Random polytopes
Van Vu, Rutgers University
4:10 - 4:45 Testing for a Theta
Paul Seymour, Princeton University
4:50 - 6:00 working group discussion
6:00 - 7:00 wine and cheese
Thursday, April 27, 2006
Session: Generalizations of Graph Colorings
8:30 - 9:00 Breakfast and registration
9:00 - 9:35 Tournaments
Noga Alon, Tel Aviv University
9:40 - 10:15 Real Number Labellings
Jerry Griggs, University of South Carolina
10:20 - 11:00 break and discussion
11:00 - 12:00 Van der Waerden Diversions
Rados Radoicic, Rutgers University
Circular chromatic number of hexagonal chains with orientations
Drago Bokal, Simon Fraser University
Between 2- and 3-colorability
Vadim Lozin, Rutgers University
12:00 - 1:30 lunch and discussion
1:30 - 2:10 Group-Valued Edge Colourings of Cubic Graphs
Daniel Kral, Georgia Institute of Technology
Parity Edge-Coloring of Graphs
Doug West, University of Illinois - Urbana
2:15 - 2:50 Distance constrained graph labelings
Jan Kratochvil, DIMATIA
2:55 - 3:30 break and discussion
3:30 - 4:05 Inequalities for the First-Fit chromatic number
Zoltan Furedi, Renyi Institute
4:10 - 4:45 Graph-theoretical Problems Arising from Defending
Against Bioterrorism and Controlling the Spread of Fires
Fred Roberts, DIMACS
4:50 - 6:00 working group discussion
Friday, April 28, 2006
Session: Extremal Combinatorics
8:30 - 9:00 Breakfast and Registration
9:00 - 9:35 Extremal Graph Theory on Intersection Graphs
Janos Pach, Courant Institute
9:40 - 10:15 Ugly proofs and Book proofs
Joel Spencer, Courant Institute
10:20 - 11:00 break and discussion
11:00 - 12:00 Foundations of Quasirandomness
Joshua Cooper, Institute of Theoretical Computer Science
Coverings and packings for radius 1 adaptive block coding
Robert B. Ellis, Illinois Institute of Technology
Pattern Avoidance in Ordered Hypergraphs
Adam Marcus, Georgia Tech
12:00 - 1:30 lunch and discussion
1:30 - 2:35 Graph classes characterized both by forbidden subgraphs and degree sequences
Stephen Hartke, University of Illinois
Choosability of Graphs with Infinite Sets of Forbidden Differences
Pavel Nejedly, Georgia Tech
Profile vectors in the poset of subspaces
Daniel Gerbner
2:35 - 3:30 break and discussion
3:00 - 3:35 Constructions via Hamiltonian Theorems
Gyula Katona, Alfréd Rényi Institute
3:40 - 4:15 Lattice point counting and Markov chains
Jozsef Beck, Rutgers University
4:20 - 4:55 Can you reduce a girth 6 planar graph to a forest by
removing edges at most two incident to any vertex?
Dan Kleitman, MIT
5:00 - 6:00 working group discussion
6:00 - 7:30 banquet
Saturday, April 29, 2006
Session: Extremal and Algebraic and Geometric Combinatorics
8:30 - 9:00 Breakfast and registration
9:00 - 9:35 Slow Mixing of Local Dynamics Via Topological Obstructions
Dana Randall, Georgia Institute of Technolgy
9:40 - 10:15 Proof of the Random Energy Conjecture for Number Partitioning
and Spin Glasses
Christian Borgs, Microsoft
10:20 - 11:00 break and discussion
11:00 - 12:00 The linear discrepancy of product of chains
Jeong Ok Choi, University of Illinois at Urbana-Champaign
General Geographical Threshold Graphs
Milan Bradonjic, University of California
The Discrepancy of Quasi-arithmetic Progressions:
Power of N or Power of log N?
Sujith Vijay, Rutgers University
12:00 - 1:30 lunch and discussion
1:30 - 2:35 Edge-choosability of planar graphs with no adjacent triangles
Dan Cranston, University of Illinois
Biplanar crossing number
Laszlo Szekely, University of South Carolina
Weighted Cross-Intersecting Families
Akos Kisvolcsey
2:35 - 3:00 break and discussion
3:00 - 3:35 Convergent graph sequences and generalized quasi random graphs
Vera Sos, Alfréd Rényi Institute
3:40 - 4:15 Local chromatic number of quadrangulation of surfaces
Gabor Tardos, Simon Fraser University
4:20 - 5:30 meeting of working groups
Previous: Participation
Workshop Index
DIMACS Homepage