% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{C:/Users/Jesse/Desktop/fw/e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{rem}[thm]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A relationship between generalized Davenport-Schinzel sequences and interval chains}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Jesse Geneson\thanks{Supported by the NSF Graduate Research Fellowship under Grant No. 1122374.}\\
\small Department of Mathematics\\[-0.8ex]
\small MIT\\[-0.8ex]
\small Massachusetts, U.S.A.\\
\small\tt geneson@math.mit.edu
}

\date{\dateline{October 20, 2014}{acceptance date}\\
\small Mathematics Subject Classification: 05D99}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
Let an $(r, s)$-formation be a concatenation of $s$ permutations of $r$ distinct letters, and let a block of a sequence be a subsequence of consecutive distinct letters. A $k$-chain on $[1, m]$ is a sequence of $k$ consecutive, disjoint, nonempty intervals of the form $[a_{0}, a_{1}] [a_{1}+1, a_{2}] \ldots [a_{k-1}+1, a_{k}]$ for integers $1 \leq a_{0} \leq a_{1} < \ldots < a_{k} \leq m$, and an $s$-tuple is a set of $s$ distinct integers. An $s$-tuple stabs an interval chain if each element of the $s$-tuple is in a different interval of the chain. Alon et al. (2008) observed similarities between bounds for interval chains and Davenport-Schinzel sequences, but did not identify the cause.

We show for all $r \geq 1$ and $1 \leq s \leq k \leq m$ that the maximum number of distinct letters in any sequence $S$ on $m+1$ blocks avoiding every $(r, s+1)$-formation such that every letter in $S$ occurs at least $k+1$ times is the same as the maximum size of a collection $X$ of (not necessarily distinct) $k$-chains on $[1, m]$ so that there do not exist $r$ elements of $X$ all stabbed by the same $s$-tuple.

Let $D_{s,k}(m)$ be the maximum number of distinct letters in any sequence which can be partitioned into $m$  blocks, has at least $k$ occurrences of every letter, and has no subsequence forming an alternation of length $s$. Nivasch (2010) proved that $D_{5, 2d+1}(m) = \Theta( m \alpha_{d}(m))$ for all fixed $d \geq 2$. We show that $D_{s+1, s}(m) = \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $s \geq 2$. We also prove new lower bounds which imply that $D_{5, 6}(m) = \Theta(m \log \log m)$ and $D_{5, 2d+2}(m) = \Theta(m \alpha_{d}(m))$ for all fixed $d \geq 3$. 

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} alternations, formations, generalized Davenport-Schinzel sequences, interval chains, inverse Ackermann functions, permutations
\end{abstract}

\section{Introduction}
A sequence $s$ \emph{contains} a sequence $u$ if some subsequence of $s$ can be changed into $u$ by a one-to-one renaming of its letters. If $s$ does not contain $u$, then $s$ \emph{avoids} $u$. A sequence $s$ is called \emph{$r$-sparse} if any $r$ consecutive letters in $s$ are distinct. Collections of contiguous distinct letters in $s$ are called \emph{blocks}. 

A \emph{generalized Davenport-Schinzel sequence} is an $r$-sparse sequence avoiding a fixed forbidden sequence (or set of sequences) with $r$ distinct letters. Bounds on the lengths of generalized Davenport-Schinzel sequences were used to bound the complexity of lower envelopes of solution sets of linear homogeneous differential equations \cite{DS}, the complexity of faces in arrangements of arcs \cite{book1}, and the maximum number of edges in $k$-quasiplanar graphs with no pair of edges intersecting in more than $O(1)$ points \cite{FPS, Suk}.

Let $\lambda_{s}(n)$ be the maximum length of any $2$-sparse sequence with $n$ distinct letters which avoids alternations of length $s+2$. For $s = 1$ and $s = 2$, $\lambda_{s}(n) = \Theta(n)$. However, Hart and Sharir \cite{HaSh} showed that $\lambda_{3}(n) = \Theta(n \alpha(n))$, such that $\alpha(n)$ denotes the inverse Ackermann function. Nivasch \cite{Niv} and Klazar \cite{Kl1} proved that $\lim_{n \rightarrow \infty} \frac{\lambda_{3}(n)}{n \alpha(n)} = 2$. 

Agarwal, Sharir, Shor \cite{SAS} and Nivasch \cite {Niv} proved that $\lambda_{s}(n) = n 2^{\frac{1}{t!}\alpha(n)^{t} \pm O(\alpha(n)^{t-1})}$ for even $s \geq 4$ with $t = \frac{s-2}{2}$. Pettie \cite{Pet1} proved that $\lambda_{5}(n) = \Theta(n \alpha(n) 2^{\alpha(n)})$ and that $\lambda_{s}(n) =  n 2^{\frac{1}{t!}\alpha(n)^{t} \pm O(\alpha(n)^{t-1})}$ for odd $s \geq 7$ with $t = \frac{s-3}{2}$.

In \cite{Niv}, similar bounds were also derived for a different sequence extremal function. Let an \emph{$(r, s)$-formation} be a concatenation of $s$ permutations of $r$ distinct letters. For example $abcddcbaadbc$ is a $(4,3)$-formation. Define $F_{r,s}(n)$ to be the maximum length of any $r$-sparse sequence with $n$ distinct letters which avoids all $(r,s)$-formations. 

