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