Mathematical Institute

University of Oxford

Thursday 5 June 2014

A One-Day Meeting in Combinatorics will be held in the
Mathematical Institute, University of Oxford on **Thursday 5 June 2014**.
Schedule and abstracts can be found below.

10.30 am
Coffee

11.00 am
**Rob Morris (IMPA)
**

*
Counting sparse H-free graphs*

11.55 am
**
Angelika Steger (ETH Zurich)
**

*
Ramsey theorems for random structures*

12.50 pm
Lunch

2.15 pm
**
Jacob Fox (MIT)
**

*
Combinatorics of permutations
*

3.10 pm
**
Jeff Kahn (Rutgers)
**

*
A little more on "sparse random"*

4.05 pm
Tea

5.00 pm
**Gil Kalai (Jerusalem)
**

*
Influence, thresholds, and noise sensitivity*

The meeting is organized in partnership with the Clay Mathematics Institute, and is supported by the London Mathematical
Society and the British Combinatorial Committee.
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. For any inquiries, please contact Alex Scott (scott at maths.ox.ac.uk).

**Jacob Fox (MIT),
**
*
Combinatorics of permutations
*

For a permutation p, let S_n(p) be the number of permutations on
n letters avoiding p. A decade ago, Marcus and Tardos proved the celebrated
Stanley-Wilf conjecture that, for each permutation p, S_n(p)^{1/n} tends
to a finite limit L(p). Backed by numerical evidence, it has been
conjectured
by various researchers over the years that L(p) is on the order of k^2 for
every permutation p on k letters. We disprove this conjecture, showing that
L(p) is exponential in a power of k for almost all permutations p on k
letters. The proof uses ideas from extremal and probabilistic
combinatorics.

**Jeff Kahn (Rutgers),
**
*
A little more on "sparse random"
*

One of the more interesting of recent combinatorial directions
has been the effort to understand the extent to which various
classical facts remain true in a random setting.
The present talk will mainly discuss what we know about this question
when the ''classical fact'' is the Erdös-Ko-Rado Theorem.
(Joint with Arran Hamm.)

**Gil Kalai (Jerusalem),
***
Influence, thresholds, and noise sensitivity
*

We will consider the notions of influence and noise sensitivity of
Boolean functions and discuss the connection with harmonic analysis,
applications, and extensions.
The influence of a variable (or a set of variables) on a function is the
probability that changing the value of the variable(s) can change the value
of the function.
The noise-sensitivity of a function is the probability that for a random
assignment to the variables adding a random independent noise will change
the value of the function.
We will look at some old and new results and open problems, and mention
applications to sharp threshold phenomena, percolation, random graphs,
voting, and computation: classic and quantum.
The new results that I will present are based on joint works with
Jeff Kahn, Jean Bourgain, and Elchanan Mossel, and on a work in progress
with Guy Kindler.

**Rob Morris (IMPA),
**
*
Counting sparse H-free graphs
*

In this talk I will discuss some recent applications of the
hypergraph containers method to the following basic question: How many
H-free graphs are there with n vertices and m edges? As a general rule, we
obtain a reasonably good answer to the counting problem whenever we have a
sufficiently strong supersaturation theorem, but precise structural
descriptions of almost all such graphs require extra ideas and are lacking
except in a few special cases.

Joint work with Jozsi Balogh, Wojciech Samotij, Lutz Warnke and David
Saxton.

**Angelika Steger (ETH Zurich),
**
*
Ramsey theorems for random structures
*

In this talk we consider various versions of Ramsey-type questions in a
random graph setting: the classical Ramsey problem,
anti-Ramsey questions, Maker-Breaker games. It is easy to see that one
should expect the same threshold (namely, the m_2-density of the forbidden
graph F) for all these problems. However, despite having the same answer,
the proofs tend to be quite different – owing to the different nature of the
problem under consideration. The aim of this talk is to provide a general
framework for proving 0-statements and to then apply it to the three
problems mentioned above. (Joint work with my students Rajko Nenadov and
Nemanja Skoric.)