DIMACS Workshop on Properties of Large Graphs: From Combinatorics to Statistical Physics and Back

October 16 - 20, 2006
DIMACS Center, CoRE Building, Rutgers University

Organizers:

László Lovász, Microsoft Research and Eötvös Loránd University, lovasz@cs.elte.hu

Benny Sudakov, Princeton University, bsudakov@math.princeton.edu

Workshop Program:

Monday, October 16, 2006

 8:45 -  9:20 Breakfast and Registration

 9:20 -  9:30 Welcoming Remarks 
              Fred Roberts, DIMACS Director 

 9:30 - 10:30 Tutorial
              Regularity Lemma(s)
              Michael Krivelevich, Tel Aviv University

10:30 - 11:00 Break
 
11:00 - 11:30 Convergent Sequences of Dense Graph, Part I
              Jennifer Chayes, Microsoft Research

11:40 - 12:10 Convergent Sequences of Dense Graph, Part II
              Christian Borgs, Microsoft Research

12:20 -  2:30 Lunch

 2:30 -  3:00 Gradient Networks: an Application to Protein Folding
              Zoltan Toroczkai, University of Notre Dame

 3:10 -  3:40 Quasi-random Graphs with Given Degree Sequences
              Fan Chung Graham, University of California, San Diego

 3:40 -  4:10 Break

 4:10 -  4:40 Spreading Dynamics on Small-world Networks with a 
              Power Law Degree Distribution
              Alexei Vazquez, Institute for Advanced Study

Tuesday, October 17, 2006

 8:45 -  9:30 Breakfast and Registration

 9:30 - 10:30 Tutorial
              Low-rank Approximations: Combinatorial and Numerical Applications
              Ravi Kannan, Yale 

10:30 - 11:00 Break

11:00 - 11:30 Core-dense Graphs and Hypergraphs
              Santosh Vempala, Georgia Tech

11:40 - 12:10 What is the Furthest Graph from a Hereditary Property?
              Uri Stav, Tel-Aviv University

12:20 -  2:30 Lunch

 2:30 -  3:30 Tutorial
              Quasirandomness
              Vera Sos, Alfréd Rényi Institute

 3:30 -  4:00 Break

 4:00 -  4:30 Multipartite Quasirandomness via Sieve Polynomials
              Joel Spencer, Courant Institute NYU

 6:00         Banquet

Wednesday, October 18, 2006

 8:45 -  9:30 Breakfast and Registration

 9:30 - 10:00 Notions of Correlation Decay in Random k-Satisfiability
              Andrea Montanari, Stanford University

10:10 - 10:40 Correlation Decay in Statistical Physics and Applications 
              to Counting Problems
              David Gamarnik, MIT

10:40 - 11:10 Break
 
11:10 - 11:40 Flag Algebras
              Alexander Razborov, IAS and Steklov Mathematical Institute

11:50 - 12:20 The Typical Structure of Graphs without Given Excluded Subgraphs
              Miklos Simonovits, Renyi Institute

12:20 -  2:30 Lunch

 2:30 -  3:00 The Rotor-router Model and Diaconis-Fulton Addition
              Yuval Peres, Microsoft Research and UC Berkeley

 3:10 -  3:40 Harmonic Deformation and Random Walk on Infinite Percolation Clusters
              Marek Biskup, UCLA

 3:40 -  4:10 Break

 4:10 -  4:40 Isomorphism and Embedding Problems for Infinite
              Limits of Preferential-Attachment Graphs
              Robert Kleinberg, Cornell

Thursday, October 19, 2006

 8:45 -  9:30 Breakfast and Registration

 9:30 - 10:00 Regular Partitions of Large Sparse Graphs with Some Applications I
              Jaroslav Nesetril, Charles University

10:10 - 10:40 Regular Partitions of Large Sparse Graphs with Some Applications II
              Patrice Ossona de Mendez

10:40 - 11:10 Break

11:10 - 11:40 Partition Regular Sets of Matrices
              Jozsef Solymosi, UBC

11:50 - 12:20 The Condition Number of Randomly Perturbed Matrices
              Van Vu, Rutgers University

12:20 -  2:30 Lunch

 2:30 -  3:00 Conditional Regularity and Testing Efficiently Bipartite Graph-Properties
              Ilan Newman, Haifa University

 3:10 -  3:40 A Combinatorial Characterization of the Testable Graph 
              Properties: It's All About Regularity
              Asaf Shapira, Microsoft Research

 3:40 -  4:10 Break

 4:10 -  4:40 From Regularity to Robustness and from Testing to Meta-testing
              Eldar Fischer, Technion

Friday, October 20, 2006

 8:45 -  9:30 Breakfast and Registration

 9:30 - 10:00 Graph Homomorphisms and Edge Coloring Models
              Balasz Szegedy, University of Toronto

10:10 - 10:40 Convergent Graph Sequences: Bounded Vertex Degrees
              Gabor Elek, Alfréd Rényi Institute

10:40 - 11:10 Break 

11:10 - 11:40 Evolving Graphs and Equation-free Computation
              Yannis Kevrekidis, Princeton

11:50 - 12:20 Hyperbolic Polynomials and Van der Waerden / 
              Schrijver-Valiant like Conjectures
              Leonid Gurvits, Los Alamos

12:20 -  2:30 Lunch

 2:30 -  3:00 Undecidable Statements and the Zero-one Law in Random Geometric Graphs
              Amit Agarwal, Princeton University

 3:10 -  3:40 Large Complex Networks: Deterministic Models
              Francesc Comellas Padro, Escola Politecnica Superior de Castelldefels

 3:40 -  4:10 Break

 4:10 -  4:40 Sampling Techniques in Low_Rank Matrix Approximation
              Amit Jayant Deshpande, MIT

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage