Erdos-Ko-Rado problems in extremal combinatorics. Extremal combinatorics is an area of discrete math that asks how large (or small) a family of objects can be if we insist it has some prescribed property.  For instance, we might ask the following:
 
EKR problem: Suppose we pick positive integers n and k such that n > 2k.  The goal is to write down as many distinct k-element subsets of {1, 2, 3, ...,  n} with the constraint that any two subsets that we pick must have a non-empty intersection.  What's the most number of sets we could choose subject to this constraint?

​

This problem was first considered by Erdos, Ko, and Rado in the early twentieth century, and it's one of the earliest and most important results in extremal combinatorics.  For the above setting, one possible way to pick a lot of sets might be to first think of your favorite number and then just write down every k-element subset of {1, 2, ..., n} containing that number.  If your favorite number is x, then all of the sets we write down will contain x, so this family of sets will have the desired intersection property.  The collection of "all k-element subsets of {1, 2, ..., n} containing the element x" is called a star.  (Question to you: how many sets does a star have?)  So we know that one way to make a big intersecting family is just to make a star.  But the big question would be "is there some clever way to somehow manage to write down an even bigger family?"  For this problem, it turns out that you can't do any better than this and stars are as big as you can make!  (So this is a cool and satisfying result where the extremal examples end up being easy to understand)

​

Our goal in this Polymath Jr. project is to learn about classic results like the Erdos--Ko--Rado theorem, learn a handful of techniques useful in extremal combinatorics, and work on a few open research questions that translate the EKR problem to other combinatorial settings.  The proof techniques we will learn about come from fundamentally different areas of math (some using relatively simple techniques involving induction and counting, and some proofs using fancy stuff like linear algebra, probability, and even representation theory!).  Although this project does not have many firm prerequisites, all students should be willing to learn more things, and those who have already seen more math will be better poised to learn about more exotic techniques.  Here are two examples of problems we will consider (definitions and explanations will be given in the intro video for this project):

​

Polymath problem 1: Suppose we pick positive integers n and k such that  n > k > 1.  The goal is to write down as many distinct permutations of {1, 2, 3, ...,  n} with the constraint that any two permutations that we pick must have a common subsequence of length at least k.  What's the most number of permutations we could choose subject to this constraint?

​

Polymath problem 2: Suppose we start with a convex n-gon.  The goal is to come up with as many distinct triangulations of this shape with the constraint that any two triangulations must have share a chord.  What's the most number of triangulations we could choose subject to this constraint?