DIMACS Workshop on Probabilistic Methods in Discrete Mathematics

October 14-18, 1996
DIMACS Center, CoRE Building, Rutgers University

Organizers:

Noga Alon, Tel Aviv University, noga@math.tau.ac.il

Joel Spencer, NYU, spencer@cs.nyu.edu

MONDAY, October 14, 1996

 9:15-9:30	Welcome to DIMACS
		Fred Roberts, DIMACS Director

 9:30-10:15	Bela Bollobas
		Memphis University and University of Cambridge
		Colourings Generated by Monotone Properties

10:15-10:45	Coffee

10:45-11:30	Michel Talagrand 
		CNRS and Ohio State University
		Concentration of measure and combinatorics: 
		what is the final word?

12:00- 2:00	Lunch

 2:00- 2:25	Joel Spencer
		Courant Institute
		An asymptotic isoperimetric inequality

 2:30- 2:55	Boris Pittel
		Ohio State University
		Maximum matchings in sparse random graphs: 
		Karp--Sipser re-visited. 

 3:00- 3:30	Coffee

 3:30- 4:15	Tomasz Luczak
		Emory University and Adam Mickiewicz University
		Extremal properties of random sets

 6:00 -		Reception

TUESDAY, October 15 , 1996

 9:30-10:15	Amir Dembo
		Stanford University and the Technion
		Information inequalities and concentration of measure

10:15-10:45	Coffee

10:45-11:10	Bruce Reed
		CNRS
		$\omega,\Delta,\chi$.

11:15-11:45	Mike Molloy
		University of Toronto
		A Bound on the Total Chromatic Number

12:00- 2:00	Lunch

 2:00- 2:25	Alexander Kostochka
		Russian Academy of Sciences
		Oriented colorings of graphs

 2:30- 2:55	Donovan Hare
		Okanagan University College
		Arithmetic Progressions in Sequences With Bounded Gaps

 3:00- 3:30	Coffee

 3:30- 	 	Discussion


WEDNESDAY, October 16, 1996

 9:30-10:15	Vojtech Rodl
		Emory University
		Partition properties of Random Structures

10:15-10:45	Coffee

10:45-11:30	Robin Pemantle 
		University of Wisconsis-Madison
		Exponentially separated paths and application to oriented 
		percolation


THURSDAY, October 17, 1996

 9:30-10:15	Zoltan Furedi
		University of Illinois
		The expected size of a random sphere-of-influence graph

10:15-10:45	Coffee

10:45-11:30	Jeong Han Kim
		AT & T 
		Random Coverings of the n-Dimensional Cube

12:00-14:00	Lunch

 2:00- 2:25	Aravind Srinivasan
		National University of Singapore
		Improving the discrepancy bound for sparse matrices: 
		better approximations for sparse integer programs

 2:30- 2:55	Paul Spirakis
		Computer Technology Institute, Greece
		Genetic probabilistic methods for almost uniform generation 
		in parallel.

 3:00- 3:30	Coffee

 3:30- 3:55	Sotiris Nikoletseas 
		Computer Technology Institute, Greece
		Stochastic Graphs Have Short Memory: Fully Dynamic 
		Connectivity in Poly-Log Expected Time

 4:00- 5:00	Problem session


FRIDAY, October 18, 1996

 9:30-9:55	Ljubomir Perkovic
		Carnegie Mellon University
		Edge Coloring in polynomial time (on average)

10:00-10:25	Nabil Kahale
		AT & T
		A semidefinite bound for mixing rates of Markov chains

10:25-10:45	Coffee

10:45-11:30	Colin McDiarmid
		Oxford University
		Finding a minimum spanning tree in a network with 
		random weights

12:00- 2:00	Lunch

 2:00- 2:25	Igor Pak
		Harvard University
		Random walks on groups: strong stationary times approach.

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage