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

MIT PRIMES/Art of Problem Solving

CROWDMATH 2019: Graph Coloring

G
Topic
First Poster
Last Poster
formation width algorithm
JGeneson   2
N Dec 9, 2019 by JGeneson
Definitions
An $(r,s)$-formation is a concatenation of $s$ permutations of $r$ letters, e.g. $a b c c b a a b c a c b$ is a $(3, 4)$-formation.

For every sequence $u$ define $fw(u)$, the formation width of $u$, to be the minimum $s$ for which there exists $r$ such that there is a subsequence isomorphic to $u$ in every $(r,s)$-formation.

Problem:
In the first $2$ papers on $fw$ (https://arxiv.org/abs/1308.3810 and https://arxiv.org/abs/1502.04095), we found an algorithm to calculate $fw(u)$ for any sequence $u$.

The algorithm in the second paper is faster than the first, but both algorithms are very slow. Find a faster algorithm to compute $fw(u)$.

Notes
Both papers have Python formation width algorithms at the end.

Suppose that $I_{c} = 1 2 \dots c$ and $D_{c} = c (c-1) \dots 1$. A formation with all permutations equal to $I_{c}$ or $D_{c}$ for some $c$ is called a binary formation.

The key fact used for both algorithms is Corollary 12 in the first paper:

If $u$ has $r$ distinct letters, then every binary $(r, s)$-formation contains $u$ if and only if $s \geq fw(u)$.

Algorithm for calculating $fw(u)$:
Let $r$ be the number of distinct letters in $u$. Starting with $s = 1$, check if every binary $(r, s)$-formation contains $u$. If so, output $s$ and halt. Otherwise increment $s$ and repeat.
2 replies
JGeneson
Dec 29, 2018
JGeneson
Dec 9, 2019
formation width algorithm for 3-letter sequences
JGeneson   2
N Dec 9, 2019 by JGeneson
For definition of $fw(u)$, see the Problems page.

One of the problems for $fw(u)$ is to find an algorithm to compute $fw(u)$ that is polynomial-time in the length of $u$. There is already a polynomial-time algorithm for $fw(u)$ when $u$ has two distinct letters. Is there a polynomial-time algorithm for $fw(u)$ for sequences $u$ with three distinct letters?
2 replies
JGeneson
Nov 19, 2019
JGeneson
Dec 9, 2019
probabilistic algorithms for computing formation width
JGeneson   2
N Nov 26, 2019 by solvingking
For definition of $fw(u)$, see the Problems page.

Any ideas for probabilistic algorithms for computing $fw(u)$?

For example, how accurate a value can we get for $fw(u)$ by checking only a random subset of the binary formations with $s$ permutations instead of the full set of binary formations with $s$ permutations in order to to compute $fw(u)$?
2 replies
JGeneson
Nov 19, 2019
solvingking
Nov 26, 2019
No more topics!
a