CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Probabilistic Combinatorics
Org: Tom Bohman et Po-Shen Loh (Carnegie Mellon University)

The second eigenvalue of random lifts  [PDF]

Joint work with Simon Griffiths. For a fixed $d$-regular graph $H$, a random $n$-lift is obtained by replacing each vertex $v$ of $H$ by a ``fibre'' containing $n$ vertices, then placing a random matching between adjacent fibres. We show that whp, all eigenvalues of the lift that are not eigenvalues of H (``new'' eigenvalues), have order $O(\sqrt{d})$, and that any exceptionally large new eigenvalues are whp caused by a dense subgraph of size $O(|E(H)|)$.

KEVIN COSTELLO, Georgia Institute of Technology
On Randomizing Derandomized Greedy Algorithms  [PDF]

Some of the oldest, simplest, and easiest implemented approximation algorithms can be thought of as greedy derandomizations of some naive random algorithm. We consider two such algorithms (Johnson's algorithm for Maximum Satisfiability and the greedy algorithm for Maximum Cut) and ask whether considering the variables in a random order as opposed to an arbitrary one can improve the approximation guarantee of the algorithm.

Joint work with Asaf Shapira and Prasad Tetali.

Graph regularity and removal lemmas  [PDF]

Szemer\'edi's regularity lemma is one of the most powerful tools in graph theory. It was introduced by Szemer\'edi in his proof of the celebrated Erd\H{o}s-Tur\'an conjecture on long arithmetic progressions in dense subsets of the integers. Roughly speaking, it says that every large graph can be partitioned into a small number of parts such that the bipartite subgraph between almost all pairs of parts is random-like. One of the most important applications is the graph removal lemma, which roughly says that every graph with few copies of a fixed graph $H$ can be made $H$-free by removing few edges. It remains a significant problem to estimate the bounds in the regularity lemma and the removal lemma, and their variants. In this talk I discuss recent joint work with David Conlon which makes progress on this problem.

PO-SHEN LOH, Carnegie Mellon University
Rainbow Hamilton cycles in random graphs  [PDF]

We show that in the setting of randomly edge-colored Erd\H{o}s-R\'enyi random graphs, a rainbow-colored Hamilton cycle appears under conditions that are asymptotically best-possible. Specifically, when the edges of $G_{n,p}$ are randomly colored from a set of $(1+o(1))n$ colors, with $p=(1+o(1))\frac{\log n}{n}$, w.h.p. there exists a Hamilton cycle which has the further property that all edges are distinctly colored (rainbow). This improves earlier bounds of Cooper and Frieze.

Joint work with Alan Frieze.

BRUCE REED, McGill University
Bounding $\chi$ as a convex combination of $\omega$ and $\Delta +1$  [PDF]

Abstract: It has been conjectured that $\chi$ is at most $\lceil { \omega + \Delta +1 \over 2} \rceil$. It is known that there is a positive $\epsilon$ such that $\chi \le \lceil \epsilon \omega +(1-\epsilon)(\Delta+1) \rceil$. We provide a new proof of the latter result which yeilds an improved value of $\epsilon$. This is joint work with Andrew King.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria