Wednesday, June 14

Probabilistic Aspects of Combinatorics and Graph Theory

10:30 am - 12:30 pm
Room: Section B

Probabilistic methods continue to impact discrete mathematics in ever-impressive ways. Central topics include threshold functions, rapidly mixing Markov chains, and almost-sure convergence. Applications have included, e.g., good randomized algorithms for approximating the permanent of a 0-1 matrix, or in graph-theoretic terms, the number of perfect matchings in a bipartite graph. This minisymposium will provide a timely snapshot of the central topics listed above, as they relate to families of multisets, graph pebbling, graph coloring, Ramsey theory, and the infinite random graph. It is hoped that the cross-section of discrete mathematics falling within this scope will be of broad appeal to the conference attendees.

Organizers: P. Mark Kayll
University of Montana, USA
Anant P. Godbole
Michigan Technological University, USA
10:30 - 10:55 Threshold Functions for Graph Pebbling
P. Mark Kayll, Organizer
11:00 - 11:25 Thresholds for Families of Multisets, with Applications to Graph Pebbling
Glenn H. Hurlbert, Arizona State University, USA
11:30 - 11:55 On the Mixing Rate of the Glauber Dynamics on Graph Colorings
Mike Molloy, University of Toronto, Canada
12:00 - 12:25 Almost Sure Results for Discrete Random Structures
Anant P. Godbole, Organizer

©2000 Society for Industrial and Applied Mathematics
Designed by Donaghy's Web Consulting
Created 3/16/00; Updated 3/16/00