Klazar \cite{Kl} proved that $F_{r, 2}(n) = \Theta(n)$ and $F_{r, 3}(n) = \Theta(n)$ for every $r > 0$. Nivasch proved that $F_{r, 4}(n) = \Theta(n \alpha(n))$ for $r \geq 2$. Nivasch \cite{Niv} showed that $F_{r,s}(n) = n 2^{\frac{1}{t!}\alpha(n)^{t} \pm O(\alpha(n)^{t-1})}$ for all $r \geq 2$ and odd $s \geq 5$ with $t = \frac{s-3}{2}$.  Pettie \cite{Pet2} proved for $r = 2$ that $F_{r,6}(n) = \Theta(n \alpha(n) 2^{\alpha(n)})$ and that $F_{r,s}(n) =  n 2^{\frac{1}{t!}\alpha(n)^{t} \pm O(\alpha(n)^{t-1})}$ for even $s \geq 8$ with $t = \frac{s-4}{2}$. When $r \geq 3$, Pettie proved that $F_{r,s}(n) =  n 2^{\frac{1}{t!}\alpha(n)^{t}\log{\alpha(n)} \pm O(\alpha(n)^{t})}$ for even $s \geq 6$ with $t = \frac{s-4}{2}$.

To define the Ackermann hierarchy let $A_{1}(n) = 2n$ and for $k \geq 2$, $A_{k}(0) = 1$ and $A_{k}(n) = A_{k-1}(A_{k}(n-1))$ for $n \geq 1$. To define the inverse functions let $\alpha_{k}(x) = \min \left\{n : A_{k}(n) \geq x \right\}$ for all $k \geq 1$. We define the Ackermann function $A(n)$ to be $A_{n}(3)$ as in \cite{Niv}. The inverse Ackermann function $\alpha(n)$ is defined to be $\min \left\{x : A(x) \geq n \right\}$.

Nivasch's bounds on $\lambda_{s}(n)$ were derived using an extremal function which maximizes number of distinct letters instead of length. Let $D_{s,k}(m)$ be the maximum number of distinct letters in any sequence on $m$ blocks avoiding alternations of length $s$ such that every letter occurs at least $k$ times. Clearly $D_{s, k}(m) = 0$ if $m < k$ and $D_{s,k}(m) = \infty$ if $k < s-1$ and $k \leq m$. Nivasch proved that $\Psi_{s}(m, n) \leq k (D_{s, k}(m)+n)$ \cite{Niv}, where $\Psi_{s}(m, n)$ denotes the maximum possible length of any sequence on $m$ blocks with $n$ distinct letters that avoids alternations of length $s$.

Nivasch also proved that $D_{5, 2d+1}(m) = \Theta(m \alpha_{d}(m))$ for each fixed $d \geq 2$ (but noted that the bounds on $D_{5, k}(m)$ were not tight for even $k$). Sundar \cite{Sund} derived similar bounds in terms of $m$ on functions related to the Deque conjecture.

Let $F_{r, s, k}(m)$ be the maximum number of distinct letters in any sequence on $m$ blocks avoiding every $(r, s)$-formation such that every letter occurs at least $k$ times. Clearly $F_{r, s, k}(m) = 0$ if $m < k$ and $F_{r,s,k}(m) = \infty$ if $k < s$ and $k \leq m$. Every $(r, s)$-formation contains an alternation of length $s+1$ for every $r \geq 2$, so $D_{s+1, k}(m) \leq F_{r, s, k}(m)$ for every $r \geq 2$. Nivasch proved that $\Psi'_{r,s}(m, n) \leq k (F_{r, s, k}(m)+n)$ \cite{Niv}, where $\Psi'_{r,s}(m, n)$ denotes the maximum possible length of any sequence on $m$ blocks with $n$ distinct letters that avoids every $(r,s)$-formation.

Nivasch also proved for $r \geq 2$ that $F_{r, 4, 2d+1}(m) = \Theta(m \alpha_{d}(m))$ for each fixed $d \geq 2$. The recursive inequalities for the upper bounds on $F_{r, 4, 2d+1}(m)$ in \cite{Niv} also imply that $F_{r, 4, 6}(m) = O(m \log \log m)$ and that $F_{r, 4, 2d+2}(m) = O( m \alpha_{d}(m))$.

Similar bounds were also derived on an extremal function related to interval chains. A \emph{$k$-chain on $[1, m]$} is a sequence of $k$ consecutive, disjoint, nonempty intervals of the form $[a_{0}, a_{1}] [a_{1}+1, a_{2}] \ldots [a_{k-1}+1, a_{k}]$ for integers $1 \leq a_{0} \leq a_{1} < \ldots < a_{k} \leq m$. An \emph{$s$-tuple} is a set of $s$ distinct integers. An $s$-tuple \emph{stabs} an interval chain if each element of the $s$-tuple is in a different interval of the chain.

Let $\zeta_{s, k}(m)$ denote the minimum size of a collection of $s$-tuples such that every $k$-chain on $[1,m]$ is stabbed by an $s$-tuple in the collection. Clearly $\zeta_{s, k}(m) = 0$ if $m < k$ and $\zeta_{s, k}(m)$ is undefined if $k < s$ and $k \leq m$. 

Alon \emph{et al.} \cite{AKNSS} showed that $\zeta_{s, s}(m) = \binom{m- \lfloor \frac{s}{2} \rfloor}{\lceil \frac{s}{2} \rceil}$ for $s \geq 1$, $\zeta_{3, 4}(m) = \Theta(m \log m)$, $\zeta_{3, 5}(m) = \Theta(m \log \log m)$, and $\zeta_{3, k} (m) = \Theta(m \alpha_{\lfloor \frac{k}{2} \rfloor}(m))$ for $k \geq 6$. Alon \emph{et al.} \cite{AKNSS} observed similarities between bounds for interval chains and Davenport-Schinzel sequences, but did not identify the cause.

