CanaDAM 2011
University of Victoria, May 31 - June 3, 2011

Random Structures

ROSS J. KANG, Durham University
Subset Glauber dynamics mixes rapidly on graphs of bounded tree-width.  [PDF]

Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs of bounded tree-width. This extends known rapid mixing results for the Tutte, adjacency-rank and interlace polynomials. This is joint work with Magnus Bordewich.

MITCHEL T. KELLER, London School of Economics and Political Science
Linear Extension Diameter and Reversal Ratio  [PDF]

The linear extension diameter of a poset is the maximum distance between two of its linear extensions. (Distance is the number of incomparable pairs appearing in opposite orders.) The reversal ratio $RR(\mathbf{P})$ is the ratio of the linear extension diameter to the number of incomparable pairs. We use probabilistic techniques to define posets $\mathbf{P}_k$ for which $RR(\mathbf{P}_k)\leq~C\log~k$. We also examine bounding the reversal ratio in terms of dimension and width. Joint work with Graham Brightwell.

STEPHEN J. YOUNG, University of California, San Diego
Braess's Paradox in Sparse Random Graphs  [PDF]

Braess’s paradox is the counter-intuitive observation that closing roads can improve traffic flow. With the explosion of distributed (selfish) routing situations this paradox has become an important concern in a broad range of network design situations. However, the previous theoretical work on Braess’s paradox has focused on dense or “designer” graphs, which are unrealistic in practical situations. We show that Braess’s paradox occurs in $G(n,p)$ when $np \geq c\log(n).$ Joint work with Fan Chung.

Handling of online submissions has been provided by the CMS.

Event Sponsors

Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Victoria