Campuses:

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
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.
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.
Subscribe to RSS - Extremal Combinatorics