Let $\eta_{r, s, k}(m)$ denote the maximum size of a collection $X$ of not necessarily distinct $k$-chains on $[1, m]$ so that there do not exist $r$ elements of $X$ all stabbed by the same $s$-tuple. Clearly $\eta_{r, s, k}(m) = 0$ if $m < k$ and $\eta_{r, s, k}(m) = \infty$ if $k < s$ and $k \leq m$. 

In Section~\ref{formint} we show that $\eta_{r, s, k}(m) = F_{r, s+1, k+1}(m+1)$ for all $r \geq 1$ and $1 \leq s \leq k \leq m$. 

\begin{lem}
$\zeta_{s, k}(m) \geq \eta_{2, s, k}(m)$ for all $1 \leq s \leq k \leq m$.
\end{lem}

\begin{proof}
Let $X$ be a collection of $k$-chains on $[1,m]$ so that there do not exist $2$ elements of $X$ that are stabbed by the same $s$-tuple. Then by the pigeonhole principle, $|X|$ is the minimum possible size of a collection $Y$ of $s$-tuples such that every $k$-chain in $X$ is stabbed by an $s$-tuple in $Y$.
\end{proof}

The last lemma and the equality in Section~\ref{formint} imply that $D_{s+2, k+1}(m+1) \leq \zeta_{s,k}(m)$ for all $1 \leq s \leq k \leq m$. This implies that $D_{s+1, s}(m) \leq \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $s \geq 2$, $D_{5, 6}(m) = O(m \log \log m)$, and $D_{5, 2d+2}(m) = O(m \alpha_{d}(m))$ for $d \geq 3$.

In Section~\ref{lbounds} we construct alternation-avoiding sequences to prove lower bounds on $D_{s, k}(m)$. We prove that $D_{s+1, s}(m) = \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $s \geq 2$. Furthermore we show that $D_{5, 6}(m) = \Omega(m \log \log m)$ and $D_{5, 2d+2}(m) = \Omega(\frac{1}{d} m \alpha_{d}(m))$ for $d \geq 3$. Thus the bounds on $D_{5, d}(m)$ have a multiplicative gap of $O(d)$ for all $d$.

\section{Proof that $F_{r, s+1, k+1}(m+1) = \eta_{r, s, k}(m)$}\label{formint}
We show that $F_{r, s+1, k+1}(m+1) = \eta_{r, s, k}(m)$ for all $r \geq 1$ and $1 \leq s \leq k \leq m$ using maps like those between matrices and sequences in \cite{CK} and \cite{Pet}.

\begin{lem}
\label{equalupper}
$F_{r, s+1, k+1}(m+1) \leq \eta_{r, s, k}(m)$ for all $r \geq 1$ and $1 \leq s \leq k \leq m$.
\end{lem}

\begin{proof}
Let $P$ be a sequence with $F_{r, s+1, k+1}(m+1)$ distinct letters and $m+1$ blocks $1, \ldots, m+1$ such that no subsequence is a concatenation of $s+1$ permutations of $r$ different letters and every letter in $P$ occurs at least $k+1$ times. Construct a collection of $k$-chains on $[1,m]$ by converting each letter in $P$ to a $k$-chain: if the first $k+1$ occurrences of letter $a$ are in blocks $a_{0}, \ldots, a_{k}$, then let $a^{*}$ be the $k$-chain with $i^{th}$ interval $[ a_{i-1}, a_{i}-1 ]$.

Suppose for contradiction that there exist $r$ distinct letters $q_{1}, \ldots, q_{r}$ in $P$ such that $q_{1}^{*}, \ldots, q_{r}^{*}$ are stabbed by the same $s$-tuple $1 \leq j_{1} < \ldots < j_{s} \leq m$. Let $j_{0} = 0$ and $j_{s+1} = m+1$. Then for each $1 \leq i \leq s+1$, $q_{n}$ occurs in some block $b_{n,i}$ such that $b_{n, i} \in [ j_{i-1}+1, j_{i}]$ for every $1 \leq n \leq r$. Hence the letters $q_{1}, \ldots, q_{r}$ make an $(r, s+1)$-formation in $P$, a contradiction.
\end{proof}

\begin{cor}
$D_{s+2, k+1}(m+1) \leq \zeta_{k}^{s}(m)$ for all $1 \leq s \leq k \leq m$.
\end{cor}

The bounds on $\zeta_{s, k}(m)$ in \cite{AKNSS} imply the next corollary.

\begin{cor}
$D_{s+1, s}(m) \leq \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for $s \geq 2$, $D_{5,5}(m) = O(m \log m)$, $D_{5, 6}(m) = O(m \log \log m)$, and $D_{5, k} (m) = O(m \alpha_{\lfloor \frac{k-1}{2} \rfloor}(m))$ for $k \geq 7$.
\end{cor}

To prove that $F_{r, s+1, k+1}(m+1) \geq \eta_{r, s, k}(m)$ for all $r \geq 1$ and $1 \leq s \leq k \leq m$, we convert collections of $k$-chains into sequences with a letter corresponding to each $k$-chain. 

\begin{lem}
\label{equallower}
$F_{r, s+1, k+1}(m+1) \geq \eta_{r, s, k}(m)$ for all $r \geq 1$ and $1 \leq s \leq k \leq m$.
\end{lem}

\begin{proof}
Let $X$ be a maximal collection of $k$-chains on $[1, m]$ so that there do not exist $r$ elements of $X$ all stabbed by the same $s$-tuple. To change $X$ into a sequence $P$ create a letter $a$ for every $k$-chain $a^{*}$ in $X$, and put $a$ in every block $i$ such that either $a^{*}$ has an interval with least element $i$ or $a^{*}$ has an interval with greatest element $i-1$. 

