One-Day Meeting in Combinatorics
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.

Schedule

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, andnoisesensitivity


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).


Abstracts

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, andnoisesensitivity

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 JeffKahn, JeanBourgain,andElchananMossel, and ona work in progress withGuyKindler.

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

In this talk I will discusssome 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.)