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
complexity of formation width decision problem
JGeneson   1
N Nov 25, 2019 by JGeneson
Is it possible to prove complexity results about formation width?

For example, what can we say about the complexity of the formation width decision problem:

Given a sequence $u$ and an integer $k$, is $fw(u)  \leq k$?
1 reply
JGeneson
Nov 19, 2019
JGeneson
Nov 25, 2019
No more topics!
a