Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2021: Extremal combinatorics

G
Topic
First Poster
Last Poster
welcome to crowdmath 2021
JGeneson   4
N Jan 6, 2022 by PiGuy3141592
This year, our main topic is extremal combinatorics, with a focus on problems about sequences and 0-1 matrices. These problems have applications to many areas including:

-robot navigation (e.g. an algorithm for finding a shortest path between two given points in a grid with obstacles)
-discrete geometry (e.g. an upper bound on the maximum number of unit distances in a convex n-gon), and
-permutation pattern avoidance (the solution to the Stanley-Wilf conjecture).

Researchers have been investigating these kinds of problems for over fifty years. The topic requires no background knowledge besides basic combinatorics. You can learn more about relevant definitions and background reading on the Resources page. That page has a list of papers and exercises with each paper. All of the exercises are solved problems, they are there to help understand the topic.

The Problems page has a list of open problems. These problems are unsolved, most are from publications, and I made some of them. I’ll post some more open problems later in the year, and typically crowdmath participants also suggest open problems. Here are some examples of Crowdmath research papers from past years:

https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p5
https://arxiv.org/search/math?searchtype=author&query=CrowdMath%2C+P+A
https://arxiv.org/abs/2008.13302
https://arxiv.org/abs/1710.11352
4 replies
JGeneson
Jan 9, 2021
PiGuy3141592
Jan 6, 2022
The $u$-free process on sequences
JGeneson   27
N Dec 20, 2021 by PiGuy3141592
Consider the following process:

Fix a sequence $u$ with $r$ distinct letters. Let $S_0 = [ ]$ (the empty sequence).

1. For $i > 0$, we uniformly at random select a letter $\ell$ from $a_1, \dots, a_n$ (each with probability $1/n$).

2. Let $T$ be the sequence obtained from $S_{i-1}$ by addending the letter $\ell$.

3. If $T$ does not contain $u$ and the last $r$ letters of $T$ are all distinct, let $S_{i} = T$ and increment $i$ and go back to 1. Otherwise, let $S_i = S_{i-1}$ and increment $i$ and go back to 1. (Note: the definition of containment here is the same as on the problem/resource pages.)

Eventually, this process produces a sequence for which it is impossible to add any more letters to the end without forcing containment of $u$ or a repeated letter among the last $r$, so $S_i$ is constant after a certain point.

Define $Fr(u, n)$ to be the expected length of the sequence that we obtain using the above process.

The problem is to find $Fr(u,n)$ for all sequences $u$.

Some (possibly?) easier $u$ to start with:
$u = aa$, $u = aaa$, $u = aaaa$, $\dots$

$u = a b$, $u = a b c$, $u = a b c d$, $\dots$

$u = a b a$, $u = a b a b$, $u = a b a b a$, $\dots$

and any other nice sequences $u$ that you can think of.

Is there an algorithm to calculate $Fr(u,n)$ in general?

This problem is an analogue of the $H$-free process on graphs: see e.g. https://arxiv.org/abs/0908.0429
27 replies
JGeneson
Mar 5, 2021
PiGuy3141592
Dec 20, 2021
No more topics!
a