# Extremal Combinatorics

Monday, September 29, 2014 - 11:30am - 12:20pm

Jacob Fox (Massachusetts Institute of Technology)

For a permutation p, let S_n(p) be the number of permutations on n letters avoiding p. Stanley and Wilf conjectured that S_n(p)^{1/n} tends to a finite limit L(p) for each permutation p. Marcus and Tardos proved the Stanley-Wilf conjecture by a remarkably simple argument. 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.

Monday, September 29, 2014 - 2:00pm - 2:50pm

Melanie Wood (University of Wisconsin, Madison)

We determine the distribution of the sandpile group (a.k.a. Jacobian)

of the Erdős–Rényi random graph G(n,q) as n goes to infinity. Since

any particular abelian group appears with asymptotic probability 0 (as

we show), it is natural ask for the asymptotic distribution of Sylow

p-subgroups of sandpile groups. We prove the distributions of Sylow

p-subgroups converge to specific distributions conjectured by Clancy,

Leake, and Payne. These distributions are related to, but different

of the Erdős–Rényi random graph G(n,q) as n goes to infinity. Since

any particular abelian group appears with asymptotic probability 0 (as

we show), it is natural ask for the asymptotic distribution of Sylow

p-subgroups of sandpile groups. We prove the distributions of Sylow

p-subgroups converge to specific distributions conjectured by Clancy,

Leake, and Payne. These distributions are related to, but different

Thursday, September 11, 2014 - 2:00pm - 2:50pm

Alexander Razborov (University of Chicago)

Flag Algebras is a general method for proving results in asymptotic

extremal combinatorics that can be loosely described as systematic counting based on semi-definite programming.

The concrete results proven via this method can be (again, loosely) classified into two groups of unequal size. Brute-force

applications use counting only; the role of a human being reduced to finding a tractable problem and doing a bit of programming.

extremal combinatorics that can be loosely described as systematic counting based on semi-definite programming.

The concrete results proven via this method can be (again, loosely) classified into two groups of unequal size. Brute-force

applications use counting only; the role of a human being reduced to finding a tractable problem and doing a bit of programming.

Thursday, September 11, 2014 - 10:15am - 11:05am

Jacob Fox (Massachusetts Institute of Technology)

Famous Ramsey, Turan, and Szemeredi-type results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra.