A One-Day Meeting in Combinatorics will be held in the
Mathematical Institute, University of Oxford on Wednesday 30 May 2012.
Schedule and abstracts can be found below.
10.30 am
Coffee
11.00 am
Jarik Nesetril (Prague)
Subgraph statistics for sparse graphs
11.55 am
Benny Sudakov (UCLA)
Induced matchings, arithmetic progressions and communication
12.50 pm
Lunch
2.15 pm
Louigi Addario-Berry (Montreal)
The spectrum of random lifts
3.10 pm
Jacob Fox (MIT)
Two extensions of Ramsey's theorem
4.05 pm
Tea
4.30 pm
Béla Bollobás (Cambridge/Memphis)
Bootstrap percolation in all dimensions
Anyone interested is welcome to attend, and no registration is required. Some funds may be
available to contribute to the expenses of research students who wish to attend
the meeting. Further details can be obtained from Alex Scott (scott at maths.ox.ac.uk). Support for this event by the London Mathematical
Society and the British Combinatorial Committee is gratefully acknowledged.
Louigi Addario-Berry (Montreal),
The spectrum of random lifts
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 uniformly
random perfect matching between adjacent fibres. We show that with high
probability, all eigenvalues of the adjacency matrix A 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)|). Our key tools are (1) a convexity argument which yields
exponential bounds number of "test" vectors we need to consider when
bounding the largest new eigenvalue, and (2) a reduction which, given a
vector v with <Av,v> large, produces another, sparser vector v' satisfying
<Av,v>=O(<Av',v'>) and such that v' in a sense encodes the reasons why
<Av,v> is large.
Joint work with Simon Griffiths.
Béla Bollobás (Cambridge/Memphis),
Bootstrap percolation in all dimensions
Bootstrap percolation on a graph G with infection parameter r
is a deterministic process defined as follows. We start with a set
A_0 of initially infected sites (vertices). At each time step
t=1, 2,... the set A_{t-1} of sites infected at time t-1 gets
updated as follows: sites infected at time t-1 remain infected, and
every uninfected site with at least r infected neighbours (neighbours in
the set A_{t-1}) also gets infected.
Thus A_0⊂A_1⊂...⊂A_t⊂V(G).
We say that A_0 percolates
(with parameter r) if eventually all sites get infected, i.e.
A_t=V(G) for some t. This process, which is a simple cellular automaton,
was introduced by Chalupa, Leath and Reich in 1979.
Over the years, much attention has been paid to bootstrap percolation
on lattices and grids in which the initial configuration is selected at
random, with a certain probability p of selecting each site,
independently of each other. There are some deep results about the critical
probability, the probability p_0 such that for p<p_0
percolation is unlikely, and for p>p_0 it is likely.
In the talk I shall review some of the fundamental results, due to
Aizenman, Lebowitz, Schonman, Holroyd and others, and will present a number
of results I have obtained recently with Balogh, Morris,
Duminil-Copin, Riordan, Holmgren, Smith and Uzzell
Jacob Fox (MIT),
Two extensions of Ramsey's theorem
Ramsey's theorem, in the version of Erdos and Szekeres, states
that every 2-coloring of the edges of the complete graph on 1,...,n
contains a monochromatic clique of order 0.5log_2 n. In this talk, we
consider two well-studied extensions of Ramsey's theorem.
We show that there is a constant c>0 such that every 2-coloring of the
edges of the complete graph on 2,...,n contains a monochromatic clique such
that the sum of 1/log i over all vertices i of this monochromatic clique is
at least clogloglog n, which is tight apart from the constant factor c.
This extends an earlier work of Rodl and answers a question of Erdos from
1981.
Motivated by a problem in model theory, Vaananen asked whether for every k
there is an n such that every 2-coloring of the edges of the complete graph
on 1,...,n contains a monochromatic clique a_1 < ... < a_k such that the
differences a_{i+1}-a_i satisfy a prescribed order relation. Alon and
independently Erdos, Hajnal, and Pach answered this question affirmatively.
Alon further conjectured that the growth rate should be exponential in k.
We make progress on this conjecture, obtaining an upper bound on n which
is exponential in a power of k. This improves on a result of Shelah, who
showed that n is at most double-exponential in k.
The proofs of the above results use the powerful probabilistic technique
known as dependent random choice, with some additional combinatorial ideas.
Joint work with David Conlon and Benny Sudakov.
Jarik Nesetril (Prague),
Subgraph statistics for sparse graphs
We determine the asymptotics logorithmic density of subgraphs of large
sparse graphs (from a nowhere dense class). This also leads to a unified
approach to graph limits for both sparse and dense classes. Joint work with
Patrice Ossona de Mendez, Paris.
Benny Sudakov (UCLA),
Induced matchings, arithmetic progressions and communication
Extremal Combinatorics is one of the central branches of discrete
mathematics which deals with the problem of estimating the maximum
possible size of a combinatorial structure which satisfies certain
restrictions. Often, such problems have also applications to other
areas including Theoretical Computer Science, Additive Number Theory
and Information Theory. In this talk we will illustrate this fact by
several closely related examples focusing on a recent work with Alon
and Moitra.