Order the letters in blocks starting with the first block and moving to the last. Let $L_{i}$ be the letters in block $i$ which also occur in some block $j < i$ and let $R_{i}$ be the letters which have first occurrence in block $i$. 

All of the letters in $L_{i}$ occur before all of the letters in $R_{i}$. If $a$ and $b$ are in $L_{i}$, then $a$ appears before $b$ in block $i$ if the last occurrence of $a$ before block $i$ is after the last occurrence of $b$ before block $i$. The letters in $R_{i}$ may appear in any order.

$P$ is a sequence on $m+1$ blocks in which each letter occurs $k+1$ times. Suppose for contradiction that there exist $r$ letters $q_{1}, \ldots, q_{r}$ which form an $(r, s+1)$-formation in $P$. List all $(r, s+1)$-formations on the letters $q_{1}, \ldots, q_{r}$ in $P$ lexicographically, so that formation $f$ appears before formation $g$ if there exists some $i \geq 1$ such that the first $i-1$ elements of $f$ and $g$ are the same, but the $i^{th}$ element of $f$ appears before the $i^{th}$ element of $g$ in $P$. 

Let $f_{0}$ be the first $(r, s+1)$-formation on the list and let $\pi_{i}$ (respectively $\rho_{i}$) be the number of the block which contains the last (respectively first) element of the $i^{th}$ permutation in $f_{0}$ for $1 \leq i \leq s+1$. We claim that $\pi_{i} < \rho_{i+1}$ for every $1 \leq i \leq s$. Suppose for contradiction that for some $1 \leq i \leq s$, $\pi_{i} = \rho_{i+1}$. Let $a$ be the last letter of the $i^{th}$ permutation and let $b$ be the first letter of the $(i+1)^{st}$ permutation. 

Then $a$ occurs before $b$ in block $\pi_{i}$ and the $b$ in $\pi_{i}$ is not the first occurrence of $b$ in $P$, so the $a$ in $\pi_{i}$ is not the first occurrence of $a$ in $P$. Otherwise $a$ would appear after $b$ in $\pi_{i}$. Since the $a$ and $b$ in $\pi_{i}$ are not the first occurrences of $a$ and $b$ in $P$, then the last occurrence of $a$ before $\pi_{i}$ must be after the last occurrence of $b$ before $\pi_{i}$. Let $f_{1}$ be the subsequence obtained by deleting the $a$ in $\pi_{i}$ from $f_{0}$ and inserting the last occurrence of $a$ before $\pi_{i}$. Since the last occurrence of $a$ before $\pi_{i}$ occurs after the occurrence of $b$ in the $i^{th}$ permutation of $f_{0}$, $f_{1}$ is also an $(r, s+1)$-formation. Moreover, $f_{1}$ occurs before $f_{0}$ on the list. This contradicts the definition of $f_{0}$, so for every $1 \leq i \leq s$, $\pi_{i} < \rho_{i+1}$.

For every $1 \leq j \leq r$ and $1 \leq i \leq s+1$, the letter $q_{j}$ appears in some block between $\rho_{i}$ and $\pi_{i}$ inclusive. Since $\pi_{i} < \rho_{i+1}$ for every $1 \leq i \leq s$, the $s$-tuple $(\pi_{1}, \ldots, \pi_{s})$ stabs each of the interval chains $q_{1}^{*}, \ldots, q_{r}^{*}$, a contradiction. Hence $P$ contains no $(r, s+1)$-formation.
\end{proof}

The idea for the next lemma is similar to a proof about doubled formation free matrices in \cite{CK}.

\begin{lem}
$F_{r,s,s}(m) \leq (r-1) \binom{m-\lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for every $r \geq 1$ and $1 \leq s \leq m$.
\end{lem}

\begin{proof}
Let $P$ be a sequence with $m$ blocks such that no subsequence of $P$ is a concatenation of $s$ permutations of $r$ distinct letters and every letter of $P$ occurs at least $s$ times. An occurrence of letter $a$ in $P$ is called even if there are an odd number of occurrences of $a$ to the left of it. Otherwise the occurrence of $a$ is called odd. 

Suppose for contradiction that $P$ has at least $1+(r-1) \binom{m-\lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ distinct letters. The number of distinct tuples $(m_{1}, \ldots, m_{\lfloor \frac{s}{2} \rfloor})$ for which a letter could have even occurrences in blocks $m_{1}, \ldots, m_{\lfloor \frac{s}{2} \rfloor}$ is equal to the number of positive integer solutions to the equation $(1+x_{1})+\ldots + (1+ x_{\lfloor \frac{s}{2} \rfloor})+x_{1+\lfloor \frac{s}{2} \rfloor}= m+1$ if $s$ is even and $(1+x_{1})+\ldots + (1+ x_{\lfloor \frac{s}{2} \rfloor})+x_{1+\lfloor \frac{s}{2} \rfloor}= m$ if $s$ is odd. 

Since for each $s$ the equation has $ \binom{m-\lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ positive integer solutions, by the pigeonhole principle there are at least $r$ distinct letters $q_{1}, \ldots, q_{r}$ with even occurrences in the same $\lfloor \frac{s}{2} \rfloor$ blocks of $P$. Then $P$ contains a concatenation of $s$ permutations of the letters $q_{1}, \ldots, q_{r}$, a contradiction. 
\end{proof}

The last lemma is an alternative proof that $D_{s+1, s}(m) \leq \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ since $D_{s+1, s}(m) \leq F_{r,s,s}(m)$ for all $s, m \geq 1$ and $r \geq 2$. 

\section{Lower bounds}\label{lbounds}

In the last section we showed that $D_{s+1, s}(m) \leq \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for $s \geq 2$. The next lemma provides a matching lower bound.

\begin{lem}
$D_{s+1, s}(m) \geq \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $s \geq 2$ and $m \geq s+1$.
\end{lem}

\begin{proof}
For every $s \geq 1$ and $m \geq s+1$ we build a sequence $X_{s}(m)$ with $\binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ distinct letters. First consider the case of even $s \geq 2$. The sequence $X_{s}(m)$ is the concatenation of $m-1$ fans, so that each fan is a palindrome consisting of two blocks of equal length.

First assign letters to each fan without ordering them. Create a letter for every $\frac{s}{2}$-tuple of non-adjacent fans, and put each letter in every fan in its $\frac{s}{2}$-tuple. Then order the letters in each fan starting with the first fan and moving to the last. Let $L_{i}$ be the letters in fan $i$ which occur in some fan $j < i$ and let $R_{i}$ be the letters which have first occurrence in fan $i$.

In the first block of fan $i$ all of the letters in $L_{i}$ occur before all of the letters in $R_{i}$. If $a$ and $b$ are in $L_{i}$, then $a$ occurs before $b$ in the first block of fan $i$ if the last occurrence of $a$ before fan $i$ is after the last occurrence of $b$ before fan $i$. If $a$ and $b$ are in $R_{i}$, then $a$ occurs before $b$ in the first block of fan $i$ if the first fan which contains $a$ without $b$ is before the first fan which contains $b$ without $a$. 

Consider for any distinct letters $x$ and $y$ the maximum alternation contained in the subsequence of $X_{s}(m)$ restricted to $x$ and $y$. The maximum alternation is constructed starting with a fan that contains only $x$, and successively adding adjacent fans. Any other fans which contain $x$ without $y$ or $y$ without $x$ add at most $1$ to the alternation length. Any fans which contain both $x$ and $y$ add $2$ to the alternation length. If $x$ and $y$ occur together in $i$ fans, then the length of their alternation is at most $(\frac{s}{2}-i)+(\frac{s}{2}-i)+2i = s$.

Every pair of adjacent fans have no letters in common, so every pair of adjacent blocks in different fans can be joined as one block when the $m-1$ fans are concatenated to form $X_{s}(m)$. Thus $X_{s}(m)$ has $m$ blocks and $\binom{m- \frac{s}{2}}{\frac{s}{2}}$ letters, and each letter occurs $s$ times. 

For odd $s \geq 3$, construct $X_{s}(m)$ by adding a block $r$ after $X_{s-1}(m-1)$ containing all of the letters in $X_{s-1}(m-1)$ such that $a$ occurs before $b$ in $r$ if the last occurrence of $a$ in $X_{s-1}(m-1)$ is after the last occurrence of $b$ in $X_{s-1}(m-1)$. Then $X_{s}(m)$ contains no alternation of length $s+1$ since $X_{s-1}(m-1)$ contains no alternation of length $s$. Moreover $X_{s}(m)$ has $m$ blocks and $\binom{m- \frac{s+1}{2}}{\frac{s-1}{2}}$ letters, and each letter occurs $s$ times. 
\end{proof}

The next lemma shows how to extend the lower bounds on $D_{s+1, s}(m)$ to $F_{r,s,s}(m)$.

\begin{lem}
$F_{r,s,k}(m) \geq (r-1)F_{2,s,k}(m)$ for all $r \geq 1$ and $1 \leq s \leq k \leq m$. 
\end{lem}

\begin{proof}
Let $P$ be a sequence with $F_{2,s,k}(m)$ distinct letters and $m$ blocks such that no subsequence is a concatenation of $s$ permutations of two distinct letters and every letter occurs at least $k$ times. $P'$ is the sequence obtained from $P$ by creating $r-1$ new letters $a_{1}, \ldots, a_{r-1}$ for each letter $a$ and replacing every occurrence of $a$ with the sequence $a_{1} \ldots a_{r-1}$. 

Suppose for contradiction that $P'$ contains an $(r,s)$-formation on the letters $q_{1}, \ldots, q_{r}$. Then there exist indices $i$, $j$, $k$, $l$ and distinct letters $a$, $b$ such that $q_{i} = a_{j}$ and $q_{k} = b_{l}$. $P'$ contains a $(2,s)$-formation on the letters $q_{i}$ and $q_{k}$, so $P$ contains a $(2,s)$ formation on the letters $a$ and $b$, a contradiction. Then $P'$ is a sequence with $(r-1) F_{2,s,k}(m)$ distinct letters and $m$ blocks such that no subsequence is a concatenation of $s$ permutations of $r$ distinct letters and every letter occurs at least $k$ times.
\end{proof}

\begin{cor}
$F_{r,s,s}(m) = (r-1) \binom{m-\lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $r \geq 1$ and $m \geq s \geq 1$.
\end{cor}

The proof of the next theorem is much like the proof that $D_{5, 2d+1}(m) = \Omega(\frac{1}{d} m \alpha_{d}(m))$ for $d \geq 2$ in \cite{Niv}. The only substantial difference is the base case.

\begin{thm}
$D_{5, 6}(m) = \Omega(m \log \log m)$ and $D_{5, 2d+2}(m) = \Omega(\frac{1}{d} m \alpha_{d}(m))$ for $d \geq 3$.
\end{thm}

We prove this theorem by constructing a family of sequences that avoid $ababa$. For all $d, m \geq 1$, we inductively construct sequences $G_{d}(m)$ in which each letter appears $2d+2$ times and no two distinct letters make an alternation of length $5$. This proof uses a different definition of fan: fans will be the concatenation of two palindromes with no letters in common. Each palindrome consists of two blocks of equal length. 

For $d, m \geq 1$ the blocks in $G_{d}(m)$ containing only first and last occurrences of letters are called \emph{special blocks}. Let $S_{d}(m)$ be the number of special blocks in $G_{d}(m)$. Every letter has its first and last occurrence in a special block, and each special block in $G_{d}(m)$ has $m$ letters. 

Blocks that are not special are called \emph{regular}. No regular block in $G_{d}(m)$ has special blocks on both sides, but every special block has regular blocks on both sides. 

The sequences $G_{1}(m)$ are the concatenation of $m+1$ fans. In each fan the second block of the first palindrome and the first block of the second palindrome make one block together since they are adjacent and have no letters in common. The first palindrome in the first fan and the second palindrome in the last fan are empty. 

There is a letter for every pair of fans and the letter is in both of those fans. The letters with last appearance in fan $i$ are in the first palindrome of fan $i$. They appear in fan $i$'s first palindrome's first block in reverse order of the fans in which they first appear. The letters with first appearance in fan $i$ are in the second palindrome of fan $i$. They appear in fan $i$'s second palindrome's first block in order of the fans in which they last appear. For example, the sequence $G_{1}(4)$ is isomorphic to the following sequence, such that $( )$ denotes special block boundaries, $[ ]$ denotes regular block boundaries, and $\left< \right>$ denotes fan boundaries:\\

\noindent $\left<[ ](a b c d)[d c b a]\right>\left<[a](a e f g)[g f e]\right>\left<[e b](b e h i)[i h]\right>\left<[h f c](c f h j)[j]\right>\left<[j i g d](d g i j)[ ]\right>$\\


\begin{lem}
$G_{1}(m)$ contains no alternation of length $5$.
\end{lem} 

\begin{proof}
Let $x$ and $y$ be any two letters in $G_{1}(m)$. If $x$ and $y$ do not occur in any fan together, then clearly the subsequence of $G_{1}(m)$ restricted to $x$ and $y$ contains no alternation of length $5$. If $x$ and $y$ occur together in a fan, then their common fan contains an alternation on $x$ and $y$ of length $2$ or $3$. By the construction of $G_{1}(m)$, this alternation is extended to length at most $4$ by the occurrences of $x$ and $y$ outside the common fan.
\end{proof}

For all $d \geq 1$ the sequence $G_{d}(1)$ is defined to consist of $2d+2$ copies of the letter $1$. The first and last copies of $1$ are both special blocks, and there are empty regular blocks before the first $1$ and after the last $1$. 

The sequence $G_{d}(m)$ for $d, m \geq 2$ is constructed inductively from $G_{d}(m-1)$ and $G_{d-1}(S_{d}(m-1))$. Let $f = S_{d}(m-1)$ and $g = S_{d-1}(f)$. Make $g$ copies $X_{1}, \ldots, X_{g}$ of $G_{d}(m-1)$ and one copy $Y$ of $G_{d-1}(f)$, so that no copies of $G_{d}(m-1)$ have any letters in common with $Y$ or each other. 

Let $Q_{i}$ be the $i^{th}$ special block of $Y$. If the $l^{th}$ element of $Q_{i}$ is the first occurrence of the letter $a$, then insert $aa$ right after the $l^{th}$ special block of $X_{i}$. If the $l^{th}$ element of $Q_{i}$ is the last occurrence of $a$, then insert $aa$ right before the $l^{th}$ special block of $X_{i}$. Replace $Q_{i}$ in $Y$ by the modified $X_{i}$ for every $i$. The resulting sequence is $G_{d}(m)$. 

\begin{lem}
For all $d$ and $m$, $G_{d}(m)$ avoids $ababa$.
\end{lem}

\begin{proof}
Given that the alternations in $G_{1}(m)$ have length at most $4$ for all $m \geq 1$, then the rest of the proof is the same as the proof in \cite{Niv} that $Z_{d}(m)$ avoids $a b a b a$.
\end{proof}

Let $L_{d}(m)$ be the length of $G_{d}(m)$. Observe that $L_{d}(m) = (d+1)m S_{d}(m)$ since each letter in $G_{d}(m)$ occurs $2d+2$ times, twice in special blocks, and each special block has $m$ letters.

Define $N_{d}(m)$ as the number of distinct letters in $G_{d}(m)$ and $M_{d}(m)$ as the number of blocks in $G_{d}(m)$. Also let $X_{d}(m) = \frac{M_{d}(m)}{S_{d}(m)}$ and $V_{d}(m) = \frac{L_{d}(m)}{M_{d}(m)}$. We bound $X_{d}(m)$ and $V_{d}(m)$ as in \cite{Niv}. 

\begin{lem}\label{vd}
For all $m, d \geq 1$, $X_{d}(m) \leq 2d+2$ and $V_{d}(m) \geq \frac{m}{2}$.
\end{lem}

\begin{proof}
By construction $S_{1}(m) = m+1$ for $m \geq 1$, $S_{d}(1) = 2$ for $d \geq 2$, and $S_{d}(m) = S_{d}(m-1)S_{d-1}(S_{d}(m-1))$ for $d, m \geq 2$. Furthermore $M_{1}(m) = 3m+3$, $M_{d}(1) = 2d+4$ for $d \geq 2$, and $M_{d}(m) = M_{d}(m-1)S_{d-1}(S_{d}(m-1))+M_{d-1}(S_{d}(m-1))-S_{d-1}(S_{d}(m-1))$ for $d, m \geq 2$.

Thus $S_{2}(m) = S_{2}(m-1)(S_{2}(m-1)+1) \leq 2 (S_{2}(m-1))^{2}$ and $S_{2}(1) = 2$. Since $S'(m) = 2^{2^{m}-1}$ satisfies the recurrence $S'(1) = 2$ and $S'(m+1) = 2 (S'(m))^{2}$, then $2^{2^{m-1}} \leq S_{2}(m) \leq 2^{2^{m}-1}$. For $d \geq 2$, $S_{d}(2) = 2S_{d-1}(2)$ and $S_{1}(2) = 3$. So $S_{d}(2) = 3 \times 2^{d-1}$.

For $d \geq 2$, $M_{d}(2) = (2d+3)(3 \times 2^{d-2})+M_{d-1}(2)$ and $M_{1}(2) = 9$. Hence $M_{d}(2) = (6d+3)2^{d-1}$.

Then $X_{1}(m) = 3$ for all $m$, $X_{d}(1) = d+2$ for all $d \geq 2$, and $X_{d}(2) = 2d+1$ for all $d \geq 2$. For $d, m \geq 2$, $X_{d}(m) = X_{d}(m-1)+\frac{X_{d-1}(S_{d}(m-1))-1}{S_{d}(m-1)}$.

We prove by induction on $d$ that $X_{d}(m) \leq 2d+2$ for all $m, d \geq 1$. Observe that the inequality holds for $X_{1}(m)$, $X_{d}(1)$, and $X_{d}(2)$ for all $m, d$.

Fix $d$ and suppose $X_{d-1}(m) \leq 2d$ for all $m$. Then $X_{d}(m) \leq X_{d}(m-1)+\frac{2d-1}{S_{d}(m-1)}$. Hence $X_{d}(m) \leq X_{d}(2) + (2d-1) \sum_{n = 2}^{\infty} S_{d}(n)^{-1} = 2d+1+(2d-1) \sum_{n = 2}^{\infty} S_{d}(n)^{-1}$.

Since $S_{d}(m) \geq 2 S_{d}(m-1)$ for all $d, m \geq 2$, then $\sum_{n = 2}^{\infty} S_{d}(n)^{-1} \leq 2S_{d}(2)^{-1} = \frac{1}{3 \times 2^{d-2}} \leq \frac{1}{2d-1}$ for all $d \geq 2$, so $X_{d}(m) \leq 2d+2$. Hence $V_{d}(m) = \frac{L_{d}(m)}{M_{d}(m)} = \frac{(d+1)m S_{d}(m)}{M_{d}(m)} \geq \frac{m}{2}$. 
\end{proof}

The lower bounds on $D_{5, 2d+2}(m)$ for each $d \geq 2$ are proved in the following subsections. 

\subsection{Bound for $d = 2$}

If $d = 2$, let $m_{i} = M_{2}(i)$ and $n_{i} = N_{2}(i)$. Then $m_{i} = X_{2}(i)S_{2}(i) \leq 6 S_{2}(i) \leq 6 (2^{2^{i}-1}) \leq 2^{2^{i}+2}$ for $i \geq 1$. Then $i = \Omega(\log \log m_{i})$, so $n_{i} = \frac{L_{2}(i)}{6} = \frac{V_{2}(i) M_{2}(i)}{6} \geq \frac{i M_{2}(i)}{12} = \Omega(m_{i} \log \log m_{i})$.

We use interpolation to extend the bound from $m_{i}$ to $m$. Let $i$ and $t$ satisfy $m_{i} \leq m < m_{i+1}$ and $t = \lfloor \frac{m}{m_{i}} \rfloor$. Concatenate $t$ copies of $G_{2}(i)$ with no letters in common for a total of at least $\lfloor \frac{m}{m_{i}}\rfloor n_{i} = \Omega(m \log \log m)$ letters. Hence $D_{5, 6}(m) = \Omega(m \log \log m)$.

\subsection{Bound for $d = 3$}

We prove that $S_{3}(m) \leq A_{3}(2m)$ following the method of \cite{Niv}. Since $S_{3}(m) = S_{3}(m-1)S_{2}(S_{3}(m-1)) \leq S_{2}(S_{3}(m-1))^{2} \leq 2^{2^{S_{3}(m-1)+1}-2}$, then let $F(m) = 2^{2^{m+1}-2}$ and $G(m) = 2^{2^{m}}$. Then $2F(m) = 2^{2^{m+1}-1} \leq 2^{2^{2m}} = G(2m)$ for every $m \geq 0$. Thus $S_{3}(m) \leq F^{(m-1)}(S_{3}(1)) < 2F^{(m-1)}(S_{3}(1)) \leq G^{(m-1)}(2S_{3}(1)) = A_{3}(2m)$. 

Let $m_{i} = M_{3}(i)$ and $n_{i} = N_{3}(i)$. Therefore $m_{i} = X_{3}(i)S_{3}(i) \leq 8 S_{3}(i) \leq A_{3}(2i+2)$ for $i \geq 1$. So $i = \Omega(\alpha_{3}(m_{i}))$ and $n_{i} = N_{3}(i) = \frac{L_{3}(i)}{8} = \frac{V_{3}(i)M_{3}(i)}{8} \geq \frac{i M_{3}(i)}{16} = \Omega(m_{i} \alpha_{3}(m_{i}))$. Then $D_{5, 8}(m) = \Omega(m \alpha_{3}(m))$ by interpolation.

\subsection{Bound for $d \geq 4$}

For each $d\geq 4$ we prove that $S_{d}(m) \leq A_{d}(m+2)$ for $m \geq 1$ by induction on $d$. Since $S_{4}(m) = S_{4}(m-1)S_{3}(S_{4}(m-1)) \leq S_{3}(S_{4}(m-1))^{2}$, then let $F(m) = S_{3}(m)^{2}$. Since $4 F(m) \leq A_{3}(4m)$ and $A_{4}(3) > 4 S_{4}(1)$, then $S_{4}(m) \leq F^{(m-1)}(S_{4}(1)) < 4 F^{(m-1)}(S_{4}(1)) \leq A_{3}^{(m-1)}(4 S_{4}(1)) < A_{4}(m+2)$. 

Fix $d > 4$ and suppose that $S_{d-1}(m) \leq A_{d-1}(m+2)$. Define $F(m) = S_{d-1}(m)^{2}$. Since $4 F(m) \leq A_{d-1}(4m)$ and $A_{d}(3) > 4 S_{d}(1)$, then $S_{d}(m) \leq F^{(m-1)}(S_{d}(1)) < 4 F^{(m-1)}(S_{d}(1)) \leq A_{d-1}^{(m-1)}(4 S_{d}(1)) < A_{d}(m+2)$. 

Fix $d \geq 4$. Let $m_{i} = M_{d}(i)$ and $n_{i} = N_{d}(i)$. Then $m_{i} = X_{d}(i)S_{d}(i) \leq (2d+2)S_{d}(i) \leq (2d+2)A_{d}(i+2) \leq A_{d}(i+3)$. Then $i \geq \alpha_{d}(m_{i})-3$, so $n_{i} = \frac{L_{d}(i)}{2d+2} = \frac{V_{d}(i) M_{d}(i)}{2d+2} \geq \frac{i M_{d}(i)}{4d+4} = \Omega(\frac{1}{d} m_{i} \alpha_{d}(m_{i}))$. By interpolation $D_{5, 2d+2}(m) = \Omega(\frac{1}{d} m \alpha_{d}(m))$ for $d \geq 4$. 

\begin{cor}
If $r \geq 2$, then $F_{r, 4, 6}(m) = \eta_{r, 3, 5}(m) = \Omega(m \log \log m)$ and $F_{r, 4, 2d+2}(m) = \eta_{r, 3, 2d+1}(m) = \Omega(\frac{1}{d} m \alpha_{d}(m))$ for $d \geq 3$. 
\end{cor}

\subsection*{Acknowledgments}
This research was supported by the NSF graduate research fellowship under Grant No. 1122374. The author thanks Seth Pettie for comments on this paper and Peter Shor for improving the bounds on $S_{2}(m)$ in Lemma~\ref{vd}. The author also thanks the anonymous referees for their helpful suggestions.

\begin{thebibliography}{}
\bibitem{book1} M. Sharir and P.K. Agarwal. Davenport-Schinzel sequences and their geometric applications. Cambridge University Press, Cambridge, 1995.
\bibitem{SAS} P.K. Agarwal, M. Sharir, and P. Shor. Sharp upper and lower bounds for the length of general Davenport-Schinzel sequences. Journal of Combinatorial Theory Series A, 52 (1989) 228-274.
\bibitem{AKNSS} N. Alon, H. Kaplan, G. Nivasch, M. Sharir, and S. Smorodinsky. Weak epsilon-nets and interval chains. J. ACM, 55 (2008).
\bibitem{CK} J. Cibulka and J. Kyn\v{c}l. Tight bounds on the maximum size of a set of permutations with bounded vc-dimension. Journal of Combinatorial Theory Series A, 119 (2012) 1461-1478.
\bibitem{DS} H. Davenport and A. Schinzel. A combinatorial problem connected with differential equations. American Journal of Mathematics, 87 (1965) 684-694.
\bibitem{FPS} J. Fox, J. Pach, and A. Suk. The number of edges in k-quasiplanar graphs. SIAM Journal of Discrete Mathematics, 27 (2013) 550-561.
\bibitem{HaSh} S. Hart and M. Sharir. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica, 6 (1986) 151-177
\bibitem{Kl} M. Klazar. A general upper bound in the extremal theory of sequences. Commentationes Mathematicae Universitatis Carolinae, 33 (1992) 737-746.
\bibitem{Kl1} M. Klazar. On the maximum lengths of Davenport-Schinzel sequences. Contemporary trends in discrete mathematics (DIMACS series in discrete mathematics and theoretical computer science), 49 (1999) 169-178.
\bibitem{Niv} G. Nivasch. Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations. Journal of the ACM, 57 (2010).
\bibitem{Pet} S. Pettie. Degrees of nonlinearity in forbidden 0-1 matrix problems. Discrete Mathematics 311 (2011) 2396-2410.
\bibitem{Pet1} S. Pettie. Sharp bounds on Davenport-Schinzel sequences of every order. Symposium on Computational Geometry (2013): 319-328. 
\bibitem{Pet2} S. Pettie. Sharp bounds on formation-free sequences. SODA (2015) 592-604.
\bibitem{Suk} A. Suk and B. Walczak. New bounds on the maximum number of edges in k-quasi-planar graphs. Twenty-first International Symposium on Graph Drawing (2013): 95-106.
\bibitem{Sund} R. Sundar. On the Deque conjecture for the splay algorithm. Combinatorica 12(1): 95-124 (1992).
\end{thebibliography}
\end{document}