\documentclass[12pt]{article}
\usepackage{latexsym}

  \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt 
  \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt 
  \parskip=10pt 
  \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 

\begin{document}

\def\cla#1#2#3#4#5#6#7#8{%autor, nazev, cas., rocnik, rok, stranky, Zbl, MR
  {\sc #1, }#2, {\it #3, }{\bf #4 }(#5), #6. [Zbl #7 and MR #8.]}

\def\claprv#1#2#3#4#5#6#7#8{%autor, nazev, cas., rocnik, rok, stranky, Zbl, MR
  {\sc #1, }#2, {\it #3, }{\bf #4 }(#5), #6. [Zentralblatt f\"ur 
Mathematik und ihre Grenzgebiete #7 and Mathematical Reviews #8.]}

\def\vsbo#1#2#3#4#5#6#7#8#9{
%autor, nazev, strany, editori, nazev, nakladatel, misto a rok, Zbl, MR
  {\sc #1, }#2. In: #4 (editors), {\it #5, }#6, #7; pp. #3. [Zbl #8 and MR #9.]}

\def\vsbor#1#2#3#4#5#6#7#8#9{
%autor, nazev, strany, editori, nazev, nakladatel, misto a rok, Zbl, MR
  {\sc #1, }#2. In: #4 (editor), {\it #5, }#6, #7; pp. #3. [Zbl #8 and MR #9.]}





\newcommand{\DS}{\mathrm{DS}}
\newcommand{\kduk}{\hfill $\Box$}
\newcommand{\R}{\mathbf{R}}
\newcommand{\N}{\mathbf{N}}
\newcommand{\ex}{\mathrm{Ex}}
\newcommand{\al}{\mathrm{al}}
\newcommand{\lin}{\mathrm{Lin}}
\newcommand{\HH}{{\cal H}}
\newcommand{\FF}{{\cal F}}
\newcommand{\GG}{{\cal G}}
\newcommand{\f}{{\lambda}}

  \begin{center} 

  {\bf GENERALIZED DAVENPORT--SCHINZEL SEQUENCES: \\ RESULTS,
PROBLEMS, AND APPLICATIONS} \vskip 20pt


 {\bf Martin Klazar\footnote{Supported by the project LN00A056 of the 
Ministry of Education of the Czech Republic.}}\\
  {\smallit Department of Applied Mathematics (KAM)
and
Institute for Theoretical Computer Science (ITI),\\
Charles University, Malostransk\'e n\'am\v est\'\i\ 25,
118 00 Praha,
Czech Republic} 
  {\tt klazar@kam.mff.cuni.cz}\\  \vskip 10pt 
  \end{center} 

  \vskip 30pt \centerline{\smallit Received:  6/28/01  , Revised:
6/14/02,  Accepted:  8/10/02,
Published:  8/14/02 } 




\vskip 40pt
  \centerline{\bf Abstract} 
   \noindent
We survey in detail extremal results on Davenport--Schinzel sequences 
and their generalizations, from the seminal papers of H. Davenport 
and A. Schinzel in 1965 to present. We discuss geometric 
and enumerative applications, generalizations to colored trees, 
and generalizations to hypergraphs. Eleven illustrative 
examples with proofs are given and nineteen open problems are posed.

   \pagestyle{myheadings} 
   \markright{\smalltt INTEGERS:\smallrm ELECTRONIC JOURNAL OF 
   COMBINATORIAL NUMBER THEORY \smalltt 2 (2002),\#A11\hfill} 

  \thispagestyle{empty} \baselineskip=15pt \vskip 30pt 

\section*{\normalsize 1. Introduction}

{\bf DS sequences.} Why a survey on Davenport--Schinzel sequences? 
(We shall abbreviate 
this term as DS sequences.) Two combinatorially oriented 
survey articles have appeared, 
Stanton and Dirksen \cite{stan_dirk} and Klazar \cite{klaz97}. Both are 
now outdated. Sharir and Agarwal \cite{shar_agar} and Agarwal and 
Sharir \cite{agar_shar} focus on geometric applications. 
Survey and historic sections can be found also in \cite{klaz96a}, 
\cite{klaz_valt}, and \cite{valt99}, but the main goals of 
these works lie elsewhere. In this survey we treat the subject   
in more details and more concisely, pose many open problems, and present
several combinatorially interesting and often unexplored generalizations of the 
original problem. We concentrate on its extremal side but we do discuss 
related enumerative aspects. 

In Section 1 the classical Davenport--Schinzel's extremal functions 
$\f_s(n)$ are introduced and several simple bounds on them are proved. 
Section 2 surveys the extremal results 
on DS sequences which were obtained in the early period, before the superlinearity 
of $\f_3(n)$ was discovered in \cite{hart_shar}. Section 3 explains 
the superlinear bounds on lengths of DS 
sequences. Section 4 presents the generalization of DS sequences to any 
forbidden subsequence, which was introduced in \cite{adam_klaz_valt}. 
Section 5 describes various combinatorial situations where DS sequences and their 
generalizations appear; we discuss geometric graphs, colored trees, $0$-$1$ matrices, ordered 
bipartite graphs, permutations, and set partitions. In Section 6 we describe a further generalization
of DS sequences, or rather of the containment relation that defines them, 
to ordered hypergraphs; this 
section surveys some results of \cite{klaz00} and \cite{klaz_pripr}.  

An $s$-{\em DS sequence\/}, where 
$s\ge 1$ is an integer, is any finite sequence $u=a_1a_2\ldots a_l$ over 
a fixed infinite alphabet $A$ satisfying two conditions:  
\begin{enumerate}
\item For every $i=1,2,\ldots, l-1$ we have $a_i\neq a_{i+1}$, which means that 
$u$ contains no immediate repetition.
\item There do not exist $s$ indices $1\le i_1<i_2<\cdots<i_s\le l$ such that 
$a_{i_1}=a_{i_3}=a_{i_5}=\cdots=a$, $a_{i_2}=a_{i_4}=a_{i_6}=\cdots=b$, and 
$a\neq b$. That is, $u$ contains no alternating subsequence of length $s$.
\end{enumerate}

We write $\DS_s$ to denote the set of $s$-DS sequences.
What are the elements of the alphabet $A$ is not important. We assume that we have in 
$A$ all positive integers $1,2,\ldots$, the letters $a,b,c,d,\ldots$, and perhaps some 
other symbols. The set $A^*$ consists of all finite sequences over $A$. Two sequences 
from $A^*$ which have the same length and which differ only 
by an injective 
renaming of the symbols, for example $121331$ and $2c2aa2$, are called 
{\em isomorphic\/}. For our purposes isomorphic sequences are identical.
Every element of $A^*$ is isomorphic to a unique {\em normal 
sequence\/}. A sequence $u$ is normal if it is over the alphabet $\{1,2,\ldots,n\}$ 
for some integer $n>0$, every $i\in\{1,2,\ldots,n\}$ appears in $u$, and the first occurrences 
of $1,2,\ldots,n$ in $u$, if we scan $u$ from left to right, come in this 
order.

\noindent
{\bf Example 1.} There exist exactly ten normal 4-DS sequences $u$ using at most 3 symbols:
$$
u=\emptyset, 1, 12, 121, 1213, 12131, 123, 1231, 1232,\mbox{and } 12321.
$$
\vskip -36pt
\kduk


$\N$ and $\N_0$ denote the sets $\{1,2,\ldots\}$ and $\{0,1,2,\ldots\}$. 
We write $[n]$, $n\in\N$, for the set $\{1,2,\ldots,n\}$, and $[a,b]$, 
$a,b\in\N,a\le b$, for the set $\{a,a+1,\ldots,b\}$. 
For two functions $f,g: \N\rightarrow\R$, the asymptotic notation $f\ll g$
is synonymous to the $f=O(g)$ notation and means that $|f(n)|<c|g(n)|$ 
holds for every 
$n>n_0$ and a constant $c>0$. The subscripts, such as $f\ll_k g$, indicate that 
$c$ depends only on the mentioned parameters. The notation $f=o(g)$ means that 
$f(n)/g(n)\to 0$ as $n\rightarrow\infty$.

\noindent
{\bf Extremal functions $\mathbf{\f_s(n)}$.} For a sequence $u=a_1a_2\ldots a_l$ 
over $A$, we write $|u|$ to refer to its lentgh $l$. 
$S(u)=\{a_1,a_2,\ldots,a_l\}$ is the set of symbols used in $u$, 
 and $\|u\|=|S(u)|$ is their number. Obviously, always $|u|\ge \|u\|$.
We define, for the integers $s,n\ge 1$,
\begin{equation}\label{Ns}
\f_{s-2}(n)=\max\{|u|:\ u\in\DS_s\ \&\ \|u\|\le n\}.
\end{equation}
The function $\f_{s-2}(n)$ measures the maximum length of $s$-DS sequences using 
at most $n$ symbols. It is trivial that, for every $n\ge 1$ and $s\ge-1$, 
$\f_s(n)<\infty$, $\f_{-1}(n)=0$, $\f_0(n)=1$, $\f_1(n)=n$, $\f_s(1)=1$ (for 
$s\ge 0$), and $\f_s(2)=s+1$.

The notation $\f_s(n)$ for the maximum lengths of DS sequences was introduced in 1986 by 
Hart and Sharir \cite{hart_shar} and quickly became the standard notation.   
The shift $-2$ in the index results from an important application of DS sequences in 
geometry, which we explain in Section 2. All works on DS sequences prior
to   1986 use the original notation $N_s(n)$ of Davenport and 
Schinzel \cite{dave_schi65a}; $N_s(n)=\f_{s-1}(n)$. 
In the survey of these results in Section 2 we use both the original and the modern notation.

\noindent
{\bf Example 2 (\cite{dave_schi65a}).} We bound $\f_s(n)$ in a rough way, determine $\f_2(n)$ 
precisely, and bound $\f_3(n)$ in a finer way. 

We begin with the 
bound 
\begin{equation}\label{DStrivi}
\f_s(n)\le {n\choose 2}s+1
\end{equation}
 which holds for all $n\ge 1$ and $s\ge 0$.
Suppose a sequence $u=a_1a_2\ldots a_l$ satisfies condition 1 
(no immediate repetition) and $\|u\|\le n$, but its length $l$ exceeds 
the bound. Then among the $l-1\ge{n\choose 2}s+1$ two-element sets 
$\{a_i,a_{i+1}\}$, some 
$s+1$ sets must coincide (by the pigeonhole principle), which produces in $u$ an 
alternating subsequence of length $s+2$. This proves (\ref{DStrivi}).  

Let us prove now that for every $n\ge 1$,
$$
\f_2(n)=2n-1. 
$$
The sequences $u=1\;2\;\ldots\;(n-1)\;n\;(n-1)\;\ldots\;2\;1$ show 
that $\f_2(n)\ge 2n-1$. We prove the opposite inequality by induction on $n$.
Certainly $\f_2(1)=1$. In every $u\in\DS_4$ with $\|u\|\le n$ and 
$|u|=\f_2(n)$ some symbol $x$ appears only once;  it is easy to see that any symbol 
sandwiched in the closest repetition has this property (and since $|u|$ is maximum, 
there must be a repetition). Delete $x$ and, if necessary, one of 
its neighbours (to avoid creating an immediate repetition). The sequence $v$ obtained is a 
4-DS sequence and $\|v\|\le n-1$. By induction, 
$\f_2(n)=|u|\le |v|+2\le \f_2(n-1)+2=2(n-1)-1+2=2n-1$.

We prove that 
$$
\f_3(n)\ll n\log n. 
$$
Let $u\in\DS_5$ with $\|u\|\le n$ 
and $|u|=\f_3(n)$. Note that the maximum length implies $\|u\|=n$.
For every $x\in S(u)$ we set $k(x)$ to be the number of appearances of $x$ in $u$. Only 
the first and the last appearance of $x$ in $u$ may have equal neighbours, because 
equal neighbours of any middle appearance of $x$  would create the forbidden 
5-term alternating subsequence. So by deleting at most $k(x)+2$ elements 
from $u$ we get rid of all appearances of $x$ and create no immediate repetition. 
The sequence $v$ obtained is a 5-DS sequence and $\|v\|\le n-1$. Thus 
$\f_3(n)=|u|\le |v|+k(x)+2\le \f_3(n-1)+k(x)+2$. Summing these 
inequalities over all $x\in S(u)$, we obtain the inequality 
$n\f_3(n)\le n\f_3(n-1)+\f_3(n)+2n$, which we rewrite as 
$$
{\f_3(n)\over n}-{\f_3(n-1)\over n-1}\le {2\over n-1}.
$$
Summing these inequalities for $2,3,\ldots,n$ leads to the bound 
$\f_3(n)\le n(1+2(1^{-1}+2^{-1}+\cdots+(n-1)^{-1}))\ll n\log n$.
\kduk

\vskip 30pt
\section*{\normalsize 2. The Early Period}

{\bf The geometric origin of $\mathbf{\f_s(n)}$.} Davenport and Schinzel introduced the 
sequences, which now bear their names, in 1965 in \cite{dave_schi65a}. They were led to 
them by the following 
geometric problem. Suppose $f_1,\ldots, f_n: \R\rightarrow\R$ are $n$ 
continuous functions such that the equation $f_i(x)=f_j(x)$ has for $i\neq j$ 
at most $s$ solutions $x\in\R$. In other words, the graphs of any two functions 
intersect in at most $s$ points. The real line then splits uniquely 
 into $l$ nonempty open intervals $I_1=(-\infty,a_1), 
I_2=(a_1,a_2), I_3=(a_2,a_3), \ldots, I_l=(a_{l-1},\infty)$ so that the 
pointwise minimum function $f(x)=\min_{j=1\ldots n}f_j(x)$ coincides 
on each $I_i$ with a unique function $f_{j(I_i)}$, 
$1\le j(I_i)\le n$, and $j(I_i)\neq j(I_{i+1})$. (See Figure 1 in the 
next section for a very similar situation.)
The problem is how large the number $l$ can be.
It is easy to prove that the sequence $u=j(I_1)j(I_2)\ldots j(I_l)$ is an $(s+2)$-DS sequence.
Thus if every pair $f_i$ and $f_j$, $i\neq j$, has at most $s$ intersections, 
the number $|u|=l$ of the distinct portions of the graph of $f$ can be bounded 
from above by $\f_{s}(n)$. This is the reason for the later $-2$ shift of $s$ in 
$\f_{s-2}(n)$ compared to $\DS_s$. However, in \cite{dave_schi65a} and all works prior to 1986,  
$\max\{|u|:\ u\in\DS_s\;\&\;\|u\|\le n\}$ is denoted by $N_{s-1}(n)$ (or by $N(s-1,n)$). 
For the reader's convenience, in Section 2 we combine both notations. Simply remember that 
$N_s(n)=\f_{s-1}(n)$. 

A natural example of a system $\{f_i\}$ with $|\{x\in\R:\ f_i(x)=f_j(x)\}|\le s$
for every fixed $i\neq j$ is any system of distinct polynomials of degree at most $s$.  
Or, as was the case in \cite{dave_schi65a}, any system of distinct solutions 
of a given homogeneous linear differential equation with constant 
coefficients, of order at most $s+1$. The problem to determine or to bound the maximum 
number $l$ of the portions of the graph of $f$ originated in control theory, and it was 
communicated to Davenport and Schinzel by K. Malanowski (\cite{dave_schi65a}). 
They reduced geometry to combinatorics and asked about the values of $N_s(n)$. 
In \cite{dave_schi65a} they proved that
\begin{eqnarray}
\label{DStriviblbe} (\f_{s-1}(n)=)\ N_s(n)&\le& n(n-1)s+1\\
\label{DSN4} (\f_2(n)=)\ N_3(n)&=&2n-1\\
\label{DSN5} (\f_3(n)=)\ N_4(n)&<& 2n(1+\log n)\\
\label{DSNs} (\f_{s-1}(n)=)\ N_s(n)&\ll_s& n\cdot\exp(10(s\log s)^{1/2}(\log n)^{1/2}).
\end{eqnarray}
Their proofs of (\ref{DStriviblbe})--(\ref{DSN5}) are reproduced in Example 2.
(We have slightly corrected the proof of (\ref{DStriviblbe}) to obtain the somewhat 
better bound (\ref{DStrivi}). Of the two proofs of (\ref{DSN4}) 
in \cite{dave_schi65a}, we present the second one, based on ``an observation,
made to us by Mrs. Turan that $(\ldots)$ one of the integers $(\ldots)$ occurs only once''.) 
They proved further that $N_s(n)\ge (s^2-4s+3)n-C(s)$ 
($s>3$ is odd) and $N_s(n)\ge (s^2-5s+8)n-C(s)$ ($s\ge 4$ is even). Modifying these 
constructions, they obtained the bound $N_4(n)>5n-c$.

\noindent
{\bf Davenport's results.} In the posthumously published paper \cite{dave} (edited by 
Schinzel), Davenport improved (\ref{DSN5}) to $N_4(n)\ll n\log n/\log\log n$.
He noted that the ratio $N_4(n)/n$ must have a finite limit or it must go to $+\infty$, 
because $N_4(m+n)\ge N_5(m)+N_5(n)$ for every $m$ and $n$ (easy to see from the definition). 
He proved more specificly that 
$$
\lim_{n\rightarrow\infty}{N_4(n)\over n}\ge 8.
$$
Davenport's third result is the inequality 
$N_4(lm+1)\ge 6lm-m-5l+2$ ($l,m\in\N$), 
which was ``found in collaboration with J. H. Conway''. It implies that 
$N_4(n)\ge 5n-8$, with the strict inequality for odd $n\ge 13$ and even $n\ge 18$.
The note added in proof (apparently by Schinzel) says that Z. Ko{\l}ba proved that  
$N_4(2m)\ge 11m-13$. 

\noindent
{\bf The results of Roselle and Stanton.} (Recall that $N_s(n)=\f_{s-1}(n)$.) Roselle and 
Stanton proved in \cite{stan_rose} 
that $N_s(3)=3s-4$ (for even $s>3$) and $N_s(3)=3s-5$ (for odd $s>3$). In \cite{rose_stan71}
they proved that $N_s(4)=6s-13$ (for even $s>4$) and $N_s(4)=6s-14$ (for odd $s>4$). Finally, 
in \cite{rose_stan70} they proved that $N_s(5)=10s-27$ (for even $s>6$; the case 
$s=6$ contains an error) and 
$N_s(5)=10s-29$ (for odd $s>5$). In \cite{rose_stan70} also the bound $N_4(n)\ge 5n-8$ 
is proved ($n\ge 4$). In \cite{rose_stan71} Roselle and Stanton 
gave the general bound ($s>n$) 
\begin{equation}
N_s(n)\ge\left\{
\begin{array}{ll}
{n\choose 2}s-F(n)&\mbox{$s$ is even}\\
 & \\
{n\choose 2}s-F(n)-\lfloor{n-1\over 2}\rfloor&\mbox{$s$ is odd}
\end{array}
\right\}\label{rose_stan}
\end{equation}
where $F(n)=(2n^3+9n^2-32n+9)/12$ for odd $n\ge 3$ and 
$F(n)=(2n^3+9n^2-32n+12)/12$ for even $n$. For $n=3,4,$ and $5$ 
these bounds are sharp. 

If $n=o(s)$, the bounds (\ref{DStrivi}) and (\ref{rose_stan}) yield the 
asymptotics $N_s(n)=(1+o(1)){n\choose 2}s$. But what if $n$ is bigger? 

\noindent
{\bf Problem 1.} The bounds (\ref{DStrivi}) and (\ref{rose_stan}) 
give 
$$
{n^3(1+o(1))\over 3}<N_n(n)<{n^3(1+o(1))\over 2}.
$$
What is the precise asymptotics of $N_n(n)$? 
\kduk

\noindent
{\bf Further results.} 
Peterkin \cite{pete} determined by computer the value $N_5(6)=29$ and 
found all 35 longest (normal) 6-DS sequences, corrected the value 
$N_6(5)$ of Roselle and Stanton to 34 (they had the incorrect value 33), and
proved that $N_5(n)\ge 7n-13$ ($n>5$) and $N_6(n)\ge 13n-32$ ($n>5$). 

Burkowski and Ecklund \cite{burk_eckl} found for small values of $n,r$, and $d$ the 
maximum lengths of $d$-DS sequences over $n$ symbols, in which no symbol 
appears more than $r$ times. MR reviewer N. G. de Bruijn wrote on 
\cite{burk_eckl}: 
``$\ldots$ The following question was raised by D. J. Newman: Is there a 
word $S$ in some $\Phi\sb {n,4}$ [5-DS sequences over $n$ symbols] 
that contains each symbol at least 5 times? 
The authors give an affirmative answer (but the proof seems to be 
incomplete). $\ldots$''

Dobson and Macdonald \cite{dobs_macd} obtained a slight improvement of 
(\ref{rose_stan}). We state one of their bounds: if $n$ and $r$ are even,  
then $N_{n+r}(n)\ge {1\over 6}(2n^3+3n^2(r-2)-2n(3r-5)+6r)$. For 
$n>2r+2$ this improves (\ref{rose_stan}). Their other bounds are similar.

Rennie and Dobson \cite{renn_dobs} derived the inequality 
\begin{equation}\label{renn_dobs}
\left(n-2+{1\over s-3}\right)\cdot N_s(n)\le n\cdot N_s(n-1)+{2n-s+2\over s-3}.
\end{equation}
From it they could obtain good upper bounds on $N_s(n)$ for small values
of $s$ and $n$.

The next table, taken from Rennie and Dobson \cite{renn_dobs}, gives specific bounds 
for $N_s(n)$ in the range $5\le s\le 12$ and $5\le n\le 12$. The upper bound
is obtained from (\ref{renn_dobs}). The lower bound is the larger of the lower bounds given by Dobson and Macdonald or (shown in italic) by Roselle and Stanton in (\ref{rose_stan}).

\vskip 10pt
\centerline{\begin{tabular}{|c|c|c|c|c|}
\hline
$s$ & 5 & 6 & 7 & 8  \\\hline
$n$  & & & &  \\\hline
5  & 22 & 34 & 41 & 53 \\\hline
6 & 29 & 46--47 & 56--58 & 72--76 \\\hline
7 & 36--37 & 59--62 & 72--77 & 96--102 \\\hline
8 & 43--46 & 72--78 & 89--99 & 120--131 \\\hline
9 & 50--56 & 85--96 & 106--123 & 145--164 \\\hline
10 & 57--66 & 98--115 & 123--149 & 170--200\\\hline
11 & 64--77 & 111--136 & 140--177 & 195--239  \\\hline
12 & 71--89 & 124--158 & 157--207 & 220--281 \\\hline
\end{tabular}}
\vskip 10pt

\centerline{\begin{tabular}{|c|c|c|c|c|}
\hline
$s$ & 9 & 10 & 11 & 12 \\\hline
$n$  & & & & \\\hline
5 & 61 & 73 & 81 & 93 \\\hline
6 & {\it 85}--88 & {\it 102}--105 & {\it 115}--117 & {\it 132}--135\\\hline
7  & 110--119 & 134--143 & {\it 152}--159 & {\it 176}--184 \\\hline
8  &140--154 & 170--186 & 192--207 & {\it 223}--240 \\\hline
9  & 170--193 & 210--234 & 236--261 & 276--303 \\\hline
10 & 201--236 & 250--287 & 284--321 & 332--373 \\\hline
11 & 232--283 & 291--345 & 332--387 & 392--450 \\\hline
12 & 263--334 & 332--408 & 381--458 & 452--534 \\\hline
\end{tabular}}


Mills \cite{mill73} proved the inequalities $N_4(k^2+5-j)\ge 6k^2-2k+16-6j$ 
and $N_4(k^2+k+5-j)\ge 6k^2+4k+15-6j$, where $0\le j<k$. In \cite{mill73}
and \cite{mill76} he determined the values of $N_4(n)$ for $n\le 21$: 

\vskip 10pt
\centerline{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\\hline
$N_4(n)$ &1 & 4 & 8 & 12 & 17 & 22 & 27 & 32 & 37 & 42 & 47 & 53 & 58 & 64 \\\hline
\end{tabular}}

\vskip 10pt
\centerline{\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$n$ & 15 & 16 & 17 & 18 & 19 & 20 & 21\\\hline
$N_4(n)$ & 69 & 75 & 81 & 86 & 92 & 98 & 104 \\\hline
\end{tabular}}
 
\noindent
The values of $N_4(n)$ form the sequence A002004 of the database \cite{sloa}.
The formula $N_4(n)=5n-8$, valid for $4\le n\le 11$, breaks down later, as
noted already by Davenport.

\noindent
{\bf Szemer\'edi's general bound.} In 1974, Szemer\'edi \cite{szem} published a remarkable result 
with a difficult proof: for $n\to\infty$, 
\begin{equation}\label{szem}
N_s(n)\ll_s n\log^* n.
\end{equation} 
Here $\log^* n$ is the smallest integer $k>0$ such that $e_k>n$, where 
$e_1={\rm e}=2.71828\dots$ and $e_{i+1}={\rm e}^{e_i}$. (Nothing changes if we replace 
${\rm e}$ by any other base $b>1$.) The key part of Szemer\'edi's proof is a decomposition 
lemma, which is based on the doubly exponential upper bound in a particular case of 
the classical Ramsey theorem (triples colored with two colors). The bound (\ref{szem}) 
improved considerably both (\ref{DSNs}) and (\ref{DSN5}). 

Mills' article \cite{mill76} and Stanton and Dirksen's survey \cite{stan_dirk}, both published 
in 1976, mark the end of the early investigations of $N_s(n)=\f_{s-1}(n)$. DS sequences 
were dormant for the next 10 years.

\vskip 30pt
\section*{\normalsize 3. Superlinear Growth}

{\bf New bounds on $\mathbf{\f_3(n)}$: enigma solved.} In the middle of 1980s,  
the importance of DS sequences for combinatorial 
and computational geometry was discovered, first by Atallah \cite{atal}. 
Or rather rediscovered, since the geometric motivation was in the background 
from the very beginning, only computational geometry did not exist 
in the times of \cite{dave_schi65a}. The functions 
$\f_s(n)$, $s>2$, remained mysterious. Despite the effort invested 
in the proofs of (\ref{DSNs}) and (\ref{szem}), the $O(n)$ upper bounds were not in sight and  
the correct orders of growth of $\f_s(n)$ were unclear. 
Stanton and Dirksen conjectured in \cite{stan_dirk} that $\f_3(n)/n\to\infty$. 

\begin{figure}
\unitlength1mm
\begin{picture}(100,40)(0,0)
\put(20,0){\line(0,1){40}}
\put(20,0){\line(1,0){100}}
\put(60,7){\line(-1,1){30}}
\put(40,19){\line(1,0){55}}
\put(52,9){\line(3,1){55}}
\put(33,37){$S_2$}
\put(62,21){$S_1$}
\put(102,29){$S_3$}
\thicklines
\put(40,27.17){\line(-1,1){10}}
\put(40,26.83){\line(-1,1){10}}

\put(40,19.15){\line(1,0){8}}
\put(40,18.85){\line(1,0){8}}

\put(48,19.17){\line(1,-1){4}}
\put(48,18.83){\line(1,-1){4}}

\put(52,9.15){\line(3,1){4.5}}
\put(52,8.85){\line(3,1){4.5}}

\put(60,7.17){\line(-1,1){3.515}}
\put(60,6.83){\line(-1,1){3.515}}

\put(60,11.82){\line(3,1){22}}
\put(60,11.52){\line(3,1){22}}

\put(82,19.15){\line(1,0){13}}
\put(82,18.85){\line(1,0){13}}

\put(95,23.45){\line(3,1){12}}
\put(95,23.15){\line(3,1){12}}
{\footnotesize 
\put(32,2){$2$}
\put(42,2){$1$}
\put(49,2){$2$}
\put(53.5,2){$3$}
\put(57,2){$2$}
\put(70,2){$3$}
\put(88,2){$1$}
\put(102,2){$3$}
}
\end{picture}
\caption{The lower envelope of plane segments.}
\end{figure}

\noindent
{\bf Example 3 (\cite{shar_agar}).} 
We illustrate the role of DS sequences in combinatorial geometry by a 
classical example, which is very similar to the problem in \cite{dave_schi65a}
(we discussed it in the beginning of Section 2) but is more recent. Let 
$S_1,S_2,\ldots,S_n$ be $n$ straight segments
in the plane, none of them vertical and no two of them overlapping. We regard 
them as graphs of $n$ real functions $f_1,\dots,f_n$ which are now defined only on intervals.  
We consider the pointwise minimum function $f=\min_i f_i$. As before, $f$ and $f_i$ 
define a unique splitting of $\R$ into the intervals $I_1,I_2,\ldots,I_l$. 
The only difference is that now $f$ is undefined on some of the intervals, certainly on 
$I_1$ and $I_l$. Again, for every $i=1,2,\dots,l$ we write down the index $j$ of the segment $S_j$ 
that forms in $I_i$ the graph of $f$; the intervals $I_i$ with undefined $f$ are ignored. We
obtain a sequence $u$ over $\{1,2,\ldots,n\}$, $|u|\le l-2$. In Figure 1, $n=3$, $l=10$, 
and $u=21232313$. The graph of $f$ is the {\em lower 
envelope} of the system $\{S_1,\ldots,S_n\}$, $u$ is the {\em minimazing sequence\/}, 
and the length $|u|$ is the {\em complexity\/} of the lower envelope. The fact that 
every two (nonoverlapping) plane segments intersect in at most one point implies
that $u$ is a 5-DS sequence. Thus the complexity of the lower enevelope has 
the bound $|u|\le\f_3(n)$.
\kduk

\noindent
Another geometric connection was recently studied by Alon and Onn 
\cite{alon_onn}. Consider a set $X$ of $n$ points lying on the moment 
curve in $\R^d$. The partitions of $X$ into $p$ parts with mutually disjoint
convex hulls then correspond to the $(d+2)$-DS sequences (immediate repetitions 
are now allowed) which are over $\{1,2,\ldots,p\}$ and are of length $n$. 
See also Aviran and Onn \cite{avir_onn}. 

New light on $\f_3(n)$ was shed by Hart and Sharir in 1986 in their 
breakthrough article \cite{hart_shar}. They proved that
\begin{equation}\label{hart_shar}
n\alpha(n)\ll \f_3(n)\ll n\alpha(n),
\end{equation}
where $\alpha(n)$ is the inverse Ackermann function, which is defined 
as follows. The Ackermann function $A(n)$ is the diagonal function $A(n)=F_n(n)$ of the 
hierarchy of functions $F_i: \N\rightarrow\N$, $i\in\N$, where
$F_1(n)=2n$ and  
$F_{i+1}(n)=F_i(F_i(\ldots F_i(1)\ldots ))$ with $n$ iterations of $F_i$.
The inverse Ackermann function is then defined by $\alpha(n)=\min\{m\in\N:\ A(m)\ge n\}$. 
Alternative definitions of the hierarchy and of $A(n)$ can be found in the literature, but these 
hardly affect the values of $\alpha(n)$. 
The function $\alpha(n)$ grows to infinity much more slowly than $\log^* n$. 
(For further information on the role of very fast and very slow functions in combinatorics 
and computer science, see Loebl and 
Ne\v set\v ril \cite{loeb_nese}.) The asymptotics  
(\ref{hart_shar}) was not only an improvement upon (\ref{szem}) for $s=4$, but 
it settled almost completely the 20 years old riddle of Davenport and Schinzel 
about the growth rate of $\f_3(n)$. 

In \cite{hart_shar}, Hart and Sharir first translated 5-DS sequences to 
certain tree objects called (generalized path) compression schemes; these are motivated by data 
structures algorithms. They derived the new upper
and lower bounds for the compression schemes, and then translated the bounds back to 
5-DS sequences. Their proofs were inspired by some ideas and techniques of Tarjan \cite{tarj} who 
pioneered applications of $\alpha(n)$ in  computer science. 
This method gave bounds for both 5-DS sequences and 
compression schemes, but it was technically complicated. Soon it turned out 
that the translation is not really necessary and that one can work directly 
with DS sequences. This approach is adopted in all subsequent works. 
(For information on compression schemes and their relation to 5-DS sequences, see  
the book of Sharir and Agarwal \cite{shar_agar}.)
Komj\'ath \cite{komj} proved the 
superlinear lower bound $\f_3(n)\gg n\alpha(n)$ by a construction purely in 
terms of sequences. Wiernik and Sharir \cite{wier_shar} gave a simpler 
construction and, more importantly and remarkably, they proved that 
the 5-DS sequences produced by it can 
be realized as minimazing sequences of appropriate systems of
plane segments. Thus there do exist systems of $n$ plane segments 
whose lower envelopes have $\gg n\alpha(n)$ portions. We come to 
the natural but open

\noindent
{\bf Problem 2.} 
Can every 5-DS sequence be realized as the minimazing sequence of a system of 
plane segments? 
\kduk


\noindent
In \cite{shar_agar}, the authors express their opinion that the correct answer is negative. 
It is easy to realize every 5-DS sequence as the minimazing sequence
of a system of {\em pseudosegments\/}. These are graphs of 
continuous functions defined on intervals, each two of them 
intersecting in at most one point.

\noindent
{\bf Example 4 (\cite{wier_shar, shar_agar}).} Following \cite{shar_agar}, 
we decribe the construction of \cite{wier_shar} proving $\f_3(n)\gg n\alpha(n)$.
One defines, by double induction, 
a two-dimensional array $S: \N\times\N\rightarrow A^*$ of sequences. Before giving the precise 
inductive definition, we have to say that the 
sequences $S(k,m)$ have no immediate repetition and are of the form 
$$
S(k,m)=u_1v_1u_2v_2\ldots u_Nv_N,
$$
where every $u_i$ is a sequence of length $m$ containing $m$ distinct 
symbols, and $v_1,\dots,v_N$ are possibly empty intermediate sequences. 
The sequences $u_i$ are called {\em fans\/} or $m$-{\em fans\/} and $v_i$ 
are called {\em separating sequences\/}. The key property of fans 
is this: every symbol of $S(k,m)$ appears 
in exactly one fan and this is its leftmost appearance in $S(k,m)$.   
The number $N=N(k,m)$ will be defined inductively in the construction.
The sequences $u_i$ and $v_i$ depend on $k$ and $m$ as well, of course, but to 
avoid cumbersome notation we do not mark this dependence.

The first row $k=1$ consists of the sequences $S(1,m)=u_1=12\ldots m$, and 
$N(1,m)=1$. If the row $k\ge 1$ is already defined, we define $S(k+1,1)$ to be 
identical with $S(k,2)$, except that every 2-fan in $S(k,2)$ is now regarded as
two neighbouring 1-fans in $S(k+1,1)$. Thus $N(k+1,1)=2N(k,2)$. 

Let now the whole row $k\ge 1$ be already defined, as well as the sequences in the row 
$k+1$ up to the column $m\ge 1$. Let the same hold for the values of $N(x,y)$. We define 
$S(k+1,m+1)$ and $N(k+1,m+1)$. We denote $w_0=S(k,N(k+1,m))$. We set 
$M=N(k,N(k+1,m))$ and create $M$ copies $w_1, w_2, \ldots, w_M$ 
of the sequence $S(k+1,m)$, renaming the symbols so that no two of 
the $M+1$ sequences $w_0,w_1,\ldots,w_M$ share a symbol. We have as many 
copies of $S(k+1,m)$ as fans in $w_0$, and any fan in $w_0$ has as many 
elements as $S(k+1,m)$ has fans.
By duplicating the last term in every fan in every $w_i,i=0,1,\ldots,M$, we create sequences 
$w'_i$. We set
$$
S(k+1,m+1)=w_1'w_2'\ldots w_M'+w_0'=w_1^*z_1w_2^*z_2\ldots w_M^*z_M,
$$
where the $+$ indicates the following interleaving of $w_1'w_2'\ldots w_M'$ and $w_0'$, which 
preserves the order of terms in both sequences. The 
elements of the first $N(k+1,m)$-fan of $w_0'$ are used to separate the twins on the ends of 
the $N(k+1,m)$ $m$-fans of $w_1'$; this yields $w_1^*$. The sequence $z_1$ consists of the last 
term of the first fan of $w_0'$, followed by the first separating sequence of $w_0'$. In the same 
way we use the second fan of $w_0'$ to separate the twins in $w_2'$, which yields $w_2^*$, and 
so on.  The resulting sequence $S(k+1,m+1)$ has no immediate repetition and its
$(m+1)$-fans are the old $m$-fans in $w_1',\ldots,w_M'$, each enlarged by one term coming   
from the fans of $w_0'$. Thus 
$$
N(k+1,m+1)=N(k+1,m)\cdot N(k,N(k+1,m)).
$$
One can easily check that the key property of fans is preserved during 
this step.

Note that $S(k,m)$ uses exactly $m\cdot N(k,m)$ symbols. Using the key property 
of fans, it is easy to show by double induction that every $S(k,m)$ is a 5-DS sequence. 
One can define, 
for details consult \cite{wier_shar} or \cite{shar_agar}, 
a sequence of numbers $1\le m_1<m_2<\cdots$ such that, 
writing $n_k$ for $\|S(k,m_k)\|=m_k\cdot N(k,m_k)$, the inequality $|S(k,m_k)|\ge n_k\alpha(n_k)-3n_k$ 
holds. (We owe the superlinear growth of $|S(k,m_k)|$ to the duplications.) Hence, for every $k\in\N$, 
\begin{equation}\label{konst1}
\f_3(n_k)\ge n_k\alpha(n_k)-3n_k.
\end{equation}
A simple interpolation argument of 
\cite{shar_agar} shows that 
$$
\f_3(n)\ge {\textstyle{1\over 2}}n\alpha(n)-2n
$$
holds for all $n\in\N$.
\kduk

\noindent
Hart and Sharir \cite{hart_shar} proved the lower bound in (\ref{hart_shar}) 
with the constant ${1\over 4}+o(1)$. The constants achieved in the upper bound 
were $52+o(1)$ in \cite{hart_shar} and $68+o(1)$ in \cite{shar_agar}. (The objective of these works was 
not really to obtain the best constants.) Klazar 
\cite{klaz_phd} obtained the constant $4+o(1)$ and in \cite{klaz99} he
proved that
\begin{equation}\label{konst2}
\f_3(n)<2n\alpha(n)+O(n\sqrt{\alpha(n)}). 
\end{equation}

\noindent
{\bf Problem 3.} 
Does the limit
$$
\lim_{n\rightarrow\infty}{\f_3(n)\over n\alpha(n)}
$$ 
exist? 
\kduk


\noindent
If it exists, (\ref{konst1}) and (\ref{konst2}) show that it lies in the 
interval $[1,2]$. 

We answer in positive the question from the MR review of Burkowski and 
Ecklund \cite{burk_eckl} that we quoted in the previous section. We know
that $\f_3(n)>cn$ for large $n$ for every constant $c>0$. We deduce from it 
that for every $k\in\N$ there exists a 5-DS sequence $v$ in which every 
symbol appears at least $k$ times. Let $v\in\DS_5$ be such that 
$|v|\ge (k+1)\|v\|$ and $\|v\|$ is as small as possible. If some symbol $a\in S(v)$ 
occurs in $v$ less than $k$ times, we eliminate all $a$-occurrences by 
deleting at most $k-1+2=k+1$ terms (as in the third proof in Example 2) and obtain a sequence 
$w\in\DS_5$ such that $|w|\ge (k+1)\|w\|$ and $\|w\|\le \|v\|-1$. But $w$  
contradicts the minimality of $\|v\|$. Therefore $v$ has the stated property.
Note that for $k=5$ the sequence $v$ must use at least 22 symbols, because 
Mills' table in Section 2 shows that $\f_3(n)<5n$ for $n<22$.

\noindent
{\bf Bounds on $\mathbf{\f_s(n)}$ for $\mathbf{s>3}$.} The next obvious step 
was to extend the new techniques to $\f_s(n)$ for 
$s>3$. Sharir in \cite{shar87} proved the upper bound
$$
\f_s(n)\ll n\alpha(n)^{c_s\alpha(n)^{s-3}}
$$
and in \cite{shar88} the lower bound
$$
\f_{2s-1}(n)\gg_s n\alpha(n)^{s-1}.
$$
Since $\f_{2s}(n)\ge\f_{2s-1}(n)$, this gives lower bounds for every $\f_s(n)$. 

This line of research culminated in 1989 in the long and 
technical work of Agarwal, Sharir and Shor \cite{agar_shar_shor}. For $s=4$ they proved the estimate
\begin{equation}\label{N6}
n2^{\alpha(n)}\ll \f_4(n)\ll n2^{\alpha(n)}.
\end{equation}
For $s>4$ they obtained strong bounds as well but they 
could not match completely the precision of (\ref{hart_shar}) and 
(\ref{N6}). Their lower bound says that 
\begin{equation}\label{N2sdol}
\f_{2s}(n)\gg_s n2^{c_s\alpha(n)^{s-1}+Q_s(n)},
\end{equation}
where $c_s=1/(s-1)!$ and $Q_s(n)$ is a polynomial in $\alpha(n)$ of degree 
at most $s-2$. As for the upper bound, they proved that 
\begin{equation}\label{N2shor}
\f_{2s+1}(n)\le n2^{\alpha(n)^{s-1}\log(\alpha(n))+C_{2s+1}(n)}\ \mbox{ and }\ 
\f_{2s}(n)\le n2^{\alpha(n)^{s-1}+C_{2s}(n)}, 
\end{equation}
where $C_k(n)$ equals 6 and 11 for $k$ equal to 3 and 4, respectively,  
$C_{2s+1}(n)=O(\alpha(n)^{s-1})$, and 
$C_{2s}(n)=O(\alpha(n)^{s-2}\log(\alpha(n)))$. We remark that in these 
bounds (and the whole \cite{agar_shar_shor}) $\log n$ denotes the 
{\em binary logarithm\/} with base 2, whereas in 
Example 2 and (\ref{DSN5}) we have the natural logarithm. 

Let us summarize the current best bounds on 
$\f_s(n)$. Cases $s\le 1$ are trivial. The formula $\f_2(n)=2n-1$ was proved by Davenport 
and Schinzel in \cite{dave_schi65a}, see Example 2. The functions $\f_3(n)$ and $\f_4(n)$ 
grow, up to multiplicative constants, as $n\alpha(n)$ and $n2^{\alpha(n)}$, 
respectively, as proved by Hart and Sharir \cite{hart_shar} and Agarwal, Sharir 
and Shor \cite{agar_shar_shor}. The bounds (\ref{N2sdol}) and (\ref{N2shor}) 
of \cite{agar_shar_shor} estimate $\f_s(n)$ for $s>4$.

\noindent
{\bf Problem 4.} 
What are the exact speeds of growth of $\f_5(n)$ and $\f_6(n)$? And of the other $\f_s(n)$ for 
$s>4$?
\kduk


\noindent
By (\ref{N2sdol}) and (\ref{N2shor}), 
$$
n2^{\alpha(n)}\ll \f_5(n)\ll n\alpha(n)^{(1+o(1))\alpha(n)}
$$ 
and 
$$
n2^{(1+o(1))\alpha(n)^2/2}\ll \f_6(n)\ll n2^{(1+o(1))\alpha(n)^2}.
$$

Bounds on $\f_s(n)$ found many applications in problems and 
algorithms of computational geometry. We suggest 
to the interested reader 
works \cite{agar_shar} and \cite{shar_agar} of Agarwal and Sharir for 
detailed information and many references. We remark that the 
``Web of Science'' \cite{webs} listed in the middle of the year 2002 more than 110 citations of 
\cite{hart_shar}, which documents the big impact of this work.

\vskip 30pt
\section*{\normalsize 4. A Generalization of $\f_s(n)$ to Any Forbidden
Subsequence}

{\bf A containment of sequences.} The extremal function $\f_s(n)$ corresponds to the (forbidden) 
alternating sequence $ababa\dots$ of length $s+2$. Now we associate with every sequence, not just with 
the alternating ones, an extremal function. For this we need to define a general  
containment of sequences.

Recall that our sequences are finite and are over $A$, where $A$ is an infinite alphabet such that 
$A\supset\N$ and $a,b,c,d,\ldots$ lie in $A$. Recall that two sequences 
$u=a_1a_2\ldots a_l$ and $v=b_1b_2\ldots b_l$ of the same length are 
isomorphic, if for some injection $f: A\rightarrow A$ we have $a_i=f(b_i)$, 
$i=1,2,\ldots,l$. This is an equivalence relation and each class of 
isomorphic sequences contains exactly one normal sequence (see the definition
before Example 1). We shall refer to elements of $A$ by the leters $a,b,c,d,\ldots$ 
and to sequences over $A$ by the letters $u,v,w,\ldots$.

Let $u$ and $v$ be two sequences. We say that $u$ {\em contains\/} $v$ 
and write $u\supset v$, if $u$ has a subsequence isomorphic to $v$. 
For example, $u=a_1a_2\ldots a_l$ contains $abccba$ if and only if there are six indices 
$1\le i_1<\cdots <i_6\le l$ such that $a_{i_1}=a_{i_6}$, 
$a_{i_2}=a_{i_5}$, $a_{i_3}=a_{i_4}$, 
and these are the only equality relations among $a_{i_1}, \ldots, a_{i_6}$.
The containment is a nonstrict partial order on classes
of isomorphic sequences. If $u$ does not contain $v$, we say that $u$ is $v$-{\em free\/}.

\noindent
{\bf The extremal function $\mathbf{Ex(v,n)}$.} A sequence $u=a_1a_2\ldots a_l$ is called 
$k$-{\em sparse\/} if $a_i=a_j,i>j,$ implies $i-j\ge k$. In other words, 
 in every interval in $u$ of length at most $k$ all terms are 
distinct. For $k=2$ we get the condition 1 from the definition of DS sequences.
Recall that $|u|$ is the length of a sequence $u$ and $\|u\|$ is the number of 
symbols used in $u$. 

Let $v$ be any sequence and $n\in\N$. We associate with $v$ the extremal function
\begin{equation}\label{obextrfcedef}
\ex(v,n)=\max\{|u|:\ u\not\supset v\;\&\;
\mbox{$u$ is $\|v\|$-sparse}\;\&\;\|u\|\le n\}.
\end{equation}
It extends $\f_s(n)$: if $\al_s$ denotes the alternating 
sequence $abab\ldots$ of length $s$, then $\f_s(n)=\ex(\al_{s+2},n)$. The condition that 
$u$ is $\|v\|$-sparse is necessary to ensure that $\ex(v,n)<\infty$; note that 
$12\dots k12\dots k12\dots$ is an infinite sequence that is $k$-sparse and contains 
no $u$ with $\|u\|\ge k+1$. 

$\ex(v,n)$ was introduced, albeit in a different notation, in 1992 by 
Adamec, Klazar and Valtr \cite{adam_klaz_valt}. 
$\ex(v,n)$ is always well defined because a modification of the
argument proving (\ref{DStrivi}) gives
\begin{equation}\label{obecnytrivi}
\ex(v,n)< {\textstyle \|v\|\cdot({n\choose \|v\|}(|v|-1)+1)}\ll_v n^{\|v\|}.
\end{equation}
Before proceeding to further general properties of $\ex(v,n)$, we derive two specific bounds 
to convey to the reader the flavour of arguments used to handle $\ex(v,n)$, and 
we present a historical remark. 

\noindent
{\bf Example 5 (\cite{klaz_phd}).}
We determine $\ex(abba,n)$ exactly and then prove a linear upper bound on 
$\ex(a_1a_2\ldots a_ka_1a_2\ldots a_k,n)$.

We prove that, for all $n\in\N$,  
$$
\ex(abba,n)=3n-2
$$
(cf. the next historical remark). 
The sequences 
$$
u=1\;2\;1\;2\;3\;2\;3\;4\;3\;4\;5\;4\;\ldots (n-2)\;(n-1)\;(n-2)\;(n-1)\;n\;(n-1)\;n
$$ 
show that $\ex(abba,n)\ge 3n-2$. We prove the opposite inequality.
For $n=1$ it is true. For 
$n>1$ we use induction on $n$. Let $u=a_1a_2\ldots a_l$ be 2-sparse, 
$abba$-free, and $\|u\|\le n$. Suppose first that some symbol $a\in S(u)$ appears 
in $u$ at least four times. We select four indices 
$1\le i_1<\cdots<i_4\le l$ such that $a_{i_1}=a_{i_2}=a_{i_3}=a_{i_4}=a$ and 
$a_j\neq a$ for $j\in [i_2+1,i_3-1]$. 
A moment of thought reveals that the symbol $b=a_{i_2+1}$ is distinct from $a$ 
and appears in $u$ only once. Deleting $a_{i_2+1}$ and also $a_{i_2}$ if 
$i_3=i_2+2$, we decrease $\|u\|$ by one and obtain by induction the even 
stronger bound $|u|\le 3(n-1)-2+2=3n-3$. Thus we may assume that every symbol appears 
in $u$ at most three times, which gives $|u|\le 3n$. If $a=a_1$ 
appears in $u$ three times, we can still apply the deletion argument 
to $b=a_2$ and conclude that $|u|\le 3n-3$. The same if $a=a_l$ appears in $u$ three times. 
If $a_1=a_l=a$, only $a$ may be repeated in $u$ and $|u|\le 2n-1$. Thus we may assume in addition 
that $a_1\neq a_l$ and both 
symbols $a_1$ and $a_l$ appear in $u$ at most twice. We conclude that $|u|\le 3n-2$.

Let $v_k=a_1a_2\ldots a_ka_1a_2\ldots a_k$ where $a_1,\dots,a_k$ are $k$ distinct 
symbols from $A$. We prove that 
$$
\ex(v_k,n)\ll_k n.
$$
Notice that $\ex(v_1,n)=n$ and $\ex(v_2,n)=\f_2(n)=2n-1$. Let $k,n\in\N$ 
and $k$ be fixed. We set $K=(k-1)^4+1$ and $L=\ex(v_k,K-1)+1$. The number 
$L$ exists by the rough general bound (\ref{obecnytrivi}). Let $u$ be a 
$k$-sparse sequence ($\|v_k\|=k$) with $\|u\|\le n$. We assume that 
$|u|\ge (2n+1)L$ and show that it implies $u\supset v_k$. We 
split $u$ into $2n+1$ disjoint intervals, each of length at least $L$. One of 
these intervals, let us call it $I$, contains neither the first nor the last 
appearance of any symbol $a\in S(u)$ because these are only at most $2n$ in number. 
If $\|I\|<K$, the definitions of $L$ and $|I|$ imply $I\supset v_k$ and we are done. 
So $\|I\|=|S(I)|\ge K$. By the property 
of $I$, every $a\in S(I)$ appears before $I$, in $I$, and after $I$. 
Applying twice 
the classical Erd\H os--Szekeres lemma, which says that every sequence of 
$(k-1)^2+1$ numbers contains a monotone subsequence of length $k$, we see
that there is a subset $Y\subset S(I)$ of $k$ elements, 
$Y=\{y_1,y_2,\ldots,y_k\}$, such that $y_1,y_2,\ldots,y_k$ appear before $I$ 
in this order, in $I$ in this or in the opposite oder, and after $I$ also 
in this or in the opposite order. But then two of the three orders agree, which gives 
$u\supset v_k$. Thus $|u|\ge (2n+1)L$ always forces 
the containment $u\supset v_k$. We conclude that $\ex(v_k,n)<(2n+1)L$.
\kduk


\noindent
{\bf A historical remark.} The author of this survey wondered from time to time why for so long 
(until the apperance of \cite{adam_klaz_valt}\footnote{
I learned about DS sequences in the fall of 1988 in the Prague combinatorial seminar that was 
then led by J. Ne\v set\v ril and J. Matou\v sek. They suggested to us, a group of undergraduate 
students of Charles University, to investigate generalizations of $\f_s(n)$. This 
eventually resulted in \cite{adam_klaz_valt} and some other works. 
}) 
nobody tried to generalize $\f_s(n)$ and everybody 
followed so faithfully the original formulation of the problem that forbids 
only alternating subsequences. The extension (\ref{obextrfcedef}) of 
(\ref{Ns}) is relatively straightforward and Example 5 shows that with a modest effort one can obtain  
for $\ex(v,n)$ results of some interest. On the other hand, to 
prove (\ref{DSNs}) or (\ref{hart_shar}), say, is difficult. Of course, 
retrospect views are often dubious. We will not delve into psychological speculations but 
we want to present a little historical discovery. 

Surprisingly, revisionists appeared already in the very beginning and 
it was 
nobody else but Davenport 
and Schinzel who in 1965, besides the famous \cite{dave_schi65a}, published also 
\cite{dave_schi65b} hinting on a generalization of $\f_s(n)$. The latter 
forgotten note is missing in 
all bibliographies of DS sequences we know of 
(\cite{agar_shar}, \cite[problem E20]{guy}, \cite{klaz_phd}, \cite{shar_agar}, \cite{stan_dirk}, $\ldots$) and probably is not refered to anywhere. It 
is accesible in Davenport \cite{davecoll} where we found it. 
Davenport and Schinzel derive in \cite{dave_schi65b} an inequality on 
lentghs of subsequences of a 
2-sparse sequence. In the last paragraph they say:

\begin{quote}
The inequality is of some interest in connection with sequences which, in 
addition to having no immediate repetition, satisfy some prescribed 
``hereditary'' conditions, that is, some condition which if valid for a sequence
is necessarily valid for every subsequence. Take as an illustration 
the condition that the sequence contains no subsequence
$$
\ldots,\ a,\ldots,\ b,\ldots,\ b,\ldots,\ a,\ \ldots\ (b\neq a)\ .
$$
Then the length of any such a sequence is at most $2n(n-1)$; for we can apply 
(1) [they refer to the inequality] with $m=2$, in which case $M\le 4$. 
(Actually in this particular case the maximum length is $3n-2$.)
\end{quote}
Nobody followed the hint then.

\noindent
{\bf An almost linear bound on $\mathbf{Ex(v,n)}$.} As for strengthening of (\ref{obecnytrivi}), 
Klazar \cite{klaz92} showed
by a simple combinatorial argument that $\ex(v,n)\ll_v n^2$. The main 
result of \cite{klaz92} says that
if $v$ is a sequence with $\|v\|=k\ge 2$ and $|v|=l\ge 5$, then for every $n\in\N$
\begin{equation}\label{muj}
\ex(v,n)\le n\cdot k2^{l-3}\cdot (10k)^{2\alpha(n)^{l-4}+8\alpha(n)^{l-5}}.
\end{equation}
If $k=1$ or $l\le 4$, it is easy to show that $\ex(v,n)\ll_v n$. This 
general bound was derived by adapting the techniques from Sharir 
\cite{shar87}.

\noindent
{\bf A slight generalization: $\mathbf{Ex(v,k,n)}$.} One can investigate the more general 
extremal function $\ex(v,k,n)$, which is defined 
as the maximum length of a $v$-free and $k$-sparse sequence $u$ with 
$\|u\|\le n$. It is clear that $\ex(v,\|v\|,n)=\ex(v,n)$ and $\ex(v,k,n)=\infty$  
whenever $k<\|v\|$ and $n\ge k$ --- the infinite sequence $12\dots k12\dots k12\dots$ is $k$-sparse 
and does not contain 
$v$. Thus one has to have $k\ge \|v\|$. For the asymptotics it brings 
nothing new because, as proved in \cite{adam_klaz_valt}, 
\begin{equation}\label{exvkn}
\ex(v,n)\ll_{v,k} \ex(v,k,n)\le\ex(v,n)
\end{equation}
for every sequence $v$ and every $k\ge \|v\|$; the latter inequality is trivial.
As for the precise values, in Klazar \cite{klaz96b} it was proved that for 
$n\ge k\ge 2$,
$$
\ex(abab,k,n)=2n-k+1\ \mbox{ and }\ \ex(abba,k,n)=2n+
\left\lfloor{n-1\over k-1}\right\rfloor-1.
$$
For $n\le k-1$ both functions equal to $n$.

As one expects, the asymptotic order of $\ex(v,n)$ respects the containment order of sequences:
\begin{equation}\label{respects}
u\subset v\Rightarrow \ex(u,n)\ll_{u,v}\ex(v,n).
\end{equation}
For $\|u\|=\|v\|$ this is triviality, since then 
even $\ex(u,n)\le\ex(v,n)$. For $\|u\|<\|v\|$ this follows immediately from the first bound in 
(\ref{exvkn}), and $\ll$ cannot in general be replaced with $\le$. 

\noindent
{\bf Blow-ups.} If $a\in A$ and $i\in\N$, we write $a^i$ for the sequence $aa\ldots a$ of $i$ $a$'s. We call $u$ a {\em chain\/} if $\|u\|=|u|$, that is, $u$ has no repetition. Obviously, $\ex(a^i,n)=(i-1)n$ for any $i\in\N$ and $\ex(v,n)=\min(|v|-1,n)$ 
for any chain $v$.

In the extremal theory of sequences we want to determine, for as many 
sequences as possible, the extremal functions or at least their orders 
of growth. At present our knowledge is still very fragmentary. 
The most succesful approach so far turned out to be the following one. We start 
with some sequences 
$v_1,\dots,v_r$ and combine them, by a specific operation, into a new 
sequence $w$. If certain conditions are satisfied, we can bound 
$\ex(w,n)$ in terms of the functions $\ex(v_i,n)$. We have found 
three such operations; two are unary ($r=1$) and one is binary ($r=2$). 
They have two common features: the resulting $w$ always contains all $v_i$ and 
if $\ex(v_i,n)\ll n$ for all $i=1,\dots,r$ then $\ex(w,n)\ll n$ as well. 
We begin with one of the unary operations, the blow-up.

Every sequence $u$ expresses uniquely in the form 
$u=a_1^{i_1}a_2^{i_2}\ldots a_r^{i_r}$, where $a_j\in A$, 
$a_j\neq a_{j+1}$, and $i_j\in\N$. The {\em blow-up\/} of $u$ is any 
sequence isomorphic to $a_1^{k_1}a_2^{k_2}\ldots a_r^{k_r}$, where 
$k_1\ge i_1$, $k_2\ge i_2, \ldots$, $k_r\ge i_r$. For example, $1221111$ and 
$a^3b^3a=aaabbba$ are blow-ups of $\al_3=aba$. 

If $v$ is not a chain, then 
$\ex(v,n)\ge |1\;2\;\ldots\ n|=n$. On the other hand, we mentioned above that
for every chain $u$ the function $\ex(u,n)$ is eventually constant. 
Thus the extremal function $\ex(v,n)$ of 
every proper blow-up $v$ of a chain $u$ grows 
substantially faster than $\ex(u,n)$. There are reasons to believe that, 
except of this trivial situation, blowing up a sequence cannot change the asymptotics of its extremal function:

\noindent
{\bf Problem 5.} 
Prove (or disprove) that if $u$ is not a chain and $v$ is a blow-up of $u$, 
then
$$
\ex(v,n)\ll_{u,v}\ex(u,n). 
$$
\vskip -36pt
\kduk


\noindent
The lower bound $\ex(v,n)\ge \ex(u,n)$ is trivial. 

Adamec, Klazar and Valtr \cite{adam_klaz_valt} proved that the bound in 
Problem 5 often holds. Namely, if $a$ is a symbol and $u,v$ sequences, 
then 
\begin{equation}\label{blowup}
\ex(a^2u,n)-\ex(au,n)\ll_{au}n\ \mbox{ and }\ \ex(ua^3v,n)\ll_{ua^2v} \ex(ua^2v,n).
\end{equation}
By symmetry, also $\ex(ua^2,n)-\ex(ua,n)\ll_{ua}n$. 
Let $v=a_1^{k_1}a_2^{k_2}\ldots a_r^{k_r}$ be any blow-up 
of $u=a_1^{i_1}a_2^{i_2}\ldots a_r^{i_r}$ such that $k_j>i_j$ implies  
$i_j\ge 2$ or $j=1$ or $j=r$. Applying the bounds (\ref{blowup}),  
it is easy to see that then $\ex(v,n)\ll\ex(u,n)$. Both extremal functions 
are then of the same asymptotic order. For example, 
$a^4bc^5ab^2$ and $abc^2ab$ have extremal functions with the same asymptotic 
order.

In Problem 5, it remains to settle the case when $uav$ is not a chain and is
blown-up to $ua^2v$ (here $u$ and $v$ are nonempty sequences, $u$ does not end with $a$, and $v$ 
does not begin with $a$).  
This operation is not covered by the results (\ref{blowup}) and whether it changes asymptotics is unknown. Surprisingly, this does happen for certain 
tree generalizations of $\ex(v,n)$, as shown by Valtr in \cite{valt99}. 
This is a contrary evidence showing that perhaps blow-ups may 
change asymptotics.

\noindent
{\bf Example 6 (\cite{adam_klaz_valt}).}
We prove the first bounds of (\ref{exvkn}) and (\ref{blowup}). 
We begin with (\ref{exvkn}). Let $v$ be 
a fixed sequence, $k\ge\|v\|$ be a number, and $u$ be a $\|v\|$-sparse 
and $v$-free sequence. It suffices to show that $u$ has a 
$k$-sparse subsequence 
$w$ such that $|w|\gg_{v,k} |u|$. We set $w$ to be the longest $k$-sparse 
subsequence of $u$. Let $I$ be any of the intervals in $u$ that are disjoint 
to $w$ and are maximal to this property. Suppose, for a 
while, that $\|I\|\ge 2k-1$. Then there must be an $a\in S(I)$ that differs 
from the $k-1$ terms of $w$ preceding $I$ and also from the $k-1$ terms of 
$w$ following after $I$. Such an $a$ could be added to $w$, in contradiction with the maximality of $w$. Hence $\|I\|\le 2k-2$ for every $I$. Thus
$|I|\le\ex(v,2k-2)$ for every $I$ and $|w|\ge 1+|u|/(1+\ex(v,2k-2))$. This 
finishes the proof of the first bound in (\ref{exvkn}). 

Now we prove that $\ex(a^2u,n)=\ex(au,n)+O(n)$, where the constant in $O$ 
depends on the sequence $au$. Let $k=\|a^2u\|$ and $v$ be a 
$k$-sparse and $a^2u$-free sequence with $\|v\|\le n$. First, we show that 
there is a constant $c>0$ depending only on $a^2u$ and with the 
following property. 
For every term $x$ of $v$ there is a $k$-sparse subsequence $w$ of $v$ 
avoiding $x$ and of length $|w|\ge |v|-c$. In other words, $x$ plus some 
other $O(1)$ terms of $v$ can be deleted so that the $k$-sparseness is 
preserved. To prove it, we fix an arbitrary interval $I$ in $v$ containing $x$ and of length
$|I|=\ex(a^2u,3k-3)+1$. So $\|I\|\ge 3k-2$ and there must be a subset 
$Y\subset S(I)$, $|Y|=k-1$, such that every $y\in Y$ is distinct from $x$,  
from the $k-1$ terms preceding $I$, and from the $k-1$ terms following 
after $I$. We fix in $I$ one appearance 
for each $y\in Y$ and we delete from $v$ the rest of $I$. 
The resulting sequence $w$ is clearly $k$-sparse, $x$ was deleted, and 
$|w|\ge |v|-(\ex(a^2u,3k-3)+2-k)$. We can set $c=\ex(a^2u,3k-3)+2-k$.

In this way we delete from $v$, one by one, the first appearances of 
all $x\in S(v)$. At most $cn$ elements are deleted and 
the resulting subsequence $w$ is $k$-sparse. Clearly, $w\not\supset au$ 
because otherwise $v\supset a^2u$ would be forced. 
Thus $|v|\le |w|+cn\le\ex(au,n)+cn$ 
and $\ex(a^2u,n)\le\ex(au,n)+O(n)$. Trivially, $\ex(a^2u,n)\ge\ex(au,n)$.
\kduk

\noindent
{\bf The two-letter theorem.} If $u$ has at most two symbols, then either 
$u\supset ababa$ and $\ex(u,n)\ge\f_3(n)\gg n\alpha(n)$, or $u$ 
is contained in a blow-up of $abab$. The main result of \cite{adam_klaz_valt}
says that for the latter $u$'s we have $\ex(u,n)\ll_u n$. We obtain the 
characterization (\cite[Theorem 5]{adam_klaz_valt}) that is in \cite{valt99} 
called the {\em two-letter theorem\/}: If $\|u\|\le 2$ then
\begin{equation}\label{dvepismena}
\ex(u,n)\ll_u n\iff u\not\supset ababa.
\end{equation}
It follows from (\ref{respects}) and from the discussion after Problem 5 that
the proof of (\ref{dvepismena}) (given $\f_3(n)\gg n\alpha(n)$) reduces 
to proving that  $\ex(ab^2a^2b,n)\ll n$. By (\ref{blowup}), this implies 
$\ex(a^ib^ja^kb^l,n)\ll_m n$, where $m=\max(i,j,k,l)$, for every choice of 
the exponents $i,j,k,l\in\N_0$. 

\noindent
{\bf More results and errors on blow-ups.} In \cite[p. 467]{klaz_valt} 
the first author wrote: ``However, it may be checked that the method 
[of Hart and Sharir] ($\ldots$) works for $a^ib^ia^ib^ia^i$ as well and so 
$Ex(a^ib^ia^ib^ia^i,n)=\Theta(n\alpha(n))$.''. However, after some time he 
realized that no matter how hard he tried he could not recollect the proof 
anymore and therefore we have the following problem.

\noindent
{\bf Problem 6.} 
Prove (or disprove) that $\ex(v,n)\ll_v n\alpha(n)$ for every blow-up $v$ of 
$ababa$. That is, prove (or disprove) that
$$
\ex(ab^2a^2b^2a,n)\ll n\alpha(n).
$$
\vskip -36pt
\kduk


\noindent
This is a special case of Problem 5.
We are not done with the forbidden 5-term alternating subsequence yet! 
The applications of the conjectural bound $\ex(a^ib^ia^ib^ia^i,n)\ll_i n\alpha(n)$
in  \cite[3.2]{klaz_valt} must be considered as unproved.

A simpler proof of the two-letter theorem was given in Klazar \cite{klaz96a}. 
In particular, he proved that 
$$
7n-9\le\ex(ab^2a^2b,n)\le 8n-7
$$
and $\ex(a^ib^ia^ib^i,n)<(1+o(1))32i^2\cdot n$. The method of \cite{klaz96a} was extended in Klazar \cite{klaz94} to the blow-ups of the sequences $v_k$ of 
Example 5. In \cite{klaz94} he proved that, for $i\in\N$ and $k$ distinct 
symbols $a_1,a_2,\ldots,a_k$,
\begin{equation}\label{94JCTA}
\ex(a_1^ia_2^i\ldots a_k^ia_1^ia_2^i\ldots a_k^i,n)\ll_{i,k}n.
\end{equation}

\noindent
{\bf Two general questions on the growth of $\mathbf{Ex(v,n)}$.} Is the 
equivalence (\ref{dvepismena}) valid for sequences using more than two 
symbols? Klazar and Valtr realized that the answer was ``no''. A 
specific example is given in Klazar \cite{klaz93}: $u_1=abcbadadbcd\not\supset ababa$ but $\ex(u_1,n)\gg n\alpha(n)$. A more extremal example in this direction is given
in \cite{klaz99}: 
$$
u_2=abcbadadbecfcfedef\not\supset ababa\ \mbox{ but }\ 
\ex(u_2,n)\gg n2^{\alpha(n)}.
$$
Thus the containment of $\al_5=ababa$ is not the sole cause of superlinearity.
These examples are obtained by showing that the constructions of 
\cite{wier_shar} and \cite{agar_shar_shor} produce sequences avoiding not 
only $ababa$ and $ababab$, respectively, but even $u_1$ and $u_2$. Some new 
construction might help to solve the following problem.

\noindent
{\bf Problem 7.} 
We conjecture that for every constant $c>0$ there exists 
a sequence $u$ such that
$$
u\not\supset ababa\ \mbox{ but }\ \ex(u,n)\gg n2^{\alpha(n)^c}.
$$
\vskip -32pt
\kduk

\noindent
In other words, in view of (\ref{muj}), we conjecture that every extremal function 
$\ex(v,n)$ is majorized (for $n>n_0$) by some $\ex(u,n), u\not\supset ababa$.
Below we will see that $u\not\supset abab$ implies $\ex(u,n)\ll_u n$. 
 
Another attractive but at present hopeless question is whether 
$n\alpha(n)$ is the smallest superlinear growth of extremal functions.

\noindent
{\bf Problem 8.} 
Is it true that for every sequence $u$ either $\ex(u,n)\ll n$ or 
$\ex(u,n)\gg n\alpha(n)$?
\kduk


Is there an extremal function whose restrictions to two infinite subsequences 
of $\N$ have different orders of growth? Said more explicitly, we ask if there exist a 
sequence $u$, two infinite subsequences $1\le n_1<n_2<\dots$ and $1\le m_1<m_2<\dots$ of 
$\N$, and two increasing functions $f,g:\N\to\R^+$ with $f(n)/g(n)\to\infty$, such that 
$f(n_i)\ll\ex(u,n_i)\ll f(n_i)$ and $g(m_i)\ll\ex(u,m_i)\ll g(m_i)$ as $i\to\infty$.
Valtr \cite[Proposition 3]{valt99} shows that for every sequence $u$,
$$
\limsup_{n\rightarrow\infty}{\ex(u,n)\over n}=\infty\Longrightarrow
\liminf_{n\rightarrow\infty}{\ex(u,n)\over n}=\infty.
$$
So in any case one cannot select $g(n)=n$.
If $u$ is irreducible, which means that there is no nontrivial decomposition 
$u=u_1u_2$ with $S(u_1)\cap S(u_2)=\emptyset$, then it is easy to prove the 
stronger result that $\lim_{n\rightarrow\infty}\ex(u,n)/n$ exists (it may equal 
$\infty$). 

\noindent
{\bf Insertions and intertwinings.} We proceed to the remaining two 
operations which compose $w$ from $v_1,\dots,v_r$ so that $\ex(w,n)$ can 
be bounded in terms of $\ex(v_1,n),\dots,\ex(v_r,n)$. They constitute 
the main result of Klazar and Valtr \cite{klaz_valt}. 

Let $a$ and $b$ be two distinct symbols and $u_1,u_2$, and $v$ be three sequences. 
The {\em insertion\/} of $v$ in $u=u_1a^2u_2$ gives the sequence $w=u(v)=u_1avau_2$. The 
{\em intertwining\/} of $u=u_1a^2u_2a$ and $b$ gives 
the sequence $w=u[b]=u_1ab^2au_2ab$. We can bound $\ex(u(v),n)$ only 
under the assumption that $S(u_1a^2u_2)\cap S(v)=\emptyset$. Similarly, we 
can bound $\ex(u[b],n)$ only under the assumption that 
$b\not\in S(u_1a^2u_2a)$. The insertion is a binary operation in the sense 
that it is determined completely by two sequences $u,v$ and an 
immediate repetition $\dots aa\dots$ in $u$. In the similar sense the 
intertwining is an unary operation. 

Let $u=u_1a^2u_2$ and $v$ be two sequences with $S(u)\cap S(v)=\emptyset$, 
and $u(v)$ arise by inserting $v$ in $u$. If $v$ is a chain, it is easy 
to see that $\ex(u(v),n)\le\ex(u,n)$. If $v$ is not a chain then, as proved in 
\cite{klaz_valt},
\begin{equation}\label{insert}
\ex(u(v),n)=\ex(u_1avau_2,n)\ll_{u,v}\ex(v,\ex(u,n)).
\end{equation}

Let $u=u_1a^2u_2a$ be a sequence, $b$ be a symbol such that 
$b\not\in S(u)$, and $u[b]$ arise by intertwining $u$ with $b$. 
Then, as proved in 
\cite{klaz_valt},
\begin{equation}\label{intertw}
\ex(u[b],n)=\ex(u_1ab^2au_2ab,n)\ll_u\ex(u,n).
\end{equation}
By symmetry, we have the analogous statement for $bau_1ab^2au_2$.
The lower bounds 
$$
\ex(u(v),n)\gg_{u,v}\max(\ex(u,n),\ex(v,n))\  \mbox{ and }\  
\ex(u[b],n)\gg_u\ex(u,n)
$$ 
are immediate from (\ref{respects}). Simpler 
proofs of (\ref{insert}) and (\ref{intertw}) were given in Valtr 
\cite{valt99}. Blowing-up $u[b]$, we obtain from (\ref{intertw}) 
for $i,j\in\N$ the bounds 
$$
\ex(u_1ab^iau_2ab^j,n)\ll_{u,i,j}\ex(u,n)
$$ 
(remember the condition $b\not\in S(u)$).

\noindent
{\bf Linear sequences.} It is natural (but difficult) to investigate the class of the {\em linear sequences\/}
$$
\lin=\{v:\ \ex(v,n)\ll n\}.
$$
We have already met several members of it: $abab$ (Example 2), $abba$ and
$v_k$ (Example 5), $a^i$ and chains (trivial). On the other hand, 
$ababa\not\in\lin$ by (\ref{hart_shar}).

\noindent
{\bf Problem 9.} 
What are the elements of $\lin$?
\kduk


The bounds (\ref{blowup}), (\ref{insert}), and (\ref{intertw}) give a 
simple method to obtain many members of $\lin$:  start with $a^i$ 
and by repeated blow-ups, insertions, and intertwinings generate linear 
sequences. To formulate it more precisely, let $L$ be the smallest class 
of sequences that is closed on the isomorphism and has the following closure properties: (i) for every $i\in\N$, $a^i\in L$; (ii)
if $au\in L$ then $a^iu\in L$ for every $i\in\N$, and  
if $ua\in L$ then $ua^i\in L$ for every $i\in\N$; (iii) if $ua^2v\in L$ 
then $ua^iv\in L$ for every $i\in\N$; 
(iv) if $u=u_1a^2u_2,v\in L$ and $S(u)\cap S(v)=\emptyset$ then 
$u_1avau_2\in L$; and (v) if $u=u_1a^2u_2a\in L$ and $b\not\in S(u)$ then 
$u_1ab^2au_2ab\in L$, and if $u=au_1a^2u_2\in L$ and $b\not\in S(u)$ then $bau_1ab^2au_2\in L$. Then (\cite{klaz_valt}),
$$
L\subset\lin.
$$
Observe that, by the way of definition, $L$ is closed to the containment and to all 
blow-ups. 

\noindent
{\bf Problem 10.} 
Decide if there is a sequence $u\in\lin\backslash L$.
\kduk


By (\ref{respects}), $u\subset v\in\lin$ implies that $u\in\lin$. Hence we can 
characterize $\lin$ by means of the class of minimal nonlinear sequences
$$
B=\{u:\ u\not\in\lin\mbox{ but $v\in\lin$ whenever 
$v\subset u\;\&\;|v|<|u|$}\}.
$$
Namely, we have the equivalence $u\in\lin\iff\forall v\in B\; [v\not\subset u]$. Knowing (effectively) $B$, we could hope to draw more information about $\lin$.
Unfortunately, at present we know only 
two significant properties of $B$: (i) $ababa\in B$ and (ii) $B$ has at least two elements. The first property follows from the facts that 
$\f_3(n)\gg n\alpha(n)$ (by (\ref{hart_shar})), $abab\in\lin$ (Example 2), $ab^2a\in\lin$ 
(Example 5), and $aba^2\in\lin$ (trivial). As for (ii), it follows from the examples 
given after the bound (\ref{94JCTA}). Might $B$ be infinite?

\noindent
{\bf Problem 11.} 
Is the set $B$ of minimal nonlinear sequences finite or infinite?
\kduk


\noindent
One might hope to prove the finiteness of the set $B$, which is an 
antichain to the containment, by proving that the quasiordering $(A^*,\subset)$ 
has no infinite antichains at all. However, one can 
easily construct infinite antichains in $(A^*,\subset)$ and thus $B$ 
still might be infinite. An infinite antichain is presented by Klazar 
\cite{klaz93} who also determines certain well quasiordered subsets of $A^*$.

\noindent
{\bf Interesting sequences in the class $\mathbf{L}$.}
Let us return to the class $L$ of the sequences whose linearity 
we can prove. It is rich enough to contain several interesting families of sequences. 
First we prove by induction on $|u|$ that every $abab$-free 
sequence $u$ falls in $L$. If $u$ is $abab$-free then $u$ is isomorphic 
to $au_1au_2a\ldots au_k$, where $u_1,\dots,u_k$ are possibly empty 
sequences, the sets $S(u_i)$ are mutually disjoint, and 
$a\not\in S(u_i)$ for every $i=1,\dots,k$. By induction, $u_i\in L$ for every 
$i=1,\dots,k$. Inserting in $a^{k+1}$ the sequences $u_1,\dots,u_k$, we 
conclude (applying $k$ times the closure property (iv)) that $u\in L$. 
Thus $\ex(u,n)\ll_u n$ for every $abab$-free sequence $u$. In particular,
$$
\DS_4\subset\lin.
$$
Recall that $u_1=abcbadadbcd\not\in\lin$ and $u_1\not\supset ababa$. 
Thus $\DS_5\not\subset\lin$.

Intertwinings and blow-ups yield an immediate proof of the two-letter 
theorem: $a^3\in L$ by (i), $ab^2a^2b\in L$ by (v), and 
$a^ib^ia^ib^i\in L$ ($i\ge 2$) by (ii) and (iii). Hence every $a^{i_1}b^{i_2}a^{i_3}b^{i_4}$ ($i_j\ge 0$) is linear. 

Intertwinings bring in $L$ sequences more complicated than 
$abab$-free sequences. Repeated intertwinings and blow-ups show that the sequence
$$
u'=1\;2\;1\;2\;3\;2\;3\;4\;3\;4\;5\;4\;\ldots (k-2)\;(k-1)\;(k-2)\;(k-1)\;k\;(k-1)\;k
$$
of Example 5 lies in $L$. Hence this longest $abba$-free 2-sparse 
sequence is linear for every 
$k$, as well as its every blow-up. On the other
hand, $abcadbcd\not\supset abba$ but $abcadbcd\not\in L$. At present 
we are not able to prove the linearity of all $abba$-free sequences.

Similarly, intertwinings and blow ups show that for every $k$ and $i$ the 
$N$-shaped sequence
$$
u_N(k,i)=1^i2^i\ldots (k-1)^ik^i(k-1)^i\ldots 2^i1^i2^i\ldots (k-1)^ik^i
$$ 
belongs to $L$ and thus is linear. The bound
\begin{equation}\label{Nshaped}
\ex(u_N(k,i),n)\ll_{i,k} n
\end{equation}
is an important result of \cite{klaz_valt} and a considerable strengthening 
of (\ref{94JCTA}). 

It follows by a case analysis that every $ababa$-free sequence $u$ 
with $\|u\|\le 3$ is contained in a blow-up of one of the three sequences 
$v_1=ababcbc$, $v_2=abcbabc$, and $v_3=abacacbc$. All blow-ups 
of $v_1$ and $v_2$ are in $L$ and thus are linear; $v_1$ is the $k=3$ instance 
of the above $u'$ and $v_2=u_N(3,1)$. But $v_3=abacacbc\not\in L$. 

\noindent
{\bf Problem 12.} 
Is it true that $\ex(abacacbc,n)\ll n$? And what about the blow-ups of 
$abacacbc$?
\kduk
%Je ten problem v P. E. is 80, vol. 2 ?


\noindent
In fact, the minimal subsequences of $v_3=abacacbc$ lying outside $L$ 
are $abacabc$, 
$abcacbc$, $abacacb$, and $bacacbc$. The first two are, up to the isomorphism, reversals of 
one another and hence have equal extremal 
functions. The same holds for the last two sequences. Writing $\overline{u}$ 
for the reversal of $u$, we have this partial characterization of 
the linear sequences over three symbols: for $\|u\|\le 3$,
$$
\mbox{$u$ and $\overline{u}$ contain none of }\{ababa, abacabc, 
abacacb\}\Rightarrow\ex(u,n)\ll_u n.
$$
In the opposite direction we know only that $ababa\subset u$ 
implies the nonlinearity of $u$.

\vskip 30pt
\section*{\normalsize 5. Geometric Graphs, Colored Trees, $0$-$1$
Matrices, Ordered Bipartite Graphs,  Permutations, and Set Partitions}

\noindent
{\bf Geometric graphs.} Generalized DS sequences found interesting applications 
in the combinatorics of {\em geometric graphs\/}. These are particular planar realizations 
of graphs: the vertices of a graph are represented by some points in the plane lying 
in the general position and the edges are represented by possibly crossing straight segments. 
Two edges of a geometric graph {\em cross\/} if their relative interiors intersect, and they are 
{\em parallel\/} if they form two opposite sides of a convex quadrilateral. 

Katchalski and Last \cite{katc_last} proved, using the bound 
(\ref{DSN4}), that any geometric graph with $n$ vertices and no two parallel 
edges has at most $2n-1$ edges. Valtr \cite{valt98} lowered this bound to 
$2n-2$, which proves the conjecture of Y. S. Kupitz from 1979; Figure 2
shows geometric graphs attaining this number of edges.
\begin{figure}
\unitlength1mm
\begin{picture}(60,50)(-35,-3)
%\thicklines
\put(0,0){\circle*{1}}\put(60,0){\circle*{1}}\put(37.7,29.6){\circle*{1}}
\put(30,6){\circle*{1}}\put(30,10){\circle*{1}}\put(30,15){\circle*{1}}
\put(30,20){\circle*{1}}
\put(0,0){\line(1,0){60}}
\put(0,0){\line(5,4){37.5}}\put(60,0){\line(-3,4){22}}
\put(0,0){\line(5,1){30}}\put(60,0){\line(-5,1){30}}
\put(30,6){\line(1,3){7.8}}
\put(0,0){\line(3,1){30}}\put(0,0){\line(2,1){30}}
\put(0,0){\line(3,2){30}}
\put(60,0){\line(-3,1){30}}\put(60,0){\line(-2,1){30}}
\put(60,0){\line(-3,2){30}}
\end{picture}
\caption{Geometric graphs with $n$ vertices and $2n-2$ edges, no two 
of them ``parallel''.}
\end{figure}
(Another nice application of (\ref{DSN4}) in combinatorial geometry 
was given by Edelsbrunner and Sharir in the article \cite{edel_shar} 
with a self-explaining title.)
Applying the $N$-sequence bound (\ref{Nshaped}), Valtr proved
in \cite{valt98} more generally   
that every geometric graph with $n$ vertices and no $k$ pairwise parallel 
edges has $\ll_k n$ edges. From this he derived that if $k$ pairwise 
crossing edges are forbidden, then the number of edges is $\ll_k n\log n$. 
(For these results see also \cite{valt99}.)
This improves the previous bound $\ll_k n\log^{2k-6}n$ (for $k>2$) of 
Agarwal et al. \cite{agar_al} (based on the bound $\ll_k n\log^{2k-4}n$
of Pach, Shahrokhi and Szegedy \cite{pach_shah_szeg}). Whether the bound 
$\ll_k n$ holds is open. It is known 
to hold only for $k=2$ (the classical case of planar graphs) and $k=3$ (\cite{agar_al}).

Precisely speaking, the bounds $\ll_k n\log^{2k-6}n$ of \cite{agar_al} and 
$\ll_k n\log n$ of \cite{valt98} are in a sense incomparable. The former 
bound holds, as stated in \cite{agar_al}, for the more general representation 
of edges by curves (details are in \cite{agar_al} given only 
for the case of segments). The latter stronger bound applies on the more 
special representation by segments. In \cite{valt97} Valtr extended it to the situation 
when edges 
are represented by $x$-monotone curves, but the case of general curves seems 
out of reach of his method.

For further applications of DS sequences in computational and combinatorial  geometry, 
see \cite{agar_shar} and \cite{shar_agar}.

\noindent
{\bf Colored trees.} From the viewpoint of graph theory, sequences can be regarded as 
undirected colored paths, where colors are the symbols used. For example, $abcabc$ is the path 
of six vertices $v_1v_2\ldots v_6$ where $v_1$ and $v_4$ are colored $a$, $v_2$ and $v_5$
 are colored $b$, and $v_3$ and $v_6$ are colored $c$. 
To work with more exciting objects, we regard colored paths just
as special cases of colored trees. Can one extend in a reasonable way the 
definition (\ref{obextrfcedef}) to colored trees? Can one prove for colored trees an 
analogue of, say, $\f_2(n)=\ex(abab,n)=2n-1$? We begin with the latter problem.

Let $T(abab,n)$ be the maximum number of vertices in a tree $T=(V,E)$ that 
can be vertex-colored by at most $n$ colors so that three conditions hold:
\begin{enumerate}
\item The coloring is proper, which means that no edge is monochromatic.
\item No subgraph of the colored tree $T$ is a subdivision of the properly 
2-colored 4-vertex path
\makebox[1.5cm]{$\bullet\hskip-1.7mm-\hskip-1.7mm\circ\hskip-1.7mm-\hskip-1.7mm
\bullet\hskip-1.7mm-\hskip-1.7mm\circ$}.
\item No subgraph of the colored tree $T$ is a subdivision of the properly 
2-colored 4-vertex star 
\raisebox{-6mm}{
\makebox[1.2cm]{
\unitlength1mm
\begin{picture}(10,6)(0,0)
\put(0,6){$\bullet\hskip-1.7mm-\hskip-1.7mm\circ\hskip-1.7mm-\hskip-1.7mm
\bullet$}
\put(3.9,2.5){$\bullet$}\put(4.9,4.3){\line(0,1){2}}
\end{picture}
}}.
\end{enumerate}

The condition 1 is the analogy of 2-sparseness. The condition 2 forbids in $T$ the color 
pattern $abab$ and it requires, for the coloring $f: V\to\N$, that there are no four distinct 
vertices $v_1,\dots,v_4\in V$ such that $f(v_1)=f(v_3)\neq f(v_2)=f(v_4)$ and the $v_1$-$v_4$ 
path contains, in this order, the vertices $v_2$ and $v_3$. The condition 3 requires that there 
are no three distinct vertices $v_1,\dots,v_3\in V$ such that 
$f(v_1)=f(v_2)=f(v_3)\neq f(v_4)$ and the three 
$v_i$-$v_4$ paths are disjoint except for $v_4$. For colored trees the conditions 1 and 2 
alone do not suffice to bound the number of vertices, as shown by 
arbitrarily large properly colored stars. Therefore we add the 
condition 3. To reformulate it, define for a color $c$ and a colored tree $T$ the tree $T(c)$ 
as the smallest subtree of $T$ containing all $c$-colored vertices. The condition 3 then 
says that, for every color $c$, in the tree  $T(c)$ all vertices with degrees at least 3 must be 
colored $c$. Notice that if we restrict $T$ to paths, 
then $T(abab,n)$ coincides with $\ex(abab,n)$. This is due to the fact 
that the sequence $abab$ is isomorphic to its reversal. 
 
\noindent
{\bf Example 7 (\cite{klaz97}).}
 We prove that for every $n\in\N$,
\begin{equation}\label{ababstromy}
T(abab,n)=2n-1.
\end{equation}
So if $T$ ranges over the larger set of all trees, $T(abab,n)$ still equals 
$\ex(abab,n)=\f_2(n)=2n-1$.

The lower bound $T(abab,n)\ge 2n-1$ is achieved already on colored paths. 
More strongly, we can color any tree $U$ on $2n-1$ vertices with $n$ colors so that the conditions 1, 2, 
and 3 are satisfied: we color with $1$ two arbitrary leaves of 
$U$, then we color with $2$ two arbitrary leaves of the uncolored subtree of $U$,
and so on until the whole $U$ is colored.  

We prove the opposite inequality $T(abab,n)\le 2n-1$.
Let $T=(V,E)$ be a tree and $f: V\rightarrow\{1,2,\ldots,n\}$ be a coloring 
satisfying the conditions 1, 2, and 3. We show that $|V|\le 2n-1$. We may 
assume that $n>1$ and that $b(T)=\#\{v\in V:\ \mathrm{deg}_T(v)\ge 3\}>0$; else 
$T$ is a path and $|V|\le\ex(abab,n)=2n-1$. Formally, we proceed by induction 
on the sum $n+b(T)$. We use the operation of {\em smoothing out\/} 
a vertex $u$ of degree $1$ or $2$. For $\deg_T(u)=1$ this is just 
the deletion of $u$. For $\deg_T(u)=2$ we delete $u$ and connect its two 
neighbours by an edge. 

Observe that there is a vertex $v$ in $T$ 
with degree at least 3 and such that $T-v=P_1\cup P_2\cup\ldots\cup P_l\cup C$ 
where $l\ge 2$, every $P_i$ is a path, and $C$ is a tree which may not be 
a path. First we show that $f$ may be assumed to be injective on the set 
$V(T)\backslash V(C)=\{v\}\cup V(P_1)\cup \ldots\cup V(P_l)$. If this is not the case, 
then $f(u_1)=f(u_2)$ for two distinct $u_1,u_2\in V(T)\backslash V(C)$, 
and either (i) $\{u_1,u_2\}\subset\{v\}\cup V(P_i)$ for some $i$ or (ii)
$u_1\in V(P_i)$ and $u_2\in V(P_j)$ for some $i\neq j$. In the case (i), there  
must be a vertex $u_3$ between $u_1$ and $u_2$ whose color $c=f(u_3)$ does 
not appear elsewhere in $T$; else we would have in $T$ the color pattern $abab$. Smoothing 
out $u_3$ and, if necessary, one of its 
neighbours (lest we create a monochromatic edge), we get rid of the 
color $c$ and keep the three conditions satisfied. By induction, $|V|\le 2(n-1)-1+2=2n-1$. 
In the case (ii) we may assume that the color $c=f(u_1)=f(u_2)$ does not 
appear elsewhere in $T$; else we have the case (i) or the  
condition 3 is violated. If $u_1$ has two neighbours, they have 
distinct colors for else we would have the $abab$ pattern. The same 
holds for $u_2$. We get rid of $c$ by smoothing out both $u_1$ and $u_2$; 
this creates no monochromatic edge. The three conditions are satisfied and we  
conclude again by induction that $|V|\le 2(n-1)-1+2=2n-1$.

Thus we may assume that on the vertices in $V(T)\backslash V(C)$ 
no color is repeated. We 
transform the colored tree $(T,f)$ into a new colored tree $(T^*,f^*)$ 
by splitting the paths $P_1,\ldots, P_l$ into individual vertices, 
assembling from them a single colored path $P$, and joining $P$ back to 
$v$. During the transformation every vertex keeps its color. 
The number of colors has not changed, $b(T^*)=b(T)-1$ because 
$\deg_{T^*}(v)=2$, and $(T^*,f^*)$ clearly satisfies the conditions 1 and 3. 
It remains to find an appropriate order for the vertices in $P$ so that  
$(T^*,f^*)$ does not contain the color pattern $abab$. Then we apply 
the inductive assumption and conclude that $|V(T)|=|V(T^*)|\le 2n-1$. 

To this end we define a binary relation $R$ on the set of colors appearing in 
$V(P_1)\cup \ldots\cup V(P_l)$.
We set $aRb$ iff $a\neq b$ and there is a path $Q=(v_0,\ldots,v_k)$ in $C\cup\{v\}$, $v_0=v$, such that, for some $i<j$, $f(v_i)=a$ and $f(v_j)=b$. We show that $R$ 
is a strict partial ordering. First we prove that $R$ is antisymmetric.
Suppose, for the contradiction, that $aRb$ and $bRa$, witnessed by paths $Q_1$ and $Q_2$,
respectively. Let $w$ be the merging vertex of $Q_1$ and $Q_2$. One case is that 
$a$ and $b$ appear on $Q_1$ in this order after $w$ (if we go in the $v$-$w$ direction), and 
the same holds for the appearances of $b$ and $a$ on $Q_2$. Since both colors appear also 
in the paths $P_i$, we have a contradiction with the condition 3: $w$ should have both colors 
$a$ and $b$. If this case does not occur 
(which includes the possibility $Q_1=Q_2$), then $Q_1$ 
or $Q_2$ must contain the pattern $aba$ or $bab$. 
But then $(T,f)$ contains the pattern $abab$, which contradicts the condition 2. Thus $R$ is 
antisymmetric. The transitivity of $R$ can be proved by very similar arguments which we omit.  

$R$ is a strict partial ordering. Any occurrence of the pattern $abab$ in 
$(T^*,f^*)$ would have to use 
two vertices of $C\cup\{v\}$ and two vertices of $P$. We order the vertices in $P$ in a linear 
extension of $R$ so that if $aRb$ then the vertex in $P$ colored $a$ is closer to $v$ than 
the vertex colored $b$. Then no $abab$ pattern can appear. 
\kduk


For a general sequence $u\in A^*$ with $\|u\|>1$, we define $T(u,n)$ as the maximum number of 
vertices of a tree $T$ that can be vertex-colored by at most $n$ colors so that three conditions hold:
\begin{enumerate}
\item Two distinct vertices with the same color have distance at least $\|u\|$ edges.
\item No subgraph of the colored tree $T$ is a subdivision of the path of $|u|$ vertices that is 
colored according to 
$u$.
\item No subgraph of the colored tree $T$ is a subdivision of the properly 
2-colored 4-vertex star 
\raisebox{-6mm}{
\makebox[1.2cm]{
\unitlength1mm
\begin{picture}(10,6)(0,0)
\put(0,6){$\bullet\hskip-1.7mm-\hskip-1.7mm\circ\hskip-1.7mm-\hskip-1.7mm
\bullet$}
\put(3.9,2.5){$\bullet$}\put(4.9,4.3){\line(0,1){2}}
\end{picture}
}}.
\end{enumerate}
We keep the condition 3 and modify the first two conditions in the obvious way.  
For $\|u\|>1$ this works fine, $T(u,n)<\infty$. For $u=a^i$ the first condition is void and 
for $i\ge 4$ we would still have $T(a^i,n)=\infty$ (consider monochromatic stars). Therefore 
in the special case of $u=a^i$ we require the coloring of $T$ to be proper. We must not forget that 
after replacing sequences by paths we lose the unique left-right order of terms. Forbidding a sequence 
$u$ we forbid its reversal $\overline{u}$ as well. For $u$ isomorphic to $\overline{u}$, if $T$ are 
restricted to paths then $T(u,n)=\ex(u,n)$. We say that then $T(u,n)$ {\em extends\/} $\ex(u,n)$.

This generalization of $\ex(u,n)$ to colored trees, $T(u,n)$, was considered first in 
\cite{klaz_phd}. From the results on $T(u,n)$ proved in Klazar \cite{klaz99a} 
we mention the extension of (\ref{muj}) to colored trees and the exact values
($n>1$)
$$
T(a^i,n)=\left\{
\begin{array}{lll}
(2i-3)n-2i+4&\dots&\mbox{$i\ge 2$ is even}\\
&&\\
(2i-4)n-2i+6&\dots&\mbox{$i\ge 3$ is odd}
\end{array}
\right. 
$$
(recall that for the monochromatic $i$-path $a^i$ the coloring of $T$ is 
required to be proper).
The next example shows that, unlike $abab$, $T(abba,n)\neq\ex(abba,n)$.

\noindent
{\bf Example 8 (\cite{valt99a}).} We show that $T(abba,n)\ge 5n-8$, in contrast with 
$\ex(abba,n)=3n-2$. (Since $abba$ is isomorphic to its reversal, $T(abba,n)$ extends 
$\ex(abba,n)$.) We hope that the construction 
of $(T,f)$ due to P. Valtr and independently discovered also by Ch. Vogt, 
is clear enough from its instance $n=6$ visualized in Figure 3. 

\begin{figure}
\unitlength1mm
\begin{picture}(90,70)(-10,-5)
\thicklines
\multiput(20,30)(15,0){6}{\circle{5}} 
%6 vodor. vrcholu
\put(19.2,29){{\footnotesize 1}}
\put(34.2,29){{\footnotesize 3}}
\put(49.2,29){{\footnotesize 4}}
\put(64.2,29){{\footnotesize 5}}
\put(79.2,29){{\footnotesize 6}}
\put(94.2,29){{\footnotesize 2}}
% jejich barvy
\multiput(22.5,30)(15,0){5}{\line(1,0){10}}
% vodor. hrany
\multiput(20,0)(0,15){5}{\circle{5}}
\multiput(95,0)(0,15){5}{\circle{5}}
% svisle vrcholy
\put(19.2,-1){{\footnotesize 1}}
\put(19.2,14){{\footnotesize 6}}
\put(19.2,44){{\footnotesize 3}}
\put(19.2,59){{\footnotesize 1}}

\put(94.2,-1){{\footnotesize 2}}
\put(94.2,14){{\footnotesize 6}}
\put(94.2,44){{\footnotesize 3}}
\put(94.2,59){{\footnotesize 2}}
% jejich barvy
\multiput(20,2.5)(0,15){4}{\line(0,1){10}}
\multiput(95,2.5)(0,15){4}{\line(0,1){10}}
% jejich hrany
\multiput(20,30)(-11,11){3}{\circle{5}}
\multiput(20,30)(-11,-11){3}{\circle{5}}
\multiput(95,30)(11,11){3}{\circle{5}}
\multiput(95,30)(11,-11){3}{\circle{5}}
% sikme vrcholy
\put(8.2,40.2){{\footnotesize 4}}
\put(-2.8,51.2){{\footnotesize 1}}
\put(8.2,18.2){{\footnotesize 5}}
\put(-2.8,7.2){{\footnotesize 1}}

\put(105.2,40.2){{\footnotesize 4}}
\put(116.2,51.2){{\footnotesize 2}}
\put(105.2,18.2){{\footnotesize 5}}
\put(116.2,7.2){{\footnotesize 2}}
% jejich barvy
\multiput(18.25,31.75)(-11,11){2}{\line(-1,1){7.5}}
\multiput(18.25,28.25)(-11,-11){2}{\line(-1,-1){7.5}}
\multiput(96.75,31.75)(11,11){2}{\line(1,1){7.5}}
\multiput(96.75,28.25)(11,-11){2}{\line(1,-1){7.5}}
% jejich hrany
\end{picture}
\caption{The bound $T(abba,n)\ge 5n-8$ for $n=6$.}
\end{figure}

The coloring is proper, contains no subdivision of $abba$, and satisfies the  
condition 3. In general the horizontal path has $n$ vertices and the 
rays contribute $4(n-2)$ vertices. Together we have $5n-8$ vertices. In Valtr \cite{valt99a} a more
general example is given showing that 
$$
T(a^ib^ia^i,n)\ge 9in-O(i+n).
$$
\vskip -30pt
\kduk


In \cite{klaz_phd} and \cite{klaz97} we posed as a problem to show that 
$T(abba,n)\ll n$. This was accomplished in \cite{valt99a} by Valtr who proved
more generally that 
$$
T(a^ib^ia^i,n)\le 24in.
$$
Thus $5n-8\le T(abba,n)\le 48n$.

\noindent
{\bf Problem 13.} 
Improve these bounds. Or, better, determine the function $T(abba,n)$ exactly.
\kduk


The theory of tree extremal functions was much advanced by Valtr in 
\cite{valt99} and \cite{valt_subm}. He introduced other generalizations of 
$\ex(v,n)$ to colored trees, which are better to work with than $T(v,n)$, and 
he proved analogues of most of the results that we described in the previous 
section. In particular, he extended blow-ups, insertions, 
and intertwinings to colored trees. To discuss properly his results would 
mean to write another Section 4; the interested reader is refered for details to 
\cite{valt99} and \cite{valt_subm}. Here I only say that, contrary 
to my original expectations, the behaviour of tree extremal functions often
turns out to be much different compared to $\ex(v,n)$. For example, the 
two-letter theorem for colored trees (\cite{valt99}, \cite{valt_subm}) says: 
for $\|u\|\le 2$, 
$$
T(u,n)\ll_u n\iff u\not\supset ababa\;\&\;u\not\supset ab^2a^2b.
$$
In fact (\cite{valt99}, \cite{valt_subm}), $T(ab^2a^2b,n)\gg n\alpha(n)$. 
Comparing this with (\ref{ababstromy}), we see that for colored trees blow-ups 
change asymptotics. 

\noindent
{\bf 0-1 matrices and ordered bipartite graphs.} Recall the notation $[n]=\{1,2,\ldots,n\}$ 
and $[a,b]=\{a,a+1,\dots,b\}$. F\"uredi and Hajnal \cite{fure_hajn} investigated 
the following class of extremal problems for $0$-$1$ matrices. Let 
$N:[k]\times [l]\to\{0,1\}$ and $M:[m]\times [n]\to\{0,1\}$ be two 0-1 matrices of types $k\times l$ and 
$m\times n$, respectively. We say that $M$ contains $N$ if there are increasing injections 
$f: [k]\to[m]$ and $g:[l]\to[n]$ such that, for all $i\in[k]$ and $j\in[l]$, $M(f(i),g(j))=1$ whenever 
$N(i,j)=1$. In other words, $M$ has a (not necessarily contiguous) $k\times l$ submatrix that has 1 on every 
position where $N$ has 1, and that has 0 or 1 on every position where $N$ has 0. It is convenient to 
write in the matrices blanks instead of zeros. 
Let $f(m,n;N)$ be the maximum number of 1's in an $m\times n$ 0-1 matrix $M$ not containing 
$N$, and let $f(n;N)=f(n,n;N)$. 
It is easy to see that for every $N$ with at most three 1's one has $f(n;N)\ll n$. For four 1's the 
situation is much more complicated. Performing on $N$ the obvious automorphisms preserving $f(n;N)$, one is 
left with 37 matrices $N$ with four 1's and no zero row or column.
F\"uredi and Hajnal investigated  $f(n;N)$ for each of these $N$. One of their results related to 
DS sequences says that
$$
n\alpha(n)\ll f(n;
\bigg(\begin{array}{llll}
1&&1& \\&1&&1\end{array}\bigg))
\ll n\alpha(n);
$$
the upper bound is obtained from (\ref{hart_shar}) by reduction 
to 5-DS sequences and for the lower bound they give a construction of their own.
They prove the same lower and upper bounds for 
$$
N=\left(\begin{array}{llll}1&&&\\&&1&\\&1&&1\end{array}\right)
$$
and the upper bound $f(n;N)\ll n\alpha(n)$ for 
$$
N=\left(\begin{array}{llll}&1&&\\&&&1\\1&&1&\end{array}\right)
\ \mbox{ and }\ 
N=\left(\begin{array}{llll}&1&&\\&&&1\\1&&&\\&&1&\end{array}\right).
$$
In the end of \cite{fure_hajn} the authors pose a question whether 
$f(n;P)\ll_P n$ holds for all permutation matrices $P$. In \cite{klaz00a} we pointed out 
that this conjecture, if true, would imply the enumerative Stanley--Wilf conjecture (which we 
formulate in a moment). 

One can naturally reformulate the matrix setting in terms of ordered bipartite graphs; these are  
bipartite graphs with linear orders on both parts. $M$ is understood as the bipartite graph 
$\GG=([n],[n+1,n+m],H)$ where, for all $i\in[m]$ and 
$j\in[n+1,n+m]$, $\{i,j\}\in H$ iff $M(i,j-n)=1$. 
The matrix containment translates into the usual subgraph relation, with the important additional 
condition that the linear orders of vertices are preserved. The extremal function $f(n;\HH)$ is defined 
as the maximum number $|H|$ of the edges of a bipartite graph $\GG=([n],[n+1,2n],H)$ such that $\GG$ does 
not contain $\HH$. For a permutation $p=a_1a_2\dots a_k$ of $[k]$, the permutation bipartite graph $\GG_p$ 
is defined as 
$$
\GG_p=([k],[k+1,2k],\{\{i,k+a_i\}:\ i=1,2,\dots,k\}).
$$   
The question of F\"uredi and Hajnal asks if, for any fixed permutation $p$, every $\GG=([n],[n+1,2n],H)$ 
not containing $\GG_p$ as an ordered subgraph must have $\ll n$ edges.   

\noindent
{\bf Permutations.} Alon and Friedgut \cite{alon_frie} 
applied generalized DS sequences to a problem in enumerative combinatorics. Let 
$p=a_1a_2\ldots a_m$ and $q=b_1b_2\ldots b_n$ be permutations of 
$[m]$ and $[n]$, respectively. We say that $q$  
contains $p$ if $q$ has a subsequence $b_{i_1}b_{i_2}\ldots b_{i_m}$, $1\le i_1<i_2<\dots<i_m\le n$, such 
that $b_{i_r}<b_{i_s}\iff a_r<a_s$ for every $r$ and $s$. Else we say that 
$q$ {\em avoids\/} $p$. Let $S_n(p)$ be the number of permutations of 
$[n]$ avoiding $p$. The {\em Stanley--Wilf conjecture\/} (stated, for example, in B\'ona 
\cite{bona97}) asserts that for any given permutation $p$, 
\begin{equation}\label{SWC}
S_n(p)<c^n
\end{equation}
holds for every $n\in\N$ and a constant $c>1$ depending only on $p$. 
Using the general bound (\ref{muj}), Alon and Friedgut proved for every $p$ the upper bound 
\begin{equation}\label{AlFr}
S_n(p)<\beta_p(n)^n, 
\end{equation}
where $\beta_p(n)$ is an extremely slowly growing function defined in terms of $\alpha(n)$. Using the 
$N$-sequence bound (\ref{Nshaped}), they proved also that (\ref{SWC}) holds for all
unimodal $p$. (Recall that $p=a_1a_2\ldots a_m$ is  unimodal if it first decreases and then increases 
or vice versa.) B\'ona \cite{bona} proved that (\ref{SWC}) holds for all permutations $p$ of the form 
$p=a_1a_2\ldots a_m=s_1s_2\ldots s_k$ where the $s_i$'s are decreasing sequences 
and, for every $i$, all terms of $s_i$ are smaller than those of $s_{i+1}$.

\noindent
{\bf Example 9 (\cite{klaz00a}).} We give a simpler proof of the bound (\ref{AlFr}). We translate 
the problem from permutations to ordered bipartite graphs $\GG$ and work with the above described 
extremal function $f(n;\GG)$ and the permutation graphs $\GG_p$. 
Let, for a permutation $p$, $G_n(p)$ be the number of all ordered bipartite 
graphs $\GG=([n],[n+1,2n],H)$ such that $\GG\not\supset\GG_p$. Clearly, 
$$
S_n(p)\le G_n(p)
$$
because now we count many more $p$-free objects. Let us suppose that we have 
a bound $f(n;\GG_p)<n\gamma(n)$, where $\gamma(n)=\gamma_p(n)$ is a nondecreasing function. 
Let $n\in\N$ be 
fixed and $m=\lceil n/2\rceil$. We claim that
$$
G_n(p)<15^{m\gamma(m)}\cdot G_m(p).
$$
To prove this inductive inequality, we transform every $\GG=([n],[n+1,2n],H)$ 
counted by $G_n(p)$ to a 
$\GG'=([m],[m+1,2m],H')$ counted by $G_m(p)$. For $i\in[m]$ and $j\in[m+1,2m]$, we let 
$\{i,j\}\in H'$ iff in $\GG$ the sets $\{2i-1,2i\}$ and 
$\{2j-1,2j\}$ are connected by at least one edge. In other words, to get $\GG'$, we identify in 
$\GG$ the vertices in each of 
the pairs $(1,2), (3,4),\ldots$ and $(n+1,n+2),(n+3,n+4), \ldots$ and replace the arising 
multiple edges by simple edges. Every edge of $\GG'$ can be obtained in at 
most $2^{2\cdot 2}-1=15$ ways. Thus if $\GG'$ has $e$ edges, there are at most $15^e$ 
graphs $\GG$ that transform to $\GG'$. Also, $\GG\not\supset\GG_p$ implies 
$\GG'\not\supset\GG_p$, and therefore $e\le f(m;\GG_p)<m\gamma(m)$. Hence we obtain the inductive inequality.
Iterating it until $m=1$ and denoting $m_0=n,m_i=\lceil m_{i-1}/2\rceil$, we obtain the bound
$$
S_n(p)\le G_n(p)<2\cdot 15^{\sum_{i\ge 1}m_i\gamma(m_i)}<2\cdot 15^{\gamma(n)\sum_{i\ge 1}m_i}
<15^{2n\gamma(n)}=\left(225^{\gamma(n)}\right)^n.
$$

We have obtained (\ref{AlFr}) with $\beta_p(n)=225^{\gamma_p(n)}$. If $\gamma_p(n)$ is 
almost constant, so 
is $\beta_p(n)$. To find such a $\gamma_p(n)$, we reduce bipartite graphs to sequences. 
We associate with every
$\GG=([n],[n+1,2n],H)$ the sequence 
$u=N_1N_2\dots N_n\in[n+1,2n]^*$, where $N_i$ is the (arbitrarily ordered) list of the neighbours of 
$i\in[n]$ in $\GG$. Let $p$ be a fixed permutation of $[k]$. It follows that 
$\GG\not\supset\GG_p$ implies $u\not\supset w$ where 
$w=a_1a_2\dots a_ka_1a_2\dots a_k\dots a_1a_2\dots a_k$ consists of $2k$ repetitions of the 
segment of $k$ distinct symbols $a_1,\dots,a_k$. The problem that $u$ may not be $k$-sparse is 
easily fixed: deleting at most $k-1$ terms from the beginnings of $N_2,N_3,\dots,N_n$, 
we obtain a subsequence $v$ of $u$, $|v|\ge |u|-(k-1)(n-1)$, which is $k$-sparse. 
Invoking (\ref{muj}), we obtain the required bound:
\begin{eqnarray*}
|H|&=&|u|\le (k-1)(n-1)+|v|<kn+\ex(w,n)\\
 &<&kn+n\cdot k2^{l-3}\cdot (10k)^{2\alpha(n)^{l-4}+8\alpha(n)^{l-5}}=:n\gamma_p(n), 
\end{eqnarray*}
where $l=2k^2$.
\kduk

\noindent
{\bf Set partitions.} From the viewpoint of algebraic 
combinatorics, sequences can be regarded as set partitions. For example, $abcabc$ 
is the partition of $[6]$ in the blocks $\{1,4\}$, $\{2,5\}$, and 
$\{3,6\}$. Generally, we assign to a sequence $u=a_1a_2\ldots a_l$ of length $l$ the partition $P$
of $[l]$ such that $i$ and $j$ are in the same block of $P$ iff 
$a_i=a_j$. Then the set of blocks of mutually isomorphic sequences of length $l$ 
corresponds bijectively to the set of all partitions of $[l]$. Representing partitions by 
equivalence relations $\sim$, we can formulate the containment of sequences $\subset$
in the following way. A partition $u=([k],\sim_u)$ is contained in another partition 
$v=([l],\sim_v)$, 
if there is an {\em increasing\/} injection $f: [k]\rightarrow[l]$ such 
that the equivalence $x\sim_u y\iff f(x)\sim_v f(y)$ holds for every $x,y\in[k]$. 

An important and interesting class of partitions is the {\em noncrossing partitions\/}. 
A partition $P$
of $[l]$ is noncrossing, if there are no four numbers $1\le x_1<x_2<x_3<x_4\le l$ 
and no two distinct blocks $B_1$ and $B_2$ of $P$ such that 
$x_1,x_3\in B_1$ and $x_2,x_4\in B_2$. More 
briefly, $P$ is noncrossing if it does not contain $abab=\{\{1,3\},\{2,4\}\}$. Noncrossing partitions 
and $abab$-free sequences (4-DS sequences with 2-sparseness dropped) are two ways of looking at the 
same thing. Simion \cite{simi} wrote an interesting survey of results on noncrossing partitions 
and related topics. The seminal work introducing noncrossing 
partitions was that of Kreweras 
\cite{krew}, followed shortly by Poupard \cite{poup}. In the same year 1972, 
Mullin and Stanton published independently their article \cite{mull_stan} on enumeration 
of 4-DS sequences. Other enumerative works on 4-DS sequences are Roselle \cite{rose}, Gardy and 
Gouyou-Beauchamps \cite{gard_gouy}, and Klazar \cite{klaz96b}. See also Klazar \cite{klaz00b} 
for a more general approach to the enumeration of $u$-free set partitions. 

Although one can read in the MR review 
of \cite{klaz99} (with the main result (\ref{konst2})) that  
``The author improves previous results to show that the number $N\sb 5(n)$ [$\f_3(n)$]
of finite sequences$\;\ldots$'', unfortunately, to my knowledge, no significant enumerative results 
on 5-DS sequences are known. Some should be discovered! In this connection it is interesting that 
Alon and Onn \cite{alon_onn} applied in an enumerative problem (of bounding the numbers of separable 
partitions of points on the moment curve) the extremal bounds (\ref{DStrivi}) and (\ref{rose_stan}). 

\noindent
{\bf Problem 14.}
Let $r_l$ be the number of $ababa$-free partitions of $[l]$. In other words,
$$
r_l=\#\{u:\ u\not\supset ababa\;\&\;|u|=l\;\&\;u\mbox{ is normal}\}.
$$
What can be said about the numbers $r_l$? What is their asymptotics?
\kduk


\noindent
The numbers $r_l$ grow superexponentially. To see it, note that no partition of 
$[l]$ into blocks of at most two elements contains $ababa=\{\{1,3,5\},\{2,4\}\}$. Thus
$$ 
r_l\ge\sum_{i\ge 0}{\textstyle{l\choose 2i}}\cdot (2i-1)!!
$$
where $(2i-1)!!=1\cdot 3\cdot 5\cdot\dots\cdot(2i-1)$ and $(-1)!!=1$. 

Having in mind the variety of enumerative formulas for noncrossing partitions, we state the 
following problem.

\noindent
{\bf Problem 15.} 
Let $s_l$ be the number of $abcabc$-free partitions of $[l]$. In other words,
$$
s_l=\#\{u:\ u\not\supset abcabc\;\&\;|u|=l\;\&\;u\mbox{ is normal}\}.
$$
What can be said about the numbers $s_l$? What is their asymptotics?
\kduk


\noindent
The hypergraph bound (\ref{exppoc}) (proved in \cite{klaz00}) covers the partition case 
and implies that $s_l<c^l$ for a 
constant $c>1$. It is easy to see that $s_{k+l}\ge s_ks_l$ for every $k,l\in\N$. 
Hence $s_l^{1/l}$ tends to a finite limit. 

\vskip 30pt
\section*{\normalsize 6. Hypergraphs} 

\noindent
{\bf A hypergraph containment.} The containment of sequences discussed through this survey 
is a special 
case of the hypergraph containment introduced in Klazar \cite{klaz00}. In Section 6 we survey some  
of the results of \cite{klaz00} and \cite{klaz_pripr}.

A {\em hypergraph\/} $\HH=(E_i:\ i\in I)$ is a finite list of finite 
nonempty subsets $E_i$ of $\N=\{1,2,\ldots\}$, which are called {\em edges\/}. The edges may be repeated 
(we allow $E_i=E_j$ for $i\neq j$). {\em Simple\/} hypergraphs have no repeated edges. 
The elements 
of $\bigcup\HH=\bigcup_{i\in I} E_i\subset\N$ are called {\em vertices\/}. 
Hypergraphs include partitions as a special case: partitions are the hypergraphs with mutually 
disjoint edges. Now, for partitions we have the important notion of the sequential 
containment. Could not it be ``lifted'' to hypergraphs? We propose the 
following definition (\cite{klaz00,klaz_pripr}).

A hypergraph $\HH'=(E_i':\ i\in I')$ {\em is contained\/} in another hypergraph 
$\HH=(E_i:\ i\in I)$, in symbols $\HH'\subset\HH$, if there is an {\em increasing\/} injection 
$F:\bigcup\HH'\to\bigcup\HH$ and an injection $f: I'\to I$ such that 
the implication
$$
x\in E_i'\Longrightarrow F(x)\in E_{f(i)}
$$
holds for every vertex $x\in\bigcup\HH'$ and every index $i\in I'$. If $\HH'\not\subset\HH$, 
we say also that $\HH$ is $\HH'$-{\em free\/}. If $\HH'$ and $\HH$ are partitions, the hypergraph
containment coincides with the sequential containment. To help the reader to get used to the former,
we give two examples. Let $\HH_1=(E_1,E_2)$, $E_1=E_2=\{1\}$, be the hypergraph consisting 
of the singleton edge $\{1\}$ repeated twice. Then $\HH$ is $\HH_1$-free iff $\HH$ is a partition.
Let $\HH_2=(\{1,3\},\{2,4\})$. Then $\HH=(E_i:\ i\in I)\supset\HH_2$ iff there are four vertices 
$x_1,\dots,x_4\in\bigcup\HH$, $x_1<x_2<x_3<x_4$, and two (not necessarily distinct) edges $E_i,E_j$ 
in $\HH$, $i\neq j$, such that $x_1,x_3\in E_i$ and $x_2,x_4\in E_j$. ($\HH_2$-free hypergraphs 
generalize noncrossing partitions.)  

Let $\FF$ be a fixed hypergraph.  One can ask two extremely natural questions.  
First, how many $\FF$-free hypergraphs are there. Second, how large $\FF$-free hypergraphs 
may be.  We discuss first the enumerative aspect and then in more details the 
extremal aspect.   

\noindent
{\bf Exponential and almost exponential bounds.} For a fixed hypergraph $\FF$ and $n\in\N$, we are 
interested in the number 
$$
a(\FF,n)=\#\{\HH:\ \mbox{$\HH$ is simple}\;\&\;{\textstyle \bigcup\HH}=[n]\;\&\;\HH\not\supset\FF\}.
$$
The simplicity of $\HH$ is needed to make $a(\FF,n)$ finite. The forbidden hypergraph $\FF$, however, 
may be arbitrary, not necessarily simple. (If $\FF=\HH_1=(\{1\},\{1\})$ from the above example, 
$a(\FF,n)$ counts the partitions of $[n]$ and equals to the $n$th Bell number.)
One of the basic problems here is to determine all hypergraphs $\FF$ for which $a(\FF,n)<c^n$ for 
a constant $c>1$. The candidates for such $\FF$ are  the {\em permutation hypergraphs\/} 
$\HH_p$ (with added singleton edges); these are slightly modified graphs $\GG_p$. For a permutation 
$p=a_1a_2\ldots a_k$ of $[k]$ we define
$$
\HH_p=(\{i,k+a_i\}:\ i=1, \ldots, k). 
$$
For example, $\HH_{1,3,2}=(\{1,4\},\{2,6\},\{3,5\})$. 
If a hypergraph $\FF$ either (i) has an edge with at least 
three elements or (ii) has two intersecting edges or (iii) has two two-element edges $E_1$ and $E_2$ 
such that $E_1<E_2$, then every permutation hypergraph $\HH_p$ is $\FF$-free. Thus for 
such an $\FF$ we 
have
$$
a(\FF,n)\ge(\lfloor n/2\rfloor)!=\exp(({\textstyle{1\over 2}}+o(1))n\log n)
$$ 
and the numbers $a(\FF,n)$ grow superexponentially.
It is clear that $\FF$ satisfies neither of (i)--(iii) if and only if it is a disjoint union of several 
singleton edges and a hypergraph isomorphic to some $\HH_p$. We say 
briefly that $\FF$ is of the form $\HH_p+${\em singletons\/}. For example, we may have  
$$
\FF=(\{1\},\{3\},\{7\},\{2,9\},\{4,6,\},\{5,8\}).
$$
We conjecture that $a(\FF,n)<c^n$ if and only if, for some permutation $p$, $\FF=\HH_p$+singletons. 
This strengthens the Stanley--Wilf conjecture.   

To prove our conjecture, it is enough to prove $a(\HH_q,n)<c^n$ for every permutation $q$; every $\HH_p$+singletons is contained in an appropriate $\HH_q$.  

\noindent
{\bf Problem 16.} Prove (or disprove) that for any given permutation $p$, 
$$
a(\HH_p,n)<c^n
$$
holds for every $n\in\N$ and a constant $c>1$.
\kduk


\noindent 
In \cite{klaz00} we proved, using (\ref{muj}), a slightly weaker bound: for every permutation $p$ 
there is an almost constant function $\beta_p(n)$ defined in terms of the inverse Ackermann function 
$\alpha(n)$, such that 
\begin{equation}\label{enumDS}
a(\HH_p,n)<\beta_p(n)^n.
\end{equation}
Note that this strengthens (\ref{AlFr}) (and our strengthening of (\ref{AlFr}) in Example 9) 
because now we count many more $p$-free objects. In \cite{klaz00} 
we also proved, using the $N$-sequence bound (\ref{Nshaped}), that the exponential 
bound in Problem 16 holds for certain permutations: if $p=a_1a_2\dots a_k$ first 
dicreases and then increases, or if $p^{-1}$ first increases and then dicreases, 
then
\begin{equation}\label{exppoc}
a(\HH_p,n)<c^n
\end{equation}
for all $n\in\N$ and a constant $c>1$. Note that this gives an exponential upper bound on the 
numbers $s_l$ of Problem 15 ($p=1,2,3$). Can the reader give a reasonably 
simple direct proof of it?  

Summarizing, we have the enumerative alternative
\begin{eqnarray}\label{enumealter}
a(\FF,n)\ \left\{
\begin{array}{lll}
<\beta_p(n)^n & \ldots & \FF\subset\HH_p\mbox{ for some $p$}\\
 & & \\
>n^{(1/2+o(1))n} & \ldots & 
\FF\not\subset\HH_p\mbox{ for every $p$,}
\end{array}
\right\}
\end{eqnarray}
we conjecture that $\beta_p(n)$ may be replaced with a constant, and can prove this 
for some particular permutations $p$.

\noindent
{\bf Two hypergraph extremal functions.} For a hypergraph $\HH=(E_i:\ i\in I)$, we denote by 
$v(\HH)=|\bigcup\HH|$ the number of vertices, by $e(\HH)=|I|$ the number of edges, and 
by $i(\HH)=\sum_{i\in I}|E_i|$ the number of vertex-edge incidences.
For a fixed hypergraph $\FF$ and $n\in\N$, we define two extremal functions 
\begin{eqnarray*}
H_e(\FF,n)&=&\max\{e(\HH):\ \HH\not\supset\FF\;\&\;\mbox{$\HH$ is simple}\;\&\;v(\HH)\le n\}\\
H_i(\FF,n)&=&\max\{i(\HH):\ \HH\not\supset\FF\;\&\;\mbox{$\HH$ is simple}\;\&\;v(\HH)\le n\}.
\end{eqnarray*}
The simplicity of $\HH$ is again needed that $H_e(\FF,n)$ and $H_i(\FF,n)$ be well defined. The 
forbidden $\FF$ may be arbitrary. Obviously, $H_e(\FF,n)\le H_i(\FF,n)$ for every $\FF$ and $n$. 
In most cases we have, up to a constant factor, also the opposite inequality:

\noindent
{\bf Example 10 (\cite{klaz_pripr}).}
Suppose that no two edges $E_1$ and $E_2$ of $\FF$ satisfy $E_1<E_2$. Let $p=v(\FF)$ and $q=e(\FF)>1$ 
(the case $q=1$ is trivial). Then for every $n\in\N$,
\begin{equation}\label{jednoducha}
H_i(\FF,n)\le (2p-1)(q-1)\cdot H_e(\FF,n).
\end{equation}

For the proof suppose that $\HH$ is a simple and $\FF$-free hypergraph with 
$v(\HH)\le n$. We transform $\HH$ in a new hypergraph $\HH'$. If $E=\{v_1,v_2,\ldots,v_s\}$ is an 
edge of $\HH$, $v_1<v_2<\cdots<v_s$, we keep it if $s<p$. If $s\ge p$, we replace $E$ with  
$t=\lfloor |E|/p\rfloor$ new edges $\{v_1,\ldots,v_p\}$, $\{v_{p+1},\ldots,v_{2p}\},\ldots,$ 
$\{v_{(t-1)p+1},\ldots,v_{tp}\}$. The new edges have each $p$ elements and are mutually separated 
in the way that is excluded in $\FF$. The new hypergraph $\HH'$ may not be simple. Therefore 
we define a simple hypergraph $\HH''$ by keeping from every family of 
repeated edges of $\HH'$ only one edge. We observe two things: (i) no edge of 
$\HH'$ is repeated more than $q-1$ times and (ii) $\HH''$ is $\FF$-free. If (i) were 
false, there would be $q$ distinct edges $E_1,\ldots,E_q$ in $\HH$ such that 
$|\bigcap_{i=1}^q E_i|\ge p$. But this implies the contradiction 
$\FF\subset\HH$. As for (ii), since the new $p$-element edges born from an edge $E$ of $\HH$ 
are separated, every copy of $\FF$ in $\HH''$ may use for every $E$ only at most one of them. 
But then it would be a copy 
of $\FF$ in $\HH$ as well, which is again impossible. 
Both observations and the definitions of $\HH'$ and $\HH''$ imply
\begin{eqnarray*}
i(\HH)&\le& {(2p-1)\cdot i(\HH')\over p}\le {(2p-1)(q-1)\cdot i(\HH'')\over p}\\
&\le& (2p-1)(q-1)\cdot e(\HH'')\\
&\le& (2p-1)(q-1)\cdot H_e(\FF,n).
\end{eqnarray*}
\vskip -36pt
\kduk


The inequality (\ref{jednoducha}) holds, for example, for all permutation hypergraphs 
$\FF=\HH_p$. On the other hand, there exists a class of somewhat singular hypergraphs $\FF$ for which 
$H_i(\FF,n)\not\ll H_e(\FF,n)$. For $\FF=(\{1\},\{2\})$ one can 
quickly show 
that $H_e(\FF,n)=1$ but $H_i(\FF,n)=n$. More generally, in \cite{klaz_pripr} we have shown that 
if $\FF=(\{1\},\{2\},\ldots,\{k\})$ then 
$H_e(\FF,n)=2^{k-1}-1$ ($n\ge k-1$) and $H_i(\FF,n)=(k-1)n-(k-2)$ ($n$ is 
large enough). 

\noindent
{\bf Problem 17.} 
Is it true that for every $\FF\neq (\{1\},\{2\},\ldots,\{k\})$ one has the estimate 
$H_i(\FF,n)\ll_{\FF} H_e(\FF,n)$?
\kduk

\noindent
{\bf Linear and almost linear bounds on $\mathbf{H_i(\FF,n)}$.} In \cite{klaz00} we proved, 
by means of 
(\ref{muj}), 
an extremal analogue of (\ref{enumDS}): for every permutation $p$,
\begin{equation}\label{extrDS}
H_i(\HH_p,n)<n\cdot\gamma_p(n)
\end{equation} 
where $\gamma_p(n)$ is defined in terms of $\alpha(n)$ and thus grows 
to infinity extremely slowly. (This proof now may be simplified by means of the inequality (\ref{jednoducha}).) Similarly, in \cite{klaz00} we proved, by means of (\ref{Nshaped}), that 
if $p=a_1a_2\dots a_k$ is a permutation that first dicreases and then increases, or 
if $p^{-1}$ first increases and then dicreases, then 
\begin{equation}\label{linhyp}
H_i(\HH_p,n)\ll_p n.
\end{equation}

\noindent
{\bf Problem 18.} 
Prove (or disprove) that for every permutation $p$ we have 
$H_i(\HH_p,n)\ll_p n$.
\vskip -7pt
{\hfill \kduk}


We have seen already in Example 9 that the extremal problem is, in a sense, more fundamental than the 
enumerative problem. This holds also on the hypergraph level: in \cite{klaz00} we prove first the bounds (\ref{extrDS}) and (\ref{linhyp}) and from them we 
derive, respectively, the bound (\ref{enumDS}) and (\ref{exppoc}) as corollaries. 
The derivation uses a variant of the inductive argument presented in 
Example 9. In the same vein, the bound in Problem 18 implies the bound in Problem 
16. 

What is the extremal analogue of (\ref{enumealter})? 

\noindent
{\bf Problem 19.}
Identify the class of hypergraphs $\Psi$ such that 
$$
H_e(\FF,n), H_i(\FF,n)\ \left\{
\begin{array}{lll}
<n\cdot \gamma_{\FF}(n) & \ldots & \FF\in\Psi\\
 & & \\
>n\cdot \delta_{\FF}(n) & \ldots & 
\FF\not\in\Psi
\end{array}
\right.
$$
holds. Here the functions $\gamma_{\FF}(n)$ and $\delta_{\FF}(n)$ grow to 
infinity, any $\gamma_{\FF}(n)$ is defined 
in terms of $\alpha(n)$ and thus is almost constant, and any $\delta_{\FF}(n)$ is much faster than 
any $\gamma_{\FF}(n)$. 
\kduk

\noindent
Unlike in enumeration, now we cannot hope to replace every $\gamma_{\FF}(n)$ with a constant. This, 
of course, comes as no surprise. By a reduction to 5-DS sequences, it is easily shown 
(\cite{klaz_pripr}) that for $\FF=(\{1,3\},\{1,5\},\{2,4\},\{2,6\})$ one has $H_e(\FF,n)\gg n\alpha(n)$. 
This $\FF$ is an example of a {\em star forest\/}. These are simple hypergraphs $\FF$ with only two-element 
edges, with no cycles, and with the components forming stars such that all centers of the stars precede 
all endvertices. In \cite{klaz_pripr} we proved that for every star forest $\FF$,
\begin{equation}\label{starf}
H_i(\FF,n)<n\cdot\gamma_{\FF}(n)
\end{equation}
where $\gamma_{\FF}(n)$ is an almost constant function defined in terms of $\alpha(n)$. Note that by (\ref{jednoducha}), it suffices to prove this bound for $H_e(\FF,n)$. 
So, in Problem 19, the class $\Psi$ must contain all star forests. Does it consist 
only from star forests? Since star forests generalize 
permutation hypergraphs $\HH_p$, the bound (\ref{starf}) generalizes the bound (\ref{extrDS}). However, (\ref{extrDS}) can be probably improved to a $\ll n$ 
bound. 

\noindent
{\bf One more almost linear bound and back to $\mathbf{abab}$.}
In the definition (\ref{obextrfcedef}), if expressed in terms of partitions, 
the number of vertices is maximized over all $v$-free partitions $u$ with at most
$n$ edges (and $u$ is moreover $\|v\|$-sparse). For partitions $\HH$ we have 
$v(\HH)=i(\HH)$ but the proper measure of size for hypergraphs is $i(\HH)$. 
We generalize the approach of (\ref{obextrfcedef}) as follows. Suppose that 
$\FF$ is a fixed partition with $q=e(\FF)>1$. Then for every $\FF$-free hypergraph $\HH$ 
(really every, even not simple) we have the inequality (\cite{klaz_pripr})
\begin{equation}\label{vahaahrany}
i(\HH)<(q-1)v(\HH)+e(\HH)\cdot\gamma_{\FF}(e(\HH))
\end{equation}
where $\gamma_{\FF}(n)$ is an almost constant function defined in terms of $\alpha(n)$. The bound 
(\ref{vahaahrany}) is an extension of (\ref{muj}) to hypergraphs. We can also apply (\ref{vahaahrany})
to bound $H_i(\FF,n)$ (almost linearly) in terms of $H_e(\FF,n)$ in situations when
(\ref{jednoducha}) does not apply. 

We conclude our survey by returning to the pattern $abab$, alias 
\makebox[1.5cm]{$\bullet\hskip-1.7mm-\hskip-1.7mm\circ\hskip-1.7mm-\hskip-1.7mm
\bullet\hskip-1.7mm-\hskip-1.7mm\circ$}, alias $(\{1,3\},$ $\{2,4\})$.

\noindent
{\bf Example 11 (\cite{klaz00,klaz_pripr}).} 
We prove that, denoting $abab=(\{1,3\},\{2,4\})$, for every $n>1$, 
$$
H_e(abab,n)=4n-5\ \mbox{ and }\ H_i(abab,n)=8n-12.
$$

We begin with the case when $\GG$ is a simple $abab$-free graph with the vertex set 
$[n]$ (so $\GG$ has only two-element edges). We prove by induction on $n$ that 
$e(\GG)\le 2n-3$. For $n=2$ this is true. Let $n>2$ and $\deg(1)\ge 2$; for $\deg(1)=1$ induction immediately 
applies. We split $[n]$ into two overlapping intervals $I_1=[k]$ and 
$I_2=[k,n]$, where $k$ is the largest vertex in $[2,n-1]$ adjacent to $1$. The restrictions of 
$\GG$ to $I_1$ and $I_2$ are simple $abab$-free graphs and every 
edge of $\GG$, except possibly of $\{1,n\}$, lies in $I_1$ or in $I_2$. By induction, 
$$
e(\GG)\le 1+2|I_1|-3+2|I_2|-3=2(|I_1|+|I_2|)-5=2n-3.
$$
In the graph case, $e(\GG)\le 2v(\GG)-3$. 

Let now $\HH$ be a simple $abab$-free hypergraph with the vertex set $[n]$. We look 
at the {\em big\/} edges of $\HH$ having 3 and more vertices. We claim that after deleting 
from each of them its first and last vertex, the resulting sets lie  in $[2,n-1]$ and are 
mutually disjoint. The former claim is clear. If the resulting sets were not 
disjoint, we would have two distinct edges $E_1,E_2$ in $\HH$ 
and five not necessarily distinct vertices $v_1, \ldots, v_5\in\bigcup\HH$ such that 
$v_2<v_3<v_4$, $v_1<v_3<v_5$, $\{v_1,v_3,v_5\}\subset E_1$, and $\{v_2,v_3,v_4\}\subset E_2$.
Moreover, we may assume that $v_1\neq v_2$ or $v_4\neq v_5$ because 
$E_1\neq E_2$ ($\HH$ is simple). But then $\HH$ contains $abab$, 
a contradiction. Thus the resulting sets must be disjoint and their number 
is at most $n-2$, which bounds the number of big edges in $\HH$. 

Not forgetting singleton edges, we conclude that 
\begin{eqnarray*}
e(\HH)&\le& n+(2n-3)+(n-2)=4n-5\\
i(\HH)&\le& n+2(2n-3)+(n-2)+2(n-2)=8n-12.
\end{eqnarray*}
The $abab$-free hypergraphs
$$
(\{i\},\{j,j+1\},\{1,k\},\{1,j,j+1\}:\ i\in[n],j\in[2,n-1], k\in[2,n])
$$
show that these bounds are tight.
\kduk


\noindent
Interestingly, the previous proof needs only small adjustments to work also for the forbidden 
hypergraph 
$abba=(\{1,4\},\{2,3\})$. For $n>1$ we have $H_e(abba,n)=4n-5$ and $H_i(abba,n)=8n-12$ as well.
This should be compared with the situation for sequences and colored trees when $abab$ and $abba$ 
have different extremal functions. 

\vskip 30pt
\noindent
{\bf Acknowledgments.} I am indebted to Ji\v r\'\i\ Matou\v sek for 
reading the manuscript and for his comments. I am also grateful to an 
anonymous referee for going through the not so short manuscript and for 
many valuable comments that helped me to improve its readability. 

\begin{thebibliography}{99}
{\footnotesize  

\bibitem{adam_klaz_valt}
\claprv{R. Adamec, M. Klazar and P. Valtr}{Generalized Davenport--Schinzel sequences with linear upper bound}{Discrete 
Mathematics}{108}{1992}{219--229}{768.05007}{93k:05015}

\bibitem{agar_al} \cla{P. K. Agarwal, B. Aronov, J. Pach, R. Pollack and 
M. Sharir}{Quasi-planar graphs have a linear number 
of edges}{Combinatorica}{17}{1997}{1--9}{880.05050}{98f:05046}

\bibitem{agar_shar}\vsbo{P. K. Agarwal and M. Sharir}{Davenport--Schinzel 
sequences and their geometric applications}{1--47}{J.-R. Sacks and 
J. Urrutia}{Handbook of Computational Geometry}{Elsevier}{Amsterdam,  
2000}{991.24846}{CMP 1 746 674}

\bibitem{agar_shar_shor} \cla{P. K. Agarwal, M. Sharir and P. Shor}{Sharp upper and lower bounds on 
the length of general Davenport--Schinzel sequences}{Journal of Combinatorial Theory, 
Series A}{52}{1989}{228--274}{697.05003}{90m:11034}
%popsano

\bibitem{alon_frie}
\cla{N. Alon and E. Friedgut}{On the number of permutations 
avoiding a given pattern}{J. Comb. Theory, 
Ser. A}{89}{2000}{133--140}{991.47660}{2000i:05007}

\bibitem{alon_onn}
\cla{N. Alon and S. Onn}{Separable partitions}{Discrete 
Applied Mathematics}{91}{1999}{39--51}{926.05011}{2000j:05010}

\bibitem{atal}
\cla{M. I. Atallah}{Some dynamic computational geometry 
problems}{Computers and Mathematics with 
Applications}{11}{1985}{1171--1181}{586.68085}{87b:68095}
%popsano

\bibitem{avir_onn}
\cla{S. Aviran and S. Onn}{Momentopes, the complexity of vector 
partitioning, and Davenport-Schinzel 
sequences}{Discrete and Computational Geometry}{27}{2002}{409--417}{}{}

\bibitem{davecoll}
{\sc  B. J. Birch, H. Halberstam and C. A. Rogers } (editors), {\it 
The Collected Works of Harold Davenport. Volume IV, } Academic Press, London, 1977. [Zbl 383.01022 and MR 58\#27141.]
%popsano

\bibitem{bona97}
\cla{M. B\'ona}{Exact enumeration of $1342$-avoiding permutations: a close 
link with labeled trees and planar maps}{J. Comb. Theory, 
Ser. A}{80}{1997}{257--272}{0887.05004}{98j:05003}

\bibitem{bona}
\cla{M. B\'ona}{The solution of a conjecture of Stanley and Wilf 
for all layered patterns}{J. Comb. Theory, 
Ser. A}{85}{1999}{133--140}{919.05002}{99i:05005}

\bibitem{burk_eckl}
\vsbo{F. J. Burkowski and E. F. Ecklund, Jr.}{Exclusion sequences with 
regularity conditions}{261--266}{F. Hoffman et al.}{The Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton 1974 
(USA), Congressus Numerantium X}{Utilitas Mathematica Publishing, Inc.}{Winnipeg, 1974}{313.05004}{52\#2901}
%popsano

\bibitem{dave}
\cla{H. Davenport}{A combinatorial problem connected with 
differential equations II}{Acta Arithmetica}{17}{1971}{363--372}{216.30204}{44\#2619}
%popsano

\bibitem{dave_schi65a}
\cla{H. Davenport and A. Schinzel}{A combinatorial problem connected 
with differential equations}{American Journal of  
Mathematics}{87}{1965}{684--694}{132.00601}{32\#7426}
%popsano

\bibitem{dave_schi65b}
\cla{H. Davenport and A. Schinzel}{A note on sequences and 
subsequences}{Elemente der Mathematik}{20}{1965}{63--64}{132.25101}{--- not reviewed}
%popsano

\bibitem{dobs_macd}
\cla{A. J. Dobson and S. O. Macdonald}{Lower bounds for the lengths 
of Davenport--Schinzel sequences}{Utilitas 
Mathematica}{6}{1974}{251--257}{299.05010}{50\#9781}
%popsano

\bibitem{edel_shar}
\cla{H. Edelsbrunner and M. Sharir}{The maximum number of ways to stab 
$n$ convex nonintersecting sets in the plane is $2n-2$}{Discrete 
 Comput. Geom.}{5}{1990}{35--42}{712.52009}{90k:52019}

\bibitem{fure_hajn}
\cla{Z. F\"uredi and P. Hajnal}{Davenport--Schinzel theory 
of matrices}{Discrete Math.}{103}{1992}{233--251}{776.05024}{93g:05026}

\bibitem{gard_gouy}
\cla{D. Gardy and D. Gouyou-Beauchamps}{Enumerating 
Davenport-Schinzel sequences}{RAIRO. Informatique Th\'eorique et Applications}{26}{1992}{387--402}{769.05007}{93k:05011}

\bibitem{guy}
{\sc R. K. Guy,} {\it Unsolved Problems in Number Theory, } 
Springer, Berlin, 1981. [Zbl 474.10001 and MR 83k:10002.] 
(Second edition appeared in 1994.)
%popsano

\bibitem{hart_shar}
\cla{S. Hart and M. Sharir}{Nonlinearity of Davenport--Schinzel sequences and 
of generalized path compression 
schemes}{Combinatorica}{6}{1986}{151--177}{636.05003}{88f:05004}
%popsano
%Web of science udava (kveten 2002) 114 citaci tohoto clanku.

\bibitem{katc_last}
\cla{M. Katchalski and H. Last}{On geometric graphs with no two edges in 
convex position}{Discrete Comput. 
Geom.}{19}{1998}{399--404}{908.05033}{99d:52015}

\bibitem{klaz92}
\cla{M. Klazar}{A general upper bound in extremal theory 
of sequences}{Commentationes Mathematicae Universitatis 
Carolinae}{33}{1992}{737--746}{781.05049}{94g:05095}
%popsano

\bibitem{klaz93}
\cla{M. Klazar}{Two results on a partial ordering of 
finite sequences}{Commentat. Math. Univ. 
Carol.}{34}{1993}{697--705}{789.05090}{95i:05108}

\bibitem{klaz94}
\cla{M. Klazar}{A linear upper bound in extremal theory 
of sequences}{J. Comb. Theory, Ser. A}{68}{1994}{454--464}{808.05096}{95m:11033}

\bibitem{klaz_phd}
{\sc M. Klazar}, {\em Combinatorial Aspects of Davenport--Schinzel 
  Sequences}, Ph.D. thesis, Charles University, Prague, 1995.

\bibitem{klaz96a}
\cla{M. Klazar}{Extremal functions for sequences}{Discrete 
Math.}{150}{1996}{195--203}{851.05093}{97c:05019}

\bibitem{klaz96b}
\cla{M. Klazar}{On $abab$-free and $abba$-free set 
partitions}{European Journal of 
Combinatorics}{17}{1996}{53--68}{840.05004}{96j:05019}

\bibitem{klaz97}
\cla{M. Klazar}{Combinatorial aspects of Davenport--Schinzel 
  sequences}{Discrete 
Math.}{165-166}{1997}{431--445}{948.05008}{98d:05149}

\bibitem{klaz99a}
\cla{M. Klazar}{Extremal problems for colored trees and 
Davenport-Schinzel sequences}{Discrete 
Math.}{197-198}{1999}{469--482}{936.05060}{99k:05004}

\bibitem{klaz99}
\vsbo{M. Klazar}{On the maximum lengths of Davenport--Schinzel 
sequences}{169--178}{R. L. Graham et al.}{Contemporary Trends in 
Discrete Mathematics, \v Sti\v r\'\i n Castle 1997 (Czech Republic)}{American Mathematical Society}{Providence RI, 1999}{938.05004}{2000h:11023}

\bibitem{klaz00b}
\cla{M. Klazar}{Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind}{Eur. J. 
Comb.}{21}{2000}{367--378}{ 0946.05004}{2000m:05007}

\bibitem{klaz00}
\cla{M. Klazar}{Counting pattern-free set partitions. II: Noncrossing and 
other hypergraphs}{Electronic Journal of Combinatorics}{7}{2000}{R34}{944.05002}{2000m:05007}

\bibitem{klaz00a}
\vsbo{M. Klazar}{The F\"uredi--Hajnal conjecture implies the Stanley--Wilf conjecture}{250--255}{D. Krob, A. A. Mikhalev and 
A. V. Mikhalev}{Formal Power Series and Algebraic Combinatorics, Moscow 2000 (Russia)}{Springer}{Berlin, 2000}{954.05048}{2001k:05005}

\bibitem{klaz_pripr}
{\sc M. Klazar,} Extremal problems (and a bit of enumeration) for 
hypergraphs with linearly ordered vertex sets, {\it ITI Series} 2001-021, technical report, 40 pages.

\bibitem{klaz_valt}
\cla{M. Klazar and P. Valtr}{Generalized Davenport--Schinzel sequences}{Combinatorica}{14}{1994}{463--476}{812.05067}{96h:05206}

\bibitem{komj}
\cla{P. Komj\'ath}{A simplified construction of nonlinear 
Davenport--Schinzel sequences}{J. Comb. Theory, 
Ser. A}{49}{1988}{262--267}{673.05001}{89m:11019}
%popsano

\bibitem{krew}
\cla{G. Kreweras}{Sur les partitions non crois\'ees d'un 
cycle}{Discrete Math.}{1}{1972}{333--350}{231.05014}{46\#8852}

\bibitem{loeb_nese}
\vsbor{M. Loebl and J. Ne\v set\v ril}{Fast and slow growing (a 
combinatorial study of unprovability)}{119--160}{A. D. Keedwell}{Surveys 
in Combinatorics, 1991}{Cambridge University Press}{Cambridge, UK, 
1991}{735.03017}{93d:03061} (London Mathematical Society Lecture Note 
Series, 166.)

\bibitem{mill73}
\vsbo{W. H. Mills}{Some Davenport--Schinzel sequences}{307--314}{R. S. D. 
Thomas and H. C. Williams}{The 3rd Manitoba Conference on Numerical 
Mathematics, Winnipeg 1973 (USA), Congressus 
Numerantium IX}{Utilitas Mathematica 
Publishing Inc.}{Winnipeg, 1974}{321.05006}{50\#135}
%popsano

\bibitem{mill76}
\cla{W. H. Mills}{On Davenport--Schinzel sequences}{Utilitas 
Math.}{9}{1976}{87--112}{337.05006}{53\#10703}

\bibitem{mull_stan}
\cla{R. C. Mullin and R. G. Stanton}{A map-theoretic approach 
to Davenport--Schinzel sequences}{Pacific Journal of 
Mathematics}{40}{1972}{167--172}{233.05013 }{46\#1745}
%popsano

\bibitem{pach_shah_szeg}
\cla{J. Pach, F. Shahrokhi and M. Szegedy}{Applications of the 
crossing number}{Algorithmica}{16}{1996}{111--117}{0851.68088}{97h:05054}

\bibitem{pete}
\vsbo{C. R. Peterkin}{Some results on Davenport--Schinzel 
sequences}{337--344}{R. S. D. Thomas and H. C. Williams}{The 3rd Manitoba Conference on Numerical Mathematics, Winnipeg 1973 (USA), Congressus 
Numerantium IX}{Utilitas Mathematica 
Publishing Inc.}{Winnipeg, 1974}{324.05008}{50\#136}
%popsano

\bibitem{poup}
\cla{Y. Poupard}{\'Etude et d\'enombrement parall\`eles des partitions 
non crois\'ees d'un cycle et des d\'ecoupages d'un polygone 
convexe}{Discrete Math.}{2}{1972}{279--288}{252.05005}{46\#3369}

\bibitem{renn_dobs}
\cla{B. C. Rennie and A. J. Dobson}{Upper bounds for the lengths 
of Davenport--Schinzel sequences}{Utilitas 
Math.}{8}{1975}{181--185}{364.05004}{52\#13624}
%popsano

\bibitem{rose}
\cla{D. P. Roselle}{An algorithmic approach to 
Davenport--Schinzel sequences}{Utilitas 
Math.}{6}{1974}{91--93}{306.05010}{50\#9780}

\bibitem{rose_stan70}
\vsbo{D. P. Roselle and R. G. Stanton}{Results on 
Davenport--Schinzel sequences}{249--267}{R. Mullin, K. B. Reid and D. P. Roselle}{Louisiana Conference on Combinatorics, Graph Theory and Computing, Baton Rouge 1970 
(USA)}{Louisiana State University}{Baton Rouge, 1970}{239.05004}{43\#68}
%popsano

\bibitem{rose_stan71}
\cla{D. P. Roselle and R. G. Stanton}{Some properties of 
Davenport--Schinzel sequences}{Acta 
Arith.}{17}{1971}{355--362}{215.33203}{44\#1641}
%popsano

\bibitem{shar87}
\cla{H. Sharir}{Almost linear upper bounds on the length of general 
Davenport--Schinzel 
sequences}{Combinatorica}{7}{1987}{131--143}{636.05004}{89f:11037}
%popsano

\bibitem{shar88}
\cla{H. Sharir}{Improved lower bounds on the length of 
Davenport--Schinzel 
sequences}{Combinatorica}{8}{1988}{117--124}{672.05015}{89j:11024}
%popsano

\bibitem{shar_agar}
{\sc M. Sharir and P. K. Agarwal,} {\it Davenport--Schinzel Sequences and Their Geometric Applications, } Cambridge University Press, Cambridge, UK, 1995. 
[Zbl 834.68113 and MR 96e:11034.]

\bibitem{simi}
\cla{R. Simion}{Noncrossing partitions}{Discrete 
Math.}{217}{2000}{367--409}{959.05009}{2001g:05011}

%\bibitem{simi_schm}
%\cla{R. Simion and F. Schmidt}{Restricted permutations}{Eur. J. 
%Comb.}{6}{1985}{383--406}{615.05002}{88a:05006}

\bibitem{sloa}
{\sc N. J. A. Sloane} (2000), The On-Line Encyclopedia of Integer 
Sequences, published electronically at
      http://www.research.att.com/\~{}njas/sequences/.

\bibitem{stan_dirk}
\cla{R. G. Stanton and P. H. Dirksen}{Davenport--Schinzel 
sequences}{Ars Combinatoria}{1}{1976}{43--51}{335.05001}{53\#13106}
%popsano

\bibitem{stan_rose}
\vsbo{R. G. Stanton and D. P. Roselle}{A result on 
Davenport--Schinzel sequences}{1023--1027}{P. Erd\H os, 
A. R\'enyi and V. T. S\'os}{Combinatorial Theory and Its Applications, 
Balatonf\"ured 1969 (Hungary), Colloquia Mathematica 
Societatis J\'anos Bolyai 4, Vol. II}{Nort-Holland}{Amsterdam, 1970}{215.33202}{46\#3324}
%popsano

\bibitem{szem}
\cla{E. Szemer\'edi}{On a problem of Davenport and 
Schinzel}{Acta  Arith.}{25}{1974}{213--224}{291.05003}{49\#244}
%popsano

\bibitem{tarj}
\cla{R. E. Tarjan}{Efficiency of a good but not linear set 
union algorithm}{Journal of the Association for Computing Machinery}{22}{1975}{215--225}{307.68029 }{56\#17194}
%popsano, ale co to je za casopis?

\bibitem{valt97}
\vsbor{P. Valtr}{Graph drawing with no $k$ pairwise crossing 
edges}{205--218}{G. DiBattista}{Graph Drawing'97, Rome 1997 
(Italy)}{Springer}{Berlin, 1997}{--- not reviewed}{99e:68166} 
(Lecture Notes in Computer Science, 1353.)

\bibitem{valt98}
\cla{P. Valtr}{On geometric graphs with no $k$ pairwise 
parallel edges}{Discrete 
Comput. Geom.}{19}{1998}{461--469}{908.05035}{99a:05138}

\bibitem{valt99}
\vsbo{P. Valtr}{Generalizations 
of Davenport--Schinzel sequences}{349--389}{R. L. Graham et al.}{Contemporary Trends in 
Discrete Mathematics, \v Sti\v r\'\i n Castle 1997 (Czech Republic)}{American Mathematical Society}{Providence RI, 1999}{942.68104}{2001d:68185}

\bibitem{valt99a}
\cla{P. Valtr}{On an extremal problem for colored trees}{Eur. J. 
Comb.}{20}{1999}{115--121}{924.05040}{99k:05061}

\bibitem{valt_subm}
{\sc P. Valtr, } Davenport--Schinzel trees, submitted.

\bibitem{wier_shar}
\cla{A. Wiernik and M. Sharir}{Planar realizations of nonlinear Davenport--Schinzel sequences by segments}{Discrete Comput. Geom.}{3}{1988}{15--47}{636.68043}{89h:11088}
%popsano

\bibitem{webs}
http://www.isinet.com/isi/
}

\end{thebibliography}



\end{document}