Jacob Fox, David Conlon, and Benny Sudakov: Vast Improvement of our Knowledge on Unavoidable Patterns in Words

I heard a lecture by Benny Sudakov on the remarkable paper  Tower-type bounds for unavoidable patterns in words, by David Conlon, Jacob Fox, and Benny Sudakov.  Here are the slides, and let me let the slides speak for themselves.

The problem

Zimin words

 

The problem and what was known: upper bounds

 

Earlier lower bounds

The new results

 

!!!

The proof is not difficult. It uses a probabilistic argument based on the Lovasz local lemma, and a step up argument.

A remaining open problem

Advertisements
This entry was posted in Combinatorics and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s