# SMS 2012 - Horaire

Nikhil Bansal -**Low discrepancy colorings and semidefinite programming**(7.5 heures). Résumé:

Discrepancy theory deals with the following type of question. Given a set-system, find a red-blue coloring of the elements such that each set is colored as evenly as possible. Perhaps surprisingly, this notion has a wide variety of applications both in computer science and mathematics, and several techniques (many of them non-constructive) have been developed to understand the discrepancy of various set-systems.

Recently, there have been several new developments in discrepancy based on connections to semidenite programming. This connection is useful is various ways. It gives efficient polynomial time algorithms for several problems for which only non-constructive results were previously known. It also leads to several new structural results, such as tightness of the so-called determinant lower bound, and bounds on the discrepancy of union of set systems. In these lectures, we will study these results in detail and visit various concepts such as correlated brownian motion, non-constructive entropy method, gaussian roundings, sdp duality, Cauchy-Binet formula and so on. Time permitting, we will also see some surprising applications of discrepancy.

Hamed Hatami -

**Influences and sharp thresholds**(3 heures). Résumé:

I will discuss the notion of the influence of a variable on a Boolean function. Then sketch the proof of the Friedgut's theorem which says that if $f:\{0,1\}^n \to \{0,1\}$ has small total influence then it essentially depends on few coordinates. This theorem does not hold when the uniform distribution on $\{0,1\}^n$ is replaced with the p-biased distribution for a small value of $p$. I will discuss the relevance of this case to the study of the threshold phenomenon, and then sketch the proof of a theorem of myself which characterizes the structure of Boolean functions with small total influences on general product probability spaces.

Penny Haxell -

**A topology-free topological method**(3 heures). Résumé:

Over the last dozen years or so, certain topological methods have been developed and used to prove a family of results related to the following general problem. Let G be a graph whose vertex set is partitioned into nonempty sets V_1,...,V_r. What conditions will guarantee that G contains an independent set \{v_1,...,v_r\} such that v_i\in V_i for each i? This family of results includes theorems on matchings in hypergraphs, list colouring, strong colouring, and Aharoni's proof of Ryser's longstanding conjecture on packing and covering in tripartite hypergraphs. The topological arguments used are based on the notion of topological connectivity of simplicial complexes. In these lectures we show how to develop this theory using only elementary combinatorial arguments. Thus we avoid any explicit use of topology, though topological intuition still plays a role.

James Lee -

**Cover times, Gaussian processes and majorizing measures**(3 heures). Résumé:

Lecture 1: Gaussian processes and majorizing measures

I will recall the relevant background and tools from Gaussian
processes, and then present a proof of Talagrand's majorizing measures
theorem. The proof, essentially a rephrasing of Talagrand's argument,
will be stated in a more combinatorial way that I think is easier to
follow.

Lecture 2: Cover times and the Gaussian free field

In joint work with Ding and Peres, we use the majorizing measures
theory to exhibit a close connection between the cover time of a graph
and the expected square of its Gaussian free field. I will discuss
this proof, along with the other main tool--the Dynkin isomorphism
theory for Markov processes--and show how the connection can be used
to answer some open questions on cover times.

Colin McDiarmid -

**Colouring random graphs**(3 heures). Résumé:

What is the typical behaviour of the chromatic number χ(G) of a graph G?
If R_n denotes some sort of random graph on n vertices, can we
determine a function f(n)
such that χ(R_n)/f(n) \to 1 in probability as n \to ∞? If
so, what is f(n)?
Can we bound the typical spread of the values χ(R_n)?
Is χ(R_n) usually close to Ω(R_n), the maximum size of a
complete subgraph?

We shall consider various models of random graph, but mainly we shall
focus on the classical Erdös-Rényi
or Bernouilli random graph G(n,p) (both in the dense case when p is a
constant and in the sparse case when
np is constant), and on random geometric graphs. Also, mostly we shall
focus on chromatic number, but
we shall briefly discuss related quantities, such as edge chromatic
number (chromatic index),
list chromatic number, total chromatic number, achromatic number,
improper chromatic number, and span.

In particular we shall meet recent results giving improved estimates
for χ(G(n,p)) in the dense case;
and see a `phase change' for colouring random geometric graphs.
What about a random graph sampled uniformly from all n vertex graphs
with at most 3 vertex-disjoint cycles?

Yuval Peres -

**Markov chain mixing times and related topics**(3 heures). Résumé:

(1) The cutoff phenomenon

(2) Evolving sets

(3) A cop and robber game and Kakeya sets

Alex Scott -

**To be announced**(7.5 heures). Résumé:

To appear.

Perla Sousi -

**Markov chain mixing times: bounds and asymptotics**(3 heures). Résumé:

Shuffling, Path coupling, Relating mixing times to hitting times of large sets.

Prasad Tetali -

**Geometric and Functional Analysis on Discrete Spaces**(3 heures). Résumé:

The lectures will begin with a review of some classical isoperimetric and functional inequalities in discrete spaces, with applications to concentration of measure and convergence to equilibrium of finite Markov chains. Recent results on generalizations of Cheeger-type inequalities and refinements of Brunn-Minkowski inequalities will then be covered, suggesting new directions for interesting research in geometric and functional analysis on graphs.

Eric Vigoda -

**Markov chains for graph colouring**(3 heures). Résumé:

This series of talks will be a survey of results related to Markov Chain Monte Carlo algorithms for generating a random k-coloring of a graph with maximum degree D. We'll begin with the coupling technique, and its refinement known as path coupling due to Bubley-Dyer. Our starting point will be Jerrum's rapid mixing result of the simplest Markov chain (aka Glauber dynamics) when k>2D. We'll then look at various improvements beginning with an improvement to k>(11/6)D using a more complicated chain that flips 2-color components. We'll see how to utilize properties of random colorings and use a multi-step coupling to get improved results assuming lower bounds on the girth and D. And we'll see improved results for planar graphs by using the spectral radius. Finally, we'll look at recent improvements in algorithms for approximately counting colorings based on random sampling.

Peter Winkler -

**Random Walks on Graphs---Old Directions and New**(7.5 heures). Résumé:

Random walk on a graph is a (by now) classical subject with lots
of beautiful theorems and scores of applications in mathematics and
computer science. Nonetheless, new and remarkable results keep
coming in. In this course, we'll review the basic tools and classical
theorems, then move in some exciting new directions, looking at recent
results and open problems. No background will be assumed beyond
probability and combinatorics at a middle undergraduate level.

Outline:

Lecture I: Random walk and electrical networks

Lecture II: Cover time for vertices and for edges

Lecture III: Collision and avoidance

Lecture IV: Pursuit and evasion

Lecture V: Branching random walk