DIMACS/DIMATIA/Renyi Combinatorial Challenges Meeting

April 26 - 29, 2006
Location: DIMACS Center, CoRE Building, Rutgers University

Organizers:
Brenda Latka, Program Chair, DIMACS, latka@dimacs.rutgers.edu
Gyula Katona, Alfréd Rényi Institute, ohkatona@renyi.hu
Jaroslav Nesetril, Charles University, nesetril at kam.mff.cuni.cz
Fred Roberts, DIMACS, froberts@dimacs.rutgers.edu

The Rényi Institute Home Page

DIMATIA Home Page

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/.


Workshop Program:


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
Contacting the Center
Document last modified on April 26, 2006.