%A LaTeX file for a 25 page document
\documentclass[12pt]{article}
\usepackage{latexsym}
\sloppy
\addtolength{\textwidth}{20mm}
\addtolength{\oddsidemargin}{-13mm}
\addtolength{\textheight}{30mm}
\addtolength{\topmargin}{-12mm}
\newenvironment{duk}{{\bf Proof.}\ }{ \hfill $\Box$ \par \bigskip }
\newcommand{\N}{{\mathbf N}}
\newcommand{\HH}{{\cal H}}
\newcommand{\TT}{{\cal T}}
\newcommand{\GG}{{\cal G}}
\newcommand{\RR}{{\cal R}}
\newcommand{\NN}{{\cal N}}
\newtheorem{veta}{Theorem}[section]
\newtheorem{lema}[veta]{Lemma}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000), \#R34\hfill}
\thispagestyle{empty}
\begin{document}
\begin{center}
{\Large\bf Counting Pattern-free Set Partitions II:
\smallskip
Noncrossing and Other Hypergraphs}
\bigskip
{\large Martin Klazar}
\bigskip
Department of Applied Mathematics\\
Charles University\\
Malostransk\'e n\'am\v est\'\i\ 25, 118 00 Praha\\
Czech Republic\\
{\tt klazar@kam.ms.mff.cuni.cz}
\bigskip
Submitted: January 28, 2000; Accepted: May 23, 2000.
\bigskip
Dedicated to the memory of Rodica Simion
\end{center}
\begin{abstract}
A (multi)hypergraph $\HH$ with vertices in
$\N$ contains a permutation $p=a_1a_2\ldots a_k$ of
$1, 2, \ldots, k$ if one can reduce $\HH$ by omitting vertices from
the edges so that the resulting hypergraph is isomorphic, via an increasing mapping, to
$\HH_p=(\{i, k+a_i\}:\ i=1, \ldots, k)$. We formulate six conjectures stating
that if $\HH$ has $n$ vertices and does not contain $p$ then the size of $\HH$ is $O(n)$ and the number
of such $\HH$s is $O(c^n)$. The latter part generalizes the Stanley--Wilf
conjecture on permutations.
Using generalized Davenport--Schinzel sequences,
we prove the conjectures with weaker bounds $O(n\beta(n))$ and $O(\beta(n)^n)$,
where $\beta(n)\rightarrow\infty$ very slowly. We prove the conjectures fully
if $p$ first increases and then decreases or if $p^{-1}$ decreases and then increases. For the cases $p=12$ (noncrossing structures) and $p=21$
(nonnested structures) we
give many precise enumerative and extremal results, both for graphs and hypergraphs.
\bigskip\noindent
2000 MSC: Primary 05A05, 05A15, 05A18, 05C65, 05D05; Secondary: 03D20, 05C30,
11B83.
\bigskip\noindent
Support of the grant GAUK 158/99 is gratefully acknowledged.
\end{abstract}
\newpage
\section{Notation, conjectures, and motivation}
We shall investigate numbers and sizes of
pattern-free hypergraphs.
A {\em hypergraph\/} $\HH$ is a finite multiset of finite nonempty subsets of
$\N=\{1, 2, \ldots\}$. More explicitly, $\HH=(H_i:\ i\in I)$ where the
{\em edges\/} $H_i, \emptyset\neq H_i\subset\N,$ and the {\em index set\/} $I$ are finite. If $H_i=H_j$, we
say that the edges $H_i$ and $H_j$ are {\em parallel\/}. {\em Simple\/}
hypergraphs have no parallel edges with $i\neq j$. The union of all
edges is denoted
$\bigcup\HH$. The elements of $\bigcup\HH\subset\N$ are called {\em vertices\/}.
Two isomorphic hypergraphs $\HH_1$ and $\HH_2$ are considered as
{\em identical\/} only
if they are isomorphic via an increasing mapping $F: \bigcup\HH_1\rightarrow\bigcup\HH_2$, otherwise they are distinct. We write $|\cdots|$ for the cardinality of a set.
The {\em order\/} of $\HH$ is the number of vertices $v(\HH)=|\bigcup\HH|$,
the {\em size\/} is the number of edges $e(\HH)=|I|$, and the {\em weight\/} is the number of incidences between vertices and edges
$i(\HH)=\sum_{i\in I}|H_i|$.
We write $[a,b]$ for the interval $a\le x\le b, x\in\N$, and $[k]$ for
$[1,k]$. If $X,Y\subset\N$ and $xn_0$).
Section 5 deals, less successfully, with $p=21$. Theorem~\ref{howelementary}
counts $21$-free graphs. Surprisingly (?), their numbers equal those of
$12$-free graphs.
In Theorem~\ref{21prmax} we count and bound maximal simple $21$-free hypergraphs. We prove that for $p=21$ the best
values of $c_i$ satisfy relations $c_1<64$, $c_2=3.67871\ldots$, $c_3=4$, $c_4=8$,
$c_5<64$, and $c_6<128$ ($n>n_0$).
\section{The conjectures C1--C6 almost hold}
We begin with a few straightforward relations. The simple inequalities established in the proof of the following lemma will be useful later.
\begin{lema}\label{implikace}
For each pattern $p$, (i) $\mathrm{C1\Longleftrightarrow C2\,\&\,C3}$,
(ii) $\mathrm{C4\Longrightarrow C3}$, (iii) $\mathrm{C1\Longrightarrow C5}$,
(iv) $\mathrm{C5\,\&\,C4\Longrightarrow C1}$, and (v)
$\mathrm{C5\Longleftrightarrow C6}$.
\end{lema}
\begin{duk}
Let $q_i(n), i\in[6]$ be the quantities introduced in C1--C6; for $i=3,4$ we mean the maximum size and weight. It is easy to see that $q_i(n)$ is
nondecreasing in $n$. Trivially, $q_1(n)\ge q_2(n)$. Taking all subsets
of $\HH\backslash\{\{v\}:\ v\in\bigcup\HH\}$ for an $\HH$ witnessing $q_3(n)$,
we see that $q_1(n)\ge 2^{q_3(n)-n}$. Also, $q_1(n)\le q_2(n)2^{q_3(n)}$
because each simple $p$-free $\HH$ with $\bigcup\HH=[n]$ is a subset of a
maximal such hypergraph. Thus we have (i). The implication (ii) is trivial by
$q_3(n)\le q_4(n)$ ($e(\HH)\le i(\HH)$). So is (iii) by $q_5(n)\le nq_1(n)$ ($v(\HH)\le i(\HH)$).
To prove (iv) realize only that $q_1(n)\le q_4(n)q_5(q_4(n))$. Clearly,
$q_5(n)\le q_6(n)$. And $q_6(n)< 2^n q_5(n)$, because
each $p$-free $\HH$ of weight $n$ can be obtained from a simple $p$-free
hypergraph of weight $m, m\le n$ by repetitions of edges. The number of
repetitions is bounded by the number of compositions of $n$, which is
$2^{n-1}$. Thus we have (v).
\end{duk}
In Theorems~\ref{c3sp}--\ref{shrnuti} we prove that each of the conjectures C1--C6 is true if the constant $c_i$ is replaced
by a very slowly growing function $\beta_i(n)$.
The almost linear bounds in C3 and C4 come from the theory of {\em generalized
Davenport--Schinzel sequences\/}. We review the required facts.
A sequence $v=a_1a_2\ldots a_l\in[n]^*$ is $k$-{\em sparse\/} if
$a_i=a_j, i1$.
We replace each $\HH\in M(n)$ by a hypergraph $\HH'$ with the vertex set $[m]$, $m=\lceil n/2\rceil$ as
follows. For $\HH=(H_i:\ i\in I)$ we define
$$
H_i'=\{j\in[m]:\ H_i\cap \{2j-1,2j\}\neq\emptyset\}
$$
and set $\HH'=(H_i':\ i\in I)$. Clearly,
$\HH$ and $\HH'$ are in bijection but $\HH'$ is in general not simple. Thus we simplify $\HH'$ to $\HH''$.
It is immediate that $\HH''\in M(m)$. We bound the number of $\HH$s that are
transformed to one $\HH''$. Since $H_i$ can intersect
$\{2j-1,2j\}$ in $3$ ways, we see that one $\HH'$ arises from at most
$$
\prod_{v\in H\in\HH'}3^1=3^{i(\HH')}
$$
hypergraphs $\HH\in M(n)$. For each $H\in\HH''$ with $|H|\ge 2k$
the multiplicity of $H$ in $\HH'$ is $s_2>\cdots>s_k$, the same role
plays
$$
(\{x_{s_i},y_{2i-1}\},\{x_{s_i},y_{4r-2i+1}\}:\ i\in[k]).
$$
\end{duk}
Using Lemma~\ref{obsNk}, bound (\ref{uNkl}), and deleting less than $kn$ terms from $v$, we obtain the following extremal graph-theoretical result.
\begin{veta}\label{grafbezNk}
Every simple graph $\GG$ of order $n$ that does not have $\NN(k)$ as a
subgraph has $O(n)$ edges.
\end{veta}
Since $\NN(k)$ contains (as a subgraph) each inverse
V-pattern of length $k$, as a consequence we obtain this strenghtening of
Lemma~\ref{nejdrivgrafy}.
\begin{lema}\label{silnejdrivgrafy}
Let $p$ be an inverse V-pattern. Then for every simple $p$-free graph $\GG$
of order $n$,
$$
e(\GG)=O(n).
$$
\end{lema}
We proceed to the proof of Theorem~\ref{invVpatt}. Let $p$ be an inverse V-pattern. Using in the proof of Theorem~\ref{c3sp} Lemma~\ref{silnejdrivgrafy}
instead of Lemma~\ref{nejdrivgrafy}, we obtain an $O(n)$ bound. (Due to the
freedom in the definition of blown up permutations, we can take a
$q=p(k^2-k+1)$ that is also an inverse V-pattern.)
In the proof of Theorem~\ref{c4sp} the sequence $v=L_1L_2\ldots L_n$, $L_i$
being the list of the edges of $\HH$ containing the vertex $i$, was used.
If $v$ contains $u_N(k,2)$, $\HH$ contains as a reduction the
hypergraph identical to
$$
(\{i,2k-i+1,2k+i\}:\ i\in[k])
$$
and thus each inverse V-pattern of length $k$. Using (\ref{uNkl}) and the strengthening of Theorem~\ref{c3sp} for inverse V-patterns, we obtain in Theorem~\ref{c4sp} an $O(n)$ bound as well.
Finally, if in the proof of Theorem~\ref{c1sp} the bound
$i(\HH'')0$, then $\limsup |a_n|^{1/n}=1/R$. We
write $|a_n|\doteq (1/R)^n$ and speak of the {\em rough asymptotics\/}.
{\em Schr\"oder numbers\/} $\{S_n\}_{n\ge 1}=\{1, 3, 11, 45, 197, \ldots\}$ count, for example, the
noncrossing arrangements of diagonals in a convex $(n+2)$-gon. Their GF $S(x)=\sum_{n\ge 0}S_nx^n=1+x+3x^2+\cdots$ is given by
\begin{equation}\label{schr}
S(x)=\textstyle{{1\over 4x}}(1+x-\sqrt{1-6x+x^2}).
\end{equation}
The rough asymptotics $S_n\doteq (3+2\sqrt{2})^n=(5.82842\ldots)^n$
is determined by the smallest positive root of $x^2-6x+1$.
By a {\em tree\/} $\TT$ we mean a {\em rooted plane tree\/}, that is, a
finite rooted tree in which sets of siblings are linearly ordered. A {\em leaf\/} is a vertex with no child. The number of children of a vertex is its
{\em outdegree\/}.
We establish a 1-1 correspondence between maximal noncrossing
hypergraphs and trees.
\begin{veta}\label{NCextr1}
Let $M$ be the set of maximal simple noncrossing hypergraphs of
order $n>1$. We have
$$
|M|=S_{n-2},\ \max_{\HH\in M}e(\HH)=4n-5, \mbox{ and }
\max_{\HH\in M}i(\HH)=8n-12.
$$
\end{veta}
\begin{duk}
We describe a bijection between $M$ and the set of trees that have $n-1$ leaves and no vertex with outdegree $1$. Moreover, if $\HH$ corresponds to $\TT$, $e(\HH)=v(\TT)+e(\TT)+2$ and $i(\HH)=v(\TT)+3e(\TT)+3$.
Let $\HH\in M$ and $\bigcup\HH=[n]$,
$n>1$. If $n=2$, $\HH=(\{1\},\{2\},\{1,2\})$.
Suppose $n>2$. By the maximality of $\HH$, $\{1,n\}, \{1,2\},$ and $\{i\},
i\in [n]$ are edges. Let
$m,1n_0$):
$c_2=5.82842\ldots,$ $c_3=4$, $c_4=8$, $c_1\le c_2 2^{c_3}<6\cdot 2^4=96, c_5<96$, and
$c_6<2\cdot 96=192$.
We turn to noncrossing graphs. A decomposition similar to that in the previous
proof provides a bijection between maximal simple $12$-free graphs
of order $n$ and trees which have $n-1$ leaves and outdegrees only $2$ or $0$.
It follows that each such a graph has $2n-3$ edges and there are $C_{n-2}$ of them. (It is well known that there are $C_{n-2}$ such trees, see exercise
6.19.d in \cite{stan}.)
\begin{veta}\label{NCgrafy}
If $a_n$ is the number of simple $12$-free graphs with $n$ edges and $F_1(x)=\sum_{n\ge 0}a_nx^n=1+x+5x^2+33x^3+245x^4+\cdots$, then
\begin{equation}\label{prvni}
F_1(x)=\textstyle{{1\over 16x}}(1+11x-\sqrt{1-10x-7x^2}).
\end{equation}
If $b_n$ is the number of $12$-free graphs with $n$ edges and
$F_2(x)=\sum_{n\ge 0}b_nx^n=1+x+6x^2+44x^3+360x^4+\cdots$, then
\begin{equation}\label{druha}
F_2(x)=\textstyle{{1\over 16x}}(1+10x-\sqrt{1-12x+4x^2}).
\end{equation}
In fact, $b_n=2^{n-1}S_n$. The rough asymptotics is
$$
a_n\doteq (5+4\sqrt{2})^n=(10.65685\ldots)^n\ \mbox{ and }\ b_n\doteq (6+4\sqrt{2})^n=(11.65685\ldots)^n.
$$
\end{veta}
\begin{duk}
To find $F_1$, we define $G=1+2x^2+\cdots$ to be the GF of simple $12$-free graphs (counted by size) in which the first and last vertex are not
adjacent. We show that
\begin{equation}\label{F1aG}
G=1+(F_1-G)(2F_1-2)\ \mbox{ and }\ F_1-G=x(3F_1-3+G).
\end{equation}
Suppose $\GG$ is a simple $12$-free graph and $\bigcup\GG=[m]$.
Consider the longest edge $E=\{1,r\}$ of $\GG$ incident with $1$ and decompose $\GG$ in the restrictions $\GG_1=\GG\,|\,[1,r]$ and
$\GG_2=\GG\,|\,[r,m]$. Since $\GG$ is $12$-free, each edge appears either in $\GG_1$ or in $\GG_2$.
If $r2$ we have the companion
identity $v_n+3v_{n-1}+3v_{n-2}+v_{n-3}=8a_{n-2}$.
\end{veta}
\begin{duk} $F_2$ and $F_1$ are related, as we know, by
$F_2(x)=F_1(x/(1-x))$. We know also that
$G(x)=\sum_{n\ge 0}g_nx^n=1+x+2x^2+8x^3+48x^4+\cdots$ satisfies
$G(x)=8x^2F_2(x)+1+x-6x^2$. Finally, $F_3(x)={1\over 1+x}G(x/(1+x))$. It is
an inversion of the relation $G(x)={1\over 1-x}F_3(x/(1-x))$ that mirrors
the insertions of isolated vertices before, between of, and after the vertices
of a $12$-free simple graph. Using these relations, we express $F_3$ in
terms of $F_1$: $(1+x)^3F_3(x)=8x^2F_1(x)+1+3x-4x^2$.
Thus the identity. Formula (\ref{podobnaprvni}) follows from (\ref{prvni}).
\end{duk}
An alternative way is to use the decomposition from the proof of
Theorem~\ref{NCgrafy}.
Equation $(1+x)^3F_3^2-(2+x)(1+3x)F_3+1+4x=0$ is then obtained.
We return to $12$-free hypergraphs and give yet another proof of the
conjecture C6. It supplies for $c_6$ a value smaller than $10$.
\begin{veta}\label{dalsiduk}
Let $a_n$ be the number of $12$-free hypergraphs of weight $n$. Then, for
$n>n_0$,
$$
a_n<10^n.
$$
\end{veta}
\begin{duk}
If $F_1=r_0+r_1x+\cdots$ and $F_2=s_0+s_1x+\cdots$ are two power series with
real coefficients and $r_i\le s_i$ for all $i=0, 1, \ldots,$ we write
$F_1\le^* F_2$. Let $\HH$ be $12$-free and $\bigcup\HH=[m]$.
Of the edges $X\in\HH$ such that $1\in X$ we choose those having
the largest second vertex (the vertex $\min (X\backslash\{1\})$) and of them
we choose those having the largest cardinality $t$. Since $\HH$ is $12$-free,
the edges $X$ we get must be all parallel, say to $X=\{x_1=1, x_2, \ldots, x_t\}_<$. We define $\HH_i$, $i\in[t]$ as consisting of the edges that lie in $[x_i, x_{i+1}]$, where $x_{t+1}=m$, and (if $t=2$) that are nonparallel to $X$; singletons $\{x_i\}$ are distributed arbitrarily among $\HH_i$ and $\HH_{i-1}$. So each edge is in exactly one $\HH_i$ or is parallel to $X$. Each $\HH_i$ is $12$-free.
Let $F=\sum_{n\ge 0}a_nx^n=1+x+\cdots$ be the GF counting $12$-free hypergraphs by weight.
Bounding the number of non/identifications of the endvertices of the $\HH_i$s by $4$ if $\HH_i\neq\emptyset$ and by $1$ else, and disregarding that for $t>3$ the edge $X$ is unique, we obtain the inequality
$$
F\le^*1+\sum_{t\ge 1}{x^t(4F-3)^t\over 1-x^t}\le^*
1+{1\over 1-x}\sum_{t\ge 1}x^t(4F-3)^t=1+{x(4F-3)\over (1-x)(1-x(4F-3))}.
$$
We used that $x^t/(1-x^t)\le^* x^t/(1-x)$. Let $G$ be the power series satisfying the inequality as equality, that is,
$$
G=1+{x(4G-3)\over (1-x)(1-x(4G-3))}.
$$
So $4x(1-x)G^2+(7x^2-2x-1)G-(3x^2+x-1)=0$. The radius of convergence of
$G$ is the least positive root $\alpha=0.10325\ldots$ of the discriminant $x^4+4x^3+22x^2-12x+1$. Induction on exponents shows that $F\le^* G$. Thus, for
$\varepsilon>0$ and $n>n_0(\varepsilon)$,
$$
a_n<(1/\alpha+\varepsilon)^n=(9.68460\ldots+\varepsilon)^n.
$$
\end{duk}
We invest more effort and count the noncrossing hypergraphs exactly. The calculations below were performed by means of the computer
algebra system MAPLE.
\begin{veta}\label{NChgrfs}
Let $a_n$ be the number of $12$-free hypergraphs of weight $n$.
$F(x)=\sum_{n\ge 0}a_nx^n=1+x+3x^2+10x^3+40x^4+\cdots$ satisfies the equation
\begin{equation}\label{rovproVsNC}
P_4(x)F^4+P_3(x)F^3+P_2(x)F^2+P_1(x)F+P_0(x)=0
\end{equation}
where $P_4(x)=(2x)^7(x-1)^3$,
$P_3(x)=-32x^6(8x^2-11x-1)(x-1)^2$,
%$P_2(x)=192x^{10}-720x^9+840x^8-248x^7-56x^6-4x^4-8x^3+4x$,
$P_2(x)=4x(x-1)(2x-1)(24x^7-54x^6+12x^5+14x^4+8x^3+5x^2+3x+1)$,
$P_1(x)=-64x^{10}+264x^9-336x^8+98x^7+34x^6+2x^5+8x^4+11x^3-6x-1$, and
$P_0(x)=8x^{10}-36x^9+50x^8-15x^7-7x^6-x^5-3x^4-3x^3+x^2+3x+1$. As to the rough asymptotics,
$$
a_n\doteq (6.06688\ldots)^n
$$
where $6.06688\ldots$ is an algebraic number of degree $23$.
\end{veta}
\begin{duk}
Let $b_n$, respectively $c_n$, be the numbers of $12$-free hypergraphs
${\cal H}$ of weight $n$
such that the 2-set $\{\min\bigcup {\cal H},\max\bigcup {\cal H}\}$, respectively the singleton $\{\min\bigcup {\cal H}\}$, is not an edge
of ${\cal H}$. Let
$G(x)=\sum_{n\ge 0}b_nx^n=1+x+2x^2+\cdots$ and $H(x)=\sum_{n\ge 0}c_nx^n=1+x^2+\cdots$ be the corresponding GFs. We prove that the series $F, G$, and $H$ satisfy the equations
\begin{eqnarray}
F&=&1+{xF\over 1-x}+(F-G)(F+H-1)+{x^3(2F+2H-3)^2(F+H-1)\over (1-x)(1-x^3)}\nonumber\\
& &+{(F+H-1)x^4(2F+2H-3)^3\over (1-x)(1-x(2F+2H-3))}\label{proF}\\
F-G&=&{x^2(3F+G-2-1/(1-x))\over 1-x^2}\label{proFbezG}\\
F-H&=&{xF\over 1-x}+{x(H-1)\over 1-x}.\label{proFbezH}
\end{eqnarray}
Elimination of $G$ and $H$ from the system yields (\ref{rovproVsNC}).
Suppose $\bigcup {\cal H}=[m]$. We define
$F({\cal H})=\{X\in{\cal H}:\ 1\in X, |X|\ge 2\}$, $J({\cal H})$ to be the
multiset of the edges $X\in F({\cal H})$ attaining the maximum value of $\min (X\backslash\{1\})$, and $j({\cal H})=\max |X|$, $X\in J({\cal H})$. To prove
equation (\ref{proF}), we partition noncrossing hypergraphs into five classes that correspond to the five summands on the right hand side.
The first class consists of ${\cal H}=\emptyset$ and is counted by $1$.
In the remaining classes ${\cal H}\neq\emptyset$. In the second class
$F({\cal H})=\emptyset$. Such an ${\cal H}$ consists of parallel singletons
$\{1\}$ followed by an $12$-free hypergraph and the class is counted by $(x+x^2+\cdots)F$. In the remaining
classes $F({\cal H})\neq\emptyset$. In the third class
$j({\cal H})=2$. For
such an ${\cal H}$ all edges in $J({\cal H})$ are parallel to
$\{1, m'\}$, $11$; recall that $m$ is the last vertex of $\HH$.
On one hand ${\cal H}$ is counted by $F-G$. On the other hand, consider the hypergraph ${\cal H}_1$ obtained by deleting the edges parallel to $\{1,m\}$.
Let $m_1=\min\bigcup{\cal H}_1$ and $m_2=\max\bigcup{\cal H}_1$. If $m_1\neq m_2$ and $\{m_1,m_2\}\not\in{\cal H}_1$, we have four non/identifications of the pairs $m_1,1$ and $m_2,m$. Then ${\cal H}_1$ is counted by $4(G-1/(1-x))$. If $m_1\neq m_2$ and $\{m_1,m_2\}\in{\cal H}_1$, we have three non/identifications and
${\cal H}_1$ is counted by $3(F-G)$. The remaining cases when
${\cal H}_1=\emptyset$ or $m_1=m_2$ are counted by $3x/(1-x)+1$. Since
$4(G-1/(1-x))+3(F-G)+3x/(1-x)+1=3F+G-2-1/(1-x)$ and the edges parallel to $\{1,m\}$ are counted by $x^2/(1-x^2)$, multiplying both factors we get (\ref{proFbezG}).
To prove equation (\ref{proFbezH}), consider $12$-free hypergraphs ${\cal H}$ with at least one edge $\{1\}$. They are counted by $F-H$. On the other hand, ${\cal H}$ arises
either by appending an $12$-free hypergraph to a repeated singleton or by adding parallel edges $\{1\}$ to a nonempty $12$-free hypergraph that has $1$ as its first vertex but $\{1\}$ is not an edge. Summing the corresponding counting series
$xF/(1-x)$ and $x(H-1)/(1-x)$, we obtain equation (\ref{proFbezH}).
It remains to determine the radius
of convergence $R>0$ of $F(x)$. Let $A(x,F)$ be
the bivariate integral polynomial given in equation (\ref{rovproVsNC}). By Pringsheim theorem, $R$ is a dominant singularity of $F(x)$. So either $R$ is a root of
$P_4(x)$ (which is not) or, by the implicit function theorem,
there is an $S$ such that the pair $x=R, F=S$ is a solution of the system
$$
A(x,F)=0\ \&\ {\partial A(x,F)\over \partial F}=0.
$$
Eliminating $F$, we find that all $x$-solutions are roots of $(x+1)(x^2+x+1)(24x^{23}-56x^{21}-232x^{20}+96x^{19}+824x^{18}+652x^{17}-
1012x^{16}-2236x^{15}
-304x^{14}+2860x^{13}+2824x^{12}-78x^{11}-2246x^{10}-1025x^9+527x^8+780x^7
+84x^6-187x^5-75x^4+8x^3+20x^2+3x-1)$. Since this polynomial has a single
positive real root $\alpha=0.16482\ldots$ (of the third factor), we have
$R=\alpha$ and $a_n\doteq (1/R)^n=(6.06688\ldots)^n$.
\end{duk}
\begin{veta}\label{NCshgrfs}
Let $a_n$ be the number of simple $12$-free hypergraphs of weight $n$. $F(x)=\sum_{n\ge 0}a_nx^n=1+x+2x^2+7x^3+27x^4+\cdots$ satisfies the equation
\begin{equation}\label{rovproObNC}
P_3(x)F^3+P_2(x)F^2+P_1(x)F+P_0(x)=0
\end{equation}
where $P_3(x)=(2x)^5$, $P_2(x)=-16x^6-68x^5+8x^3+8x^2+4x$,
$P_1(x)=2x^7+21x^6+46x^5-5x^4-16x^3-15x^2-8x-1$, and $P_0(x)=-x^7-6x^6-8x^5+
6x^4+10x^3+9x^2+5x+1$. As to the rough asymptotics,
$$
a_n\doteq (5.79950\ldots)^n
$$
where $5.79950\ldots$ is an algebraic number of degree $15$.
\end{veta}
\begin{duk}
Series $G(x)=1+x+x^2+\cdots$ and $H(x)=1+x^2+\cdots$ are defined as in the previous proof (now for simple hypergraphs). We have the simpler
algebraic system
\begin{eqnarray}
F&=&1+xF+(F-G)(F+H-1)+{(1+x)(F+H-1)x^3(2F+2H-3)^2\over 1-x(2F+2H-3)}\nonumber\\
& & \label{proFF}\\
F-G&=&x^2(3F+G-x-3)\label{proFbezGG}\\
F-H&=&xF+x(H-1).\label{proFbezHH}
\end{eqnarray}
Eliminating $G$ and $H$, we obtain equation (\ref{rovproObNC}).
The proof of equations (\ref{proFF})--(\ref{proFbezHH}) is a simplification of the previous proof, due to nonrepetition
of edges, and is left to the reader. The radius of convergence
is obtained as before, by solving the system
$A(x,F)=0\ \&\ A_F(x,F)=0$ where $A(x,F)$ is given in (\ref{rovproObNC}).
\end{duk}
The next theorem shows that order is a more appropriate counting parameter.
\begin{veta}\label{vNChgf}
Let $a_n$ be the number of simple $12$-free hypergraphs of order $n$. $F(x)=\sum_{n\ge 0}a_nx^n=1+x+5x^2+109x^3+3625x^4+\cdots$ satisfies
the equation
\begin{equation}\label{rovvNChgf}
P_3(x)F^3+P_2(x)F^2+P_1(x)F+P_0(x)=0
\end{equation}
where $P_3(x)=(x+1)^5$, $P_2(x)=-(x+1)^2(9x^2+4x+3)$,
$P_1(x)=23x^3-7x^2+5x+3$, and $P_0(x)=17x^2-1$. As to the rough asymptotics,
$$
a_n\doteq (63.97055\ldots)^n
$$
where $63.97055\ldots$ is the only positive real root
of $5x^4-316x^3-242x^2-284x-107$.
\end{veta}
\begin{duk}
It is not too difficult to adapt the decomposition used in the last two proofs for counting by order. We obtain the algebraic system
\begin{eqnarray}
F&=&1+xF+\textstyle{{1\over x}}(F-G)(xF+H-1)\nonumber\\
& &+{2(xF+H-1)((x+1)H+(x^2+x)F-2x-1)^2\over x^2-x((x+1)H+(x^2+x)F-2x-1)}
\nonumber\\
F-G&=&-1-3x+(2x+x^2)F+G\nonumber\\
F-H&=& xF+H-1\nonumber
\end{eqnarray}
and proceed as before. We omit the details. However, notice that now $A(x,F)$
in equation (\ref{rovvNChgf}) does not determine $F$, $F(0)=1$
uniquely, because
$A(0,1)=A_F(0,1)=0$. This can be avoided by working with $\overline{F}$, where
$F=1+x\overline{F}$, instead of $F$.
\end{duk}
\section{$21$-free graphs and maximal $21$-free hypergraphs}
A hypergraph is $21$-free if it does not have vertices $a**n'=n,$ and
$a'=a,n'=n$ must be excluded) are available regardless of the structure of $\GG$.
Consider the bivariate GF
$$
F(x,y)=\sum_{n,m\ge 2}v_{n,m}x^ny^m=x^2y^4+x^3(3y^4+y^6)+\cdots
$$
of the numbers $v_{n,m}$ that count simple $21$-free graphs of order $n$ with
the last edge of span $m$. Of course, we are interested in $F(x,1)$.
Going through the $2m-3$ choices and determining the order of $\GG'=\GG\cup\{E'\}$ and the span of $E'$ in $\GG'$, we see that
the addition of $E'$ amounts formally to the replacement
\begin{eqnarray}
x^ny^m & \rightarrow &x^n(y^4+y^6+\cdots+y^{m-2})+
x^{n+1}(2(y^4+y^6+\cdots+y^{m+2})-y^{m+2})\nonumber\\
& & +x^{n+2}(y^4+y^6+\cdots+y^{m+2})\nonumber\\
& & =x^n\left({y^m-1\over y^2-1}-1-y^2\right)+
x^{n+1}\left(2y^4{y^m-1\over y^2-1}-y^{m+2}\right)+x^{n+2}y^4{y^m-1\over y^2-1}.
\nonumber
\end{eqnarray}
In terms of the GF,
\begin{eqnarray}
F(x,y) & =& x^2y^4+{F(x,y)-F(x,1)\over y^2-1}-(1+y^2)F(x,1)
+{2xy^4(F(x,y)-F(x,1))\over y^2-1}\nonumber\\
& & -xy^2F(x,y)+{x^2y^4(F(x,y)-F(x,1))\over y^2-1}.\nonumber
\end{eqnarray}
This can be rewritten as
\begin{equation}\label{divna}
((x+x^2)y^4+(x-1)y^2+2)\cdot F(x,y)=(1+x)^2y^4\cdot F(x,1)-x^2y^4(y^2-1).
\end{equation}
Solving $(x+x^2)y^4+(x-1)y^2+2=0$ for $y^2$, we obtain
$$
y^2={\textstyle {1\over 2x(1+x)}}(1-x-\sqrt{1-10x-7x^2}).
$$
This series, substituted for $y^2$, makes the left hand side of equation
(\ref{divna}) vanish. Solving the resulting equation for
$F(x,1)$, we get
$$
F(x,1)={x^2(y^2-1)\over (1+x)^2}={x-3x^2-2x^3-x\sqrt{1-10x-7x^2}\over
2(1+x)^3}.
$$
This coincides, after addition of $1$, with formula (\ref{podobnaprvni}).
The first problem, counting simple $21$-free graphs by size, is similar and
easier. It suffices to adjust the above replacement
$x^ny^m\rightarrow\cdots$ by changing $x^n, x^{n+1},$ and $x^{n+2}$ on the
right hand side to
$x^{n+1}$ and to change the beginning of $F(x,y)$ from $x^2y^4$ to
$xy^4$. Proceeding as before and adding $1$ to the result, we arrive at the
formula (\ref{prvni}).
\end{duk}
Allowing multiple edges in the first problem corresponds to the substitution
$x\rightarrow x/(1-x)$, as for noncrossing graphs. Thus the GF obtained is
the same as in the noncrossing case. Similarly when isolated vertices are allowed in the second problem.
We conclude with enumerating and bounding maximal $21$-free hypergraphs.
\begin{veta}\label{21prmax}
Let $M$ be the set of maximal simple $21$-free hypergraphs of order $n$
and $a_n=|M|$. Then, with $F(x)=\sum_{n\ge 0}a_nx^n=1+x+x^2+x^3+3x^4+12x^5+\cdots$ and $n>1$,
\begin{equation}\label{rac}
F(x)={-2x^7+8x^6-11x^5+21x^4-31x^3+23x^2-8x+1\over (x-1)^2(4x^4-15x^3+16x^2-7x+1)},
\end{equation}
$$
\max_{\HH\in M}e(\HH)=4n-5, \
\mbox{and } \max_{\HH\in M}i(\HH)=8n-12.
$$
The rough asymptotics is $a_n\doteq(3.67871\ldots)^n$ where $3.67871\ldots$ is the largest positive root of $x^4-7x^3+16x^2-15x+4$.
\end{veta}
\begin{duk}
In this proof a {\em big\/} edge is an edge with $3$ or more elements.
The other edges are $1$-edges and $2$-edges. We prove the bounds on
$e(\HH)$ and $i(\HH)$. Suppose $\HH\in M$ with
$\bigcup\HH=[n], n\ge 2$. $\HH$ has at most $n$ $1$-edges contributing weight $\le n$. By the
above characterization of maximal simple $21$-free graphs, $\HH$ has at most $2n-3$ $2$-edges contributing weight
$\le 4n-6$. It is easy to see that if we delete from each
big edge the first and last
element, the resulting sets are disjoint and lie in $[2,n-1]$. Thus $\HH$ has
at most $n-2$ big edges contributing weight $\le n-2+2(n-2)=3n-6$. In total,
$e(\HH)\le n+2n-3+n-2=4n-5$ and $i(\HH)\le n+4n-6+3n-6=8n-12$. The hypergraphs
$$
\HH_1=(\{1,i,n\},\{1,n\},\{1,i\},\{i,n\},\{j\}:\ i\in[2,n-1],j\in[n])
$$
and
$$
\HH_2=(\{i,i+1,i+2\},\{i,i+2\},\{j,j+1\},\{k\}:\ i\in[n-2],j\in[n-1],k\in[n])
$$
show that the bounds are tight.
We count $M$ by means of the methodology, due to the French enumerative school, that puts enumerated objects in bijection with words of a formal language.
We say that a graph $\GG$ is an $I,J${\em -graph\/}, where $In_0$ relations $c_2=3.67871\ldots$,
$c_3=4$, $c_4=8$, $c_1<4\cdot 2^4=64$, $c_5<64$, and
$c_6<2\cdot 64=128$.
\section{Concluding remarks}
Bound (\ref{muj}) in general cannot be improved to $O(n)$. For example,
it is known that if the sequence $u\in[n]^*$ is $2$-sparse, does not contain $121212$, and
has the maximum length, then
$$
n2^{\alpha(n)}\ll |u|\ll n2^{\alpha(n)}.
$$
(We use here, as it is common in some texts, $\ll$ as a synonym to the $O(\cdots)$ notation.)
For more information see the book of Sharir and Agarwal \cite{shar_agar}.
Another extension of the problem of forbidden permutations was
given by Alon and Friedgut \cite{alon_frie}. They extend the avoidance of permutations to the words in $\N^*$, apply (\ref{uNkl}) to prove $S_n(p)**