Mathematics Department - Discrete Math - Fall 2016

# Discrete Math - Fall 2016

### Organizer(s)

Jeffry Kahn, Jacob D Baron, Patrick Devlin

## Monday, September 26th

### "Capsets, sunflower-free sets in {0,1}^n, and the slice rank method"

Time: 2:00 PM
Location: Hill 705
Abstract: A collection of $k$ sets is said to form a $k$-sunflower, or $Delta$-system, if the intersection of any two sets from the collection is the same, and we call a family of sets $mathcal{F}$ sunflower-free if it contains no sunflowers. In this talk we will look at the recent breakthrough of Ellenberg and Gijswijt and Croot, Lev and Pach, which used polynomial method to obtain exponential upper bounds for the Capset problem, that is upper bounds for the size of the largest set in $mathbb{F}_3^n$ which contains no three term arithmetic progressions. In particular we will look at Tao's reformulation of this approach using the so called "Slice Rank Method," and apply it directly to the ErdH{o}s-Szemer'{e}di sunflower problem, proving an exponential upper bound for the size of any sunflower-free family of subsets of ${1,2,…,n}$.

## Monday, September 19th

### " The frog model on trees"

Time: 2:00 PM
Location: Hill 705
Abstract: Imagine that every vertex of a graph contains a sleeping frog. At time 0, the frog at one vertex wakes up and begins a simple random walk. When it moves to a new vertex, the sleeping frog there wakes up and begins its own simple random walk, which in turn wakes up any sleeping frogs it lands on, and so on. This process is called the frog model, and many basic questions about it remain open. I'll talk about the frog model on infinite trees, where the process exhibits some interesting phase transitions. In particular, I'll (mostly) answer a question posed by Serguei Popov in 2003 by showing that on a binary tree, all frogs wake up with probability one, while on a 5-ary or higher tree, some frogs remain asleep with probability one. This work is joint with Christopher Hoffman and Matthew Junge.

## Monday, September 12th

### "Induced subgraphs of graphs with large chromatic number"

Time: 2:00 PM
Location: Hill 705
Abstract: What can we say about the induced subgraphs of a graph G with very large chromatic number? If G has no large cliques, then what else can we guarantee? We will discuss recent work on this topic, and present some new results. (Joint work with Maria Chudnovsky and Paul Seymour.)

This page was last updated on February 09, 2016 at 10:04 am and is maintained by webmaster@math.rutgers.edu.