Counting Pattern-free Set Partitions II: Noncrossing and Other Hypergraphs

Martin Klazar

Department of Applied Mathematics Charles University Malostranské náměstí 25, 118 00 Praha Czech Republic

                   klazar@kam.ms.mff.cuni.cz

Submitted: January 28, 2000; Accepted: May 23, 2000.

Dedicated to the memory of Rodica Simion

Abstract

A (multi)hypergraph H with vertices in N contains a permutation p = a_{1}a_{2} … a_{k} of 1, 2, …, k if one can reduce H by omitting vertices from the edges so that the resulting hypergraph is isomorphic, via an increasing mapping, to H_{p} = ({i, k + a_{i}} : i = 1, …, k). We formulate six conjectures stating that if H has n vertices and does not contain p then the size of H is O(n) and the number of such Hs 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β(n)) and O(β(n)^{n}), where β(n) → ∞ 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.

2000 MSC: Primary 05A05, 05A15, 05A18, 05C65, 05D05; Secondary: 03D20, 05C30, 11B83.

Support of the grant GAUK 158/99 is gratefully acknowledged.

1 Notation, conjectures, and motivation

We shall investigate numbers and sizes of pattern-free hypergraphs. A hypergraph H is a finite multiset of finite nonempty subsets of N = {1, 2, …}. More explicitly, H = (H_{i} : i ∈ I) where the edges H_{i}, ∅ ≠ H_{i} ⊂ N, and the index set I are finite. If H_{i} = H_{j}, we say that the edges H_{i} and H_{j} are parallel. Simple hypergraphs have no parallel edges with i ≠ j. The union of all edges is denoted ⋃ H. The elements of ⋃ H ⊂ N are called vertices. Two isomorphic hypergraphs H_{1} and H_{2} are considered as identical only if they are isomorphic via an increasing mapping F : ⋃ H_{1} → ⋃ H_{2}, otherwise they are distinct. We write | ⋯ | for the cardinality of a set. The order of H is the number of vertices v(H) = | ⋃ H|, the size is the number of edges e(H) = |I|, and the weight is the number of incidences between vertices and edges i(H) = ∑_{i∈I} |H_{i}|. We write [a, b] for the interval a ≤ x ≤ b, x ∈ N, and [k] for [1, k]. If X, Y ⊂ N and x < y for all x ∈ X, y ∈ Y, we write X < Y. The important feature of our hypergraphs is that their vertex sets are linearly ordered.

To simplify H means to keep just one edge from each family of mutually parallel edges of H. A subhypergraph of H = (H_{i} : i ∈ I) is any hypergraph (H_{i} : i ∈ I′) with I′ ⊂ I. A reduction of H is any hypergraph (H′_{i} : i ∈ I′) with I′ ⊂ I and H′_{i} ⊂ H_{i} for each i ∈ I′. A restriction H | X of H to X ⊂ ⋃ H is the hypergraph (H_{i} ∩ X : i ∈ I) with empty edges deleted.

We deal also with classes of particular hypergraphs. Permutations are simple H for which (i) |X| = 2, (ii) X ∩ Y = ∅, and (iii) X ≮ Y holds for all X, Y ∈ H, X ≠ Y. Matchings are simple hypergraphs satisfying (i) and (ii). Graphs are (not necessarily simple) hypergraphs satisfying (i). Partitions are simple hypergraphs satisfying (ii).

A pattern is any k-permutation p = a_{1}a_{2} … a_{k} of [k]. We associate with it the hypergraph H_{p} = ({i, k + a_{i}} : i = 1, …, k). H contains p if H has a reduction identical to H_{p}. Otherwise we say that H is p-free. H is a maximal simple p-free hypergraph if H ceases to be simple or p-free when any X ⊂ ⋃ H is added to the edges.

We propose to investigate the numbers, sizes, and weights of p-free hypergraphs of a given order. We believe that the following six conjectures are true. The constants c_{i} depend only on the pattern p.

C1. The number of simple p-free H with v(H) = n is < c_{1}^{n}.

C2. The number of maximal simple p-free H with v(H) = n is < c_{2}^{n}.

C3. For every simple p-free H with v(H) = n we have e(H) < c_{3}n.

C4. For every simple p-free H with v(H) = n we have i(H) < c_{4}n.

C5. The number of simple p-free H with i(H) = n is < c_{5}^{n}.

C6. The number of p-free H with i(H) = n is < c_{6}^{n}.

One can consider the more general situation when the forbidden reduction R is any hypergraph, not just H_{p}. But if R has an edge with more than two vertices or two intersecting edges or two two-element edges X < Y, then the conjecture C1 does not hold — no permutation has R as a reduction and we have at least n! simple R-free Hs of order 2n. Therefore C1 can possibly hold only if R has only disjoint singleton and doubleton edges and the doubletons form an H_{p}.

Our enumerative and extremal hypergraph problems are motivated by the problem of forbidden permutations (introduced by Simion and Schmidt [22]) and the Stanley– Wilf conjecture (posed in 1992) which we extend to hypergraphs. The problem asks, for a k-permutation p = a_{1}a_{2} … a_{k}, to find the numbers S_{n}(p) of n-permutations q = b_{1}b_{2} … b_{n} that avoid p. Here avoidance of p means that for no k-element subsequence 1 ≤ i_{1} < ⋯ < i_{k} ≤ n of 1, …, n we have, for every r and s, a_{r} < a_{s} iff b_{i_{r}} < b_{i_{s}}. The conjecture says that S_{n}(p) < c^{n} for each p. Strong partial results of Bóna [2] and Alon and Friedgut [1] (see also Klazar [12]) support it. Connection to hypergraphs is this: S_{n}(p) is in fact the number of size n = order 2n = weight 2n permutations not containing p. Thus each of the conjectures C1, C5, and C6 generalizes the Stanley–Wilf conjecture by embedding permutations in the class of hypergraphs.

How far can one extend the world of permutations so that there is still a chance for an exponential upper bound on the number of permutation-free objects? In Klazar [11] we considered partitions, that is H with disjoint edges. C1, C5, and C6 generalize a conjecture stated there. Although partitions will be mentioned here only briefly, we continue in the investigations of [11] and thus the title.

The paper consists of the extremal part in Sections 2 and 3 and the enumerative part in Sections 4 and 5. Section 6 contains some remarks and comments.

In Section 2 we prove in Theorem 2.6 that the conjectures C1–C6 hold in the weaker form when c_{i} is replaced by β_{i}(n). The nondecreasing functions β_{i}(n) are unbounded but grow very slowly. In Section 3 in Theorem 3.1 we prove the conjectures C1–C6 completely, provided p looks like ”A” or p^{−1} looks like ”V”.

Section 4 is concerned with exact enumeration of 12-free hypergraphs. In Theorem 4.1 we count maximal simple 12-free hypergraphs and bound their sizes and weights. Theorems 4.2 and 4.3 count 12-free graphs. In Theorem 4.4 we prove quickly that one can take c_{6} < 10. Theorems 4.5, 4.6, and 4.7 determine the best values of c_{6}, c_{5}, and c_{1}, respectively. In summary, for p = 12 the best values of c_{i} are: c_{1} = 63.97055 …, c_{2} = 5.82842 …, c_{3} = 4, c_{4} = 8, c_{5} = 5.79950 …, and c_{6} = 6.06688 … (n > n_{0}). Section 5 deals, less successfully, with p = 21. Theorem 5.1 counts 21-free graphs. Surprisingly (?), their numbers equal those of 12-free graphs. In Theorem 5.2 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 …, c_{3} = 4, c_{4} = 8, c_{5} < 64, and c_{6} < 128 (n > n_{0}).

2 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.

Lemma 2.1 For each pattern p, (i) C1 ⟺ C2 & C3, (ii) C4 ⟹ C3, (iii) C1 ⟹ C5, (iv) C5 & C4 ⟹ C1, and (v) C5 ⟺ C6.

Proof. Let q_{i}(n), i ∈ [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) ≥ q_{2}(n). Taking all subsets of H\{{v} : v ∈ ⋃ H} for an H witnessing q_{3}(n), we see that q_{1}(n) ≥ 2^{q_{3}(n)−n}. Also, q_{1}(n) ≤ q_{2}(n)2^{q_{3}(n)} because each simple p-free H with ⋃ H = [n] is a subset of a maximal such hypergraph. Thus we have (i). The implication (ii) is trivial by q_{3}(n) ≤ q_{4}(n) (e(H) ≤ i(H)). So is (iii) by q_{5}(n) ≤ nq_{1}(n) (v(H) ≤ i(H)). To prove (iv) realize only that q_{1}(n) ≤ q_{4}(n)q_{5}(q_{4}(n)). Clearly, q_{5}(n) ≤ q_{6}(n). And q_{6}(n) < 2^{n}q_{5}(n), because each p-free H of weight n can be obtained from a simple p-free hypergraph of weight m, m ≤ 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). □

In Theorems 2.3–2.6 we prove that each of the conjectures C1–C6 is true if the constant c_{i} is replaced by a very slowly growing function β_{i}(n). The almost linear bounds in C3 and C4 come from the theory of generalized Davenport–Schinzel sequences. We review the required facts.

A sequence v = a_{1}a_{2} … a_{l} ∈ [n]^{∗} is k-sparse if a_{i} = a_{j}, i < j implies j − i ≥ k. In other words, in each interval of length at most k all terms are distinct. In applications it is often the case that v is not in general k-sparse but we know that it is composed of m intervals v = I_{1}I_{2} … I_{m} such that in each I_{i} all terms are distinct. Clearly, then we can delete at most (k − 1)(m − 1) terms from v, at most k − 1 from the beginning of each of I_{2}, …, I_{m}, so that the resulting subsequence w is k-sparse.

The length of v is denoted |v|. If u, v ∈ [n]^{∗} are two sequences and v has a subsequence that differs from u only by an injective renaming f : [n] → [n] of symbols, we say that v contains u. For example, v = 2131425 contains u = 4334 but v does not contain u = 2323. We use u(k, l) to denote the sequence 12 … k12 … k … 12 … k ∈ [k]^{∗} with l segments 12 … k.

In Klazar [9] it was proved that if v ∈ [n]^{∗} is k-sparse and does not contain u(k, l), where k ≥ 2 and l ≥ 3, then for every n ∈ N

|v| ≤ n · 2k2^{kl−4}(10k)^{2(α(n))^{kl−4}+8(α(n))^{kl−5}}  (1)

where α(n) is the inverse of the Ackermann function A(n) known from the recursion theory. (If k = 1 or l ≤ 2, one can easily prove that |v| = O(n).)

We remind the reader the definition of A(n) and α(n). If F_{1}(n) = 2n, F_{2}(n) = 2^{n}, and F_{i+1}(n) = F_{i}(F_{i}(… F_{i}(1) …)) with n iterations of F_{i}, then A(n) = F_{n}(n) and α(n) = min{m : A(m) ≥ n}. Although α(n) → ∞, in practice α(n) is bounded:

α(n) ≤ 4 for n ≤ 2^{2^{·^{·^{·^{2}}}}}

where the tower has 2^{16} = 65536 twos. We use β(k, l, n) to denote the factor at n in (1). Thus

β(k, l, n) = 2k2^{kl−4}(10k)^{2(α(n))^{kl−4}+8(α(n))^{kl−5}}.  (2)

First we derive from the bound (1) an almost linear bound for sizes of p-free graphs.

Lemma 2.2 Let p be a k-permutation. For every simple p-free graph G of order n,

e(G) < n · 2β(k, 2k, n)

where β(k, l, n) is defined in (2).

Proof. For G, ⋃ G = [n] as described consider the sequence v = N_{1}N_{2} … N_{n} where N_{i} is the arbitrarily ordered list of all js such that j < i and {j, i} ∈ G. By the above remark, v has a k-sparse subsequence w, |v| < |w| + kn. It is not difficult to see that if v contains the sequence u(k, 2k), G contains p. (Take all k elements of the 1st segment of the copy of u(k, 2k) in v and the right element from the 2nd, 4th, 6th, …, 2k-th segment.) Thus w does not contain u(k, 2k) and we can apply (1):

e(G) = |v| < kn + |w| < kn + nβ(k, 2k, n) ≤ n · 2β(k, 2k, n).
□

Let l ∈ N and p be a k-permutation. We replace each vertex v in H_{p} by l new vertices v_{1} < v_{2} < ⋯ < v_{l} so that for each two vertices v < w we have v_{l} < w_{1}. The edge {v, w}_{<} is replaced by the group of l new edges {v_{i}, w_{i}}. (Any other matching of v_{i}s with w_{j}s can be used.) The simple graph obtained is identical to H_{q} for a kl-permutation q, the blown up p. We denote it q = p(l).

We extend the bound to sizes of p-free hypergraphs.

Theorem 2.3 Let p be a k-permutation. Every simple p-free hypergraph H of order n satisfies the inequality

e(H) < n · 3k(16)^{β(r,2r,n)}β(k, 2k, n) = n · β_{3}(n)  (3)

where r = k^{3} − k^{2} + k and β(k, l, n) is defined in (2).

Proof. Let H, H = [n] be as described. We show that there always exists a pair (=2set) E contained in few edges of H. Thus we can select a pair from each edge so that the multiplicity of each pair is small. This reduces the hypergraph problem to graphs.

We put in H_{1} all H ∈ H with 1 < |H| < 2k and for each H ∈ H, |H| ≥ 2k one arbitrarily chosen subset X ⊂ H, |X| = 2k. H_{2} is the simplification of H_{1}. Clearly, each edge of H_{2} has in H_{1} multiplicity less than k; otherwise H_{1} and H would contain p. Let G_{3} be the simple graph defined by E ∈ G_{3} iff E ⊂ H for some H ∈ H_{2}.

G_{3} may contain p. In fact, each H ∈ H_{2} with 2k vertices creates a copy of H_{p}. However, G_{3} does not contain q = p(k(k − 1) + 1). Suppose to the contrary that H_{q} is a subgraph of G_{3}. In each group of k^{2} − k + 1 new edges in the copy of H_{q} only at most k may come from one H ∈ H_{2}. So a subset of k of them comes from k distinct Hs. Selecting one new edge from each subset, we obtain the contradiction that H_{2} and H contain p.

Hence, G_{3} is simple and q-free. Certainly v(G_{3}) = n′ ≤ n. The previous lemma tells us that

e(G_{3}) < n′ · 2β(r, 2r, n′)

where r = k^{3} − k^{2} + k. Thus G_{3} has a vertex v^{∗} with degree

d = deg(v^{∗}) < 4β(r, 2r, n′) ≤ 4β(r, 2r, n).

We fix an edge E ∈ G_{3} incident with v^{∗} and show that E ⊂ H for few H ∈ H_{2}.

Let m be the number of the edges H ∈ H_{2} with E ⊂ H and X their union. We have the inequalities

d ≥ |X| − 1 and m < 2^{|X|−1}

which imply that

m < 2^{d} < 16^{β(r,2r,n)} = γ(n).

(For simplicity we overestimate here, m is bounded polynomially in d.) Hence a pair exists, E, that is contained in at least one but less than γ(n) edges of H_{2}. This is true also for each subhypergraph of H_{2}.

We define a mapping F : H_{2} → \binom{⋃ H_{2}}{2}. We start with the rare pair E and the edges containing it. We define the value of F on those edges as E, delete them from H_{2}, and process the remaining subhypergraph in the same way until F is defined on all edges. It is clear that (i) F (H) ⊂ H for each H ∈ H_{2} and (ii) |F^{−1}(E)| < γ(n) for each E ∈ \binom{⋃ H_{2}}{2}.

Let G_{4} be the image of F. G_{4} is a simple and p-free graph of order at most n. Thus, using in the last inequality the previous lemma,

e(H) ≤ e(H_{1}) + n < ke(H_{2}) + n < kγ(n)e(G_{4}) + n ≤ kγ(n) · n · 2β(k, 2k, n) + n

which gives the stated bound. □

We extend the bound further to weights.

Theorem 2.4 Let p be a k-permutation. Every simple p-free hypergraph H of order n satisfies the inequality

i(H) < n · 2β_{3}(n)β(k, 3k, nβ_{3}(n)) = n · β_{4}(n)  (4)

where β_{3}(n) is defined in (3) and β(k, l, n) in (2).

Proof. Let H, H = [n] be as stated. We label the edges 1, 2, …, m = e(H) and consider the sequence v = L_{1}L_{2} … L_{n} ∈ [m]^{∗} where L_{i} is the list of the edges containing the vertex i. L_{i} is ordered arbitrarily. We take the k-sparse subsequence w of v, |v| < |w| + kn. A moment of thought reveals that if v contains u(k, 3k), H contains p. (Take, for i = 1, 2, …, k, from the ith segment of the copy of u(k, 3k) in v the ith element and the right element from the (k + 2)th, (k + 4)th, …, 3k-th segment.) Thus w does not contain u(k, 3k). Bound (1) gives us |w| < mβ(k, 3k, m). By the previous theorem, m < nβ_{3}(n). Thus

i(H) = |v| < kn + |w| < kn + nβ_{3}(n)β(k, 3k, nβ_{3}(n)).
□

Finally, we use the bound for weights to obtain a bound for numbers.

Theorem 2.5 Let p be a k-permutation. The number of simple p-free hypergraphs H of order n is smaller than

(9^{(3^{2k}+2k)β_{4}(n)})^{n} = β_{1}(n)^{n}  (5)

where β_{4}(n) is defined in (4).

Proof. Let M(n) be the set of simple p-free hypergraphs with the vertex set [n] and let n > 1. We replace each H ∈ M(n) by a hypergraph H′ with the vertex set [m], m = ⌈n/2⌉ as follows. For H = (H_{i} : i ∈ I) we define

H′_{i} = {j ∈ [m] : H_{i} ∩ {2j − 1, 2j} ≠ ∅}

and set H′ = (H′_{i} : i ∈ I). Clearly, H and H′ are in bijection but H′ is in general not simple. Thus we simplify H′ to H′′.

It is immediate that H′′ ∈ M(m). We bound the number of Hs that are transformed to one H′′. Since H_{i} can intersect {2j − 1, 2j} in 3 ways, we see that one H′ arises from at most

∏_{v∈H∈H′} 3^{1} = 3^{i(H′)}

hypergraphs H ∈ M(n). For each H ∈ H′′ with |H| ≥ 2k the multiplicity of H in H′ is < k; otherwise H′ would contain p and so would H. If H ∈ H′′ and |H| < 2k, the multiplicity of H in H′ is < 3^{2k}, because H is simple and H arises from distinct edges of H. Thus each edge of H′′ has in H′ multiplicity < 3^{2k}. One H′′ ∈ M(m) arises from less than

(3^{2k})^{e(H′′)}

hypergraphs H′. By the previous theorem, e(H′′) ≤ i(H′′) < mβ_{4}(m). Also, i(H′) < 3^{2k}i(H′′) < 3^{2k}mβ_{4}(m). Combining the estimates, we obtain

|M(n)| < 3^{(3^{2k}+2k)⌈n/2⌉β_{4}(⌈n/2⌉)} · |M(⌈n/2⌉)|.

Iterating the inequality until we reach |M(1)| = 1, we obtain

|M(n)| < (3^{2(3^{2k}+2k)β_{4}(n)})^{n} .
□

We summarize what we have achieved.

Theorem 2.6 Let p be a k-permutation, β_{1}(n), β_{3}(n), and β_{4}(n) as defined in (2)–(5), β_{2}(n) = β_{1}(n), β_{5}(n) = 2β_{1}(n), and β_{6}(n) = 4β_{1}(n). The conjectures C1–C6 of Section 1 hold when the constant c_{i} is replaced by the function β_{i}(n).

Proof. The results for C1, C3, and C4 are proved in Theorems 2.5, 2.3, and 2.4, respectively. The results for C2, C5, and C6 follow by the inequalities in the proof of Lemma 2.1. □

The fact that β_{1}(n) is roughly triple exponential in α(n) does not bother us. The function α(n) grows so slowly that each β_{i}(n) is still almost constant, e.g., β_{i}(n) = O(log log … log n) for any fixed number of logarithms.

3 The conjectures C1–C6 hold for A-patterns and inverse V-patterns

A k-permutation p = a_{1}a_{2} … a_{k} is a V-pattern if, for some i, a_{1}a_{2} … a_{i} decreases and a_{i}a_{i+1} … a_{k} increases. Similarly, p is an A-pattern if it first increases and then decreases. We write p^{∗} to denote the permutation p^{∗} = (k−a_{k} +1)(k−a_{k−1} +1) … (k−a_{1} +1). For a hypergraph H we obtain \overline{H} by reverting the linear order of ⋃ H. We have \overline{H_{p}} = H_{q} where q = (p^{−1})^{∗} = (p^{∗})^{−1}. Hence, H contains p iff \overline{H} contains (p^{∗})^{−1}. In this section we prove the following result.

Theorem 3.1 The conjectures C1–C6 hold for each p such that p^{−1} is a V-pattern or p is an A-pattern.

The operation ^{∗} interchanges A-patterns and V-patterns. Therefore p is an A-pattern iff ((p^{∗})^{−1})^{−1} is a V-pattern. It suffices to prove only the first part of the theorem. The second part follows by replacing each p-free H with \overline{H}. So we assume that p is such that p^{−1} is a V-pattern; p is an inverse V-pattern for short. That is, p itself can be partitioned into a decreasing and an increasing subsequence so that all terms of the former are smaller than all terms of the latter.

We strengthen, for inverse V-patterns, the almost linear bounds of Section 2 to linear bounds. We build on a result for generalized Davenport–Schinzel sequences which concerns the forbidden N-shaped sequence u_{N}(k, l) of length 3kl,

u_{N}(k, l) = 1^{l}2^{l} … (k − 1)^{l}k^{2l}(k − 1)^{l} … 2^{l}1^{2l}2^{l} … (k − 1)^{l}k^{l} ∈ [k]^{∗}

where i^{l} = ii … i with l terms. In Klazar and Valtr [13] (Theorem B and Consequence B) we proved that if v ∈ [n]^{∗} is k-sparse and does not contain u_{N}(k, l) then

|v| < cn  (6)

where c depends only on k and l. A more readable proof is given in Valtr [25] (Theorem Consider the simple graph

N (k) = ({i, 2k − i + 1}, {i, 2k + i} : i ∈ [k]).

([k] is matched with [k + 1, 2k] decreasingly and with [2k + 1, 3k] increasingly.) Recall that for a simple graph G, ⋃ G = [n] the sequence v = N_{1}N_{2} … N_{n} consists of the lists of neighbours N_{i} = {j : j < i & {j, i} ∈ G}.

Lemma 3.2 Let G, ⋃ G = [n] be a simple graph such that v = N_{1}N_{2} … N_{n} contains u_{N}(k^{2} − 2k + 2, 2). Then G has N (k) as a subgraph.

Proof. Let r = k^{2} − 2k + 2 and v = N_{1}N_{2} … N_{n} contain u_{N}(r, 2). It follows that there are r distinct and 6r not necessarily distinct vertices in G, x_{1} < x_{2} < ⋯ < x_{r} and y_{1} < y_{2} ≤ y_{3} < y_{4} ≤ ⋯ ≤ y_{6r−1} < y_{6r}, and an r-permutation s_{1}s_{2} … s_{r} such that, for each i ∈ [r], x_{s_{i}} < y_{2i−1} and x_{s_{i}} is connected in G to the six distinct vertices y_{2i−1}, y_{2i}, y_{4r−2i+1}, y_{4r−2i+2}, y_{4r+2i−1}, and y_{4r+2i}. The 3r vertices y_{1} < y_{3} < y_{5} < ⋯ < y_{6r−1} are distinct and x_{s_{i}} is connected to y_{2i−1}, y_{4r−2i+1}, and y_{4r+2i−1}. By the classical result of Erdős and Szekeres, s_{1}s_{2} … s_{r} has a monotonous subsequence of length k. For simplicity of notation we take it to be the initial segment.

If s_{1} < s_{2} < ⋯ < s_{k} then

({x_{s_{i}}, y_{4r−2i+1}}, {x_{s_{i}}, y_{4r+2i−1}} : i ∈ [k])

is the copy of N (k) in G. If s_{1} > s_{2} > ⋯ > s_{k}, the same role plays

({x_{s_{i}}, y_{2i−1}}, {x_{s_{i}}, y_{4r−2i+1}} : i ∈ [k]).
□

Using Lemma 3.2, bound (6), and deleting less than kn terms from v, we obtain the following extremal graph-theoretical result.

Theorem 3.3 Every simple graph G of order n that does not have N (k) as a subgraph has O(n) edges.

Since N (k) contains (as a subgraph) each inverse V-pattern of length k, as a consequence we obtain this strenghtening of Lemma 2.2.

Lemma 3.4 Let p be an inverse V-pattern. Then for every simple p-free graph G of order n,

e(G) = O(n).

We proceed to the proof of Theorem 3.1. Let p be an inverse V-pattern. Using in the proof of Theorem 2.3 Lemma 3.4 instead of Lemma 2.2, 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 2.4 the sequence v = L_{1}L_{2} … L_{n}, L_{i} being the list of the edges of H containing the vertex i, was used. If v contains u_{N}(k, 2), H contains as a reduction the hypergraph identical to

({i, 2k − i + 1, 2k + i} : i ∈ [k])

and thus each inverse V-pattern of length k. Using (6) and the strengthening of Theorem 2.3 for inverse V-patterns, we obtain in Theorem 2.4 an O(n) bound as well.

Finally, if in the proof of Theorem 2.5 the bound i(H′′) < mβ_{4}(m) is improved to i(H′′) = O(m), β_{1}(m) turns to a constant. Hence, for inverse V-patterns the conjectures C1, C3, and C4 hold. So do C2, C5, and C6, by Lemma 2.1. This finishes the proof of Theorem 3.1.

4 Noncrossing graphs and hypergraphs

Recall that for H to be 12-free means not to have vertices a < b < c < d and different (but possibly parallel) edges X, Y such that a, c ∈ X and b, d ∈ Y. In consequence, if H_{i} and H_{j} are edges, i ≠ j, then |H_{i} ∩ H_{j}| ≤ 3 and equality is possible only when H_{i} and H_{j} are parallel. Partitions, graphs, and other 12-free structures are usually called noncrossing. Simion [21] gives a nice survey on noncrossing partitions. Before proceeding to hypergraphs and graphs, we review terminology and known results for the other classes.

There is only one 12-free permutation of a given size. The numbers of noncrossing matchings and partitions of order (=weight) n are

\frac{1}{n/2 + 1}\binom{n}{n/2} (for even n, 0 else) and \frac{1}{n + 1}\binom{2n}{n},

respectively. These Catalan results are by now classical, see Kreweras [14] and Stanley [23] (exercises 6.19.o and 6.19.pp). The nth Catalan number is C_{n} = \frac{1}{n+1} \binom{2n}{n}.

We show often that the generating function (abbreviated GF) counting numbers in question satisfies an algebraic equation. A procedure is known that extracts, if one does not have bad luck, from the equation an exact asymptotics for the coefficients. We content ourselves with determining just the radius of convergence and need only a simpler version of the procedure. We indicate it briefly in the end of the proof of Theorem 4.5. For more information and references on this matter we refer the reader to the interesting discussion in Flajolet and Noy [5] (part 4) and to Odlyzko [16] (section 10.5). It is well known that if F = a_{0} + a_{1}x + ⋯ is a power series with the radius of convergence R > 0, then lim sup |a_{n}|^{1/n} = 1/R. We write |a_{n}| ≐ (1/R)^{n} and speak of the rough asymptotics.

Schröder numbers {S_{n}}_{n≥1} = {1, 3, 11, 45, 197, …} count, for example, the noncrossing arrangements of diagonals in a convex (n + 2)-gon. Their GF S(x) = ∑_{n≥0} S_{n}x^{n} = 1 + x + 3x^{2} + ⋯ is given by

S(x) = \frac{1}{4x}(1 + x − \sqrt{1 − 6x + x^{2}}).  (7)

The rough asymptotics S_{n} ≐ (3 + 2\sqrt{2})^{n} = (5.82842 …)^{n} is determined by the smallest positive root of x^{2} − 6x + 1.

By a tree T we mean a rooted plane tree, that is, a finite rooted tree in which sets of siblings are linearly ordered. A leaf is a vertex with no child. The number of children of a vertex is its outdegree. We establish a 1-1 correspondence between maximal noncrossing hypergraphs and trees.

Theorem 4.1 Let M be the set of maximal simple noncrossing hypergraphs of order n > 1. We have

|M| = S_{n−2}, max_{H∈M} e(H) = 4n − 5, and max_{H∈M} i(H) = 8n − 12.

Proof. We describe a bijection between M and the set of trees that have n−1 leaves and no vertex with outdegree 1. Moreover, if H corresponds to T , e(H) = v(T ) + e(T ) + 2 and i(H) = v(T ) + 3e(T ) + 3. Let H ∈ M and ⋃ H = [n], n > 1. If n = 2, H = ({1}, {2}, {1, 2}).

Suppose n > 2. By the maximality of H, {1, n}, {1, 2}, and {i}, i ∈ [n] are edges. Let m, 1 < m ≤ n be the last vertex such that {1, m} ⊂ X for an edge X, X ≠ {1, n}. By the maximality of H, m = n; otherwise we could add {1, m, n} to H. Thus H has a unique edge X = {x_{1} = 1, x_{2}, …, x_{t} = n}_{<}, t ≥ 3. Each edge distinct from {1, n}, X, and the singletons {i} lies in exactly one of the intervals [x_{i}, x_{i+1}], i ∈ [t − 1]. H decomposes in t − 1 ≥ 2 simplified restrictions H_{i} = H | [x_{i}, x_{i+1}] with the same structure. Decomposing H_{i} further until hypergraphs of order 2 are reached, we define in an obvious manner a tree T with the stated properties. H can be easily recovered from T . Counting e(H) and i(H) in terms of v(T ) and e(T ) is straightforward and we skip it.

Hence, |M| is the same as the number of trees of the described type. It is well known that they are counted by the Schröder numbers ([23], exercise 6.39.b) and it is easy to give a proof by GF; we omit the details. The extremal values of e(H) and i(H) follow from the formulas by substituting the largest values of v(T ) and e(T ), which are 2n − 3 and 2n−4. (Alternatively, the argument from the beginning of the proof of Theorem 5.2 works for p = 12 as well.) □

That for p = 12 the conjectures C1–C6 hold follows already from Theorem 3.1. However, using the last theorem and the inequalities of Lemma 2.1, we get a much simpler proof and realistic estimates for c_{i} (n > n_{0}): c_{2} = 5.82842 …, c_{3} = 4, c_{4} = 8, c_{1} ≤ c_{2}2^{c_{3}} < 6 · 2^{4} = 96, c_{5} < 96, and c_{6} < 2 · 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 [23].)

Theorem 4.2 If a_{n} is the number of simple 12-free graphs with n edges and F_{1}(x) = ∑_{n≥0} a_{n}x^{n} = 1 + x + 5x^{2} + 33x^{3} + 245x^{4} + ⋯, then

F_{1}(x) = \frac{1}{16x}(1 + 11x − \sqrt{1 − 10x − 7x^{2}}).  (8)

If b_{n} is the number of 12-free graphs with n edges and F_{2}(x) = ∑_{n≥0} b_{n}x^{n} = 1 + x + 6x^{2} + 44x^{3} + 360x^{4} + ⋯, then

F_{2}(x) = \frac{1}{16x}(1 + 10x − \sqrt{1 − 12x + 4x^{2}}).  (9)

In fact, b_{n} = 2^{n−1}S_{n}. The rough asymptotics is

a_{n} ≐ (5 + 4\sqrt{2})^{n} = (10.65685 …)^{n} and b_{n} ≐ (6 + 4\sqrt{2})^{n} = (11.65685 …)^{n}.

Proof. To find F_{1}, we define G = 1 + 2x^{2} + ⋯ 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

G = 1 + (F_{1} − G)(2F_{1} − 2) and F_{1} − G = x(3F_{1} − 3 + G).  (10)

Suppose G is a simple 12-free graph and ⋃ G = [m]. Consider the longest edge E = {1, r} of G incident with 1 and decompose G in the restrictions G_{1} = G | [1, r] and G_{2} = G | [r, m]. Since G is 12-free, each edge appears either in G_{1} or in G_{2}. If r < m, G is counted by G, G_{1} by F_{1} − G (it has the longest possible edge), and G_{2} by 2F_{1} − 2 (it is nonempty and we can identify min ⋃ G_{2} and r or leave them separate). Multiplying both factors and not forgetting G = ∅, we obtain the first equation. The second equation corresponds to r = m. Then G is counted by F_{1} − G, G_{2} = ∅, and deleting of E (counted by x) from G_{1} yields a simple 12-free graph G_{3}. G_{3} is counted by 4(G − 1) + 3(F_{1} − G) + 1 = 3F_{1} − 3 + G, according to the possible non/identifications of its endvertices with 1 and r = m. This gives the second equation.

Elimination of G in the system (10) produces the equation

8xF_{1}^{2} − (1 + 11x)F_{1} + 1 + 4x = 0.

Quadratic formula gives us formula (8).

All noncrossing graphs arise from simple noncrossing graphs by repetitions of edges. Thus F_{2}(x) = F_{1}(x/(1−x)). Substituting x/(1−x) for x in the last equation, we obtain

8xF_{2}^{2} − (1 + 10x)F_{2} + 1 + 3x = 0.

Quadratic formula gives us formula (9). Comparing formulas (9) and (7) reveals that F_{2}(x) = (1 + S(2x))/2 and b_{n} = 2^{n−1}S_{n}. The radii of convergence of F_{i}(x) are the least positive roots of the discriminants 1 − 10x − 7x^{2} and 1 − 12x + 4x^{2}. □

Noncrossing simple graphs were enumerated, by the number of vertices and with isolated vertices allowed, by Domb and Barrett [4] (and before them by Rev. T. P. Kirkman, A. Cayley, G. N. Watson, … — see [4]). We refer the reader to [5] for a more general and elegant treatment and to Rogers [18] for related results. For n ≥ 3 the number g_{n} of noncrossing simple graphs with n (possibly isolated) vertices is given by g_{n} = 2^{n}S_{n−2} [5]. We have just proved that b_{n}, the number of noncrossing (possibly not simple) graphs with n edges, is given by b_{n} = 2^{n−1}S_{n}. Hence, for n ≥ 3,

g_{n} = 8b_{n−2}.

Pavel Podbrdský [17], an undergraduate student of Charles University, has recently found a bijective explanation of this identity.

Only little changes if we enumerate noncrossing graphs by order. We stress that in our approach vertices are never isolated.

Theorem 4.3 If v_{n} is the number of simple 12-free graphs with n vertices and F_{3}(x) = ∑_{n≥0} v_{n}x^{n} = 1 + x^{2} + 4x^{3} + 25x^{4} + 176x^{5} + ⋯, then

F_{3}(x) = \frac{1}{2(1+x)^{3}} (2 + 7x + 3x^{2} − x\sqrt{1 − 10x − 7x^{2}}).  (11)

The rough asymptotics of v_{n} is the same as that of a_{n} in the previous theorem. For n > 2 we have the companion identity v_{n} + 3v_{n−1} + 3v_{n−2} + v_{n−3} = 8a_{n−2}.

Proof. 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) = ∑_{n≥0} g_{n}x^{n} = 1 + x + 2x^{2} + 8x^{3} + 48x^{4} + ⋯ satisfies G(x) = 8x^{2}F_{2}(x) + 1 + x − 6x^{2}. Finally, F_{3}(x) = \frac{1}{1+x}G(x/(1 + x)). It is an inversion of the relation G(x) = \frac{1}{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)^{3}F_{3}(x) = 8x^{2}F_{1}(x) + 1 + 3x − 4x^{2}. Thus the identity. Formula (11) follows from (8). □

An alternative way is to use the decomposition from the proof of Theorem 4.2. Equation (1 + x)^{3}F_{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.

Theorem 4.4 Let a_{n} be the number of 12-free hypergraphs of weight n. Then, for n > n_{0},

a_{n} < 10^{n}.

Proof. If F_{1} = r_{0} + r_{1}x + ⋯ and F_{2} = s_{0} + s_{1}x + ⋯ are two power series with real coefficients and r_{i} ≤ s_{i} for all i = 0, 1, …, we write F_{1} ≤^{∗} F_{2}. Let H be 12-free and ⋃ H = [m]. Of the edges X ∈ H such that 1 ∈ X we choose those having the largest second vertex (the vertex min(X\{1})) and of them we choose those having the largest cardinality t. Since H is 12-free, the edges X we get must be all parallel, say to X = {x_{1} = 1, x_{2}, …, x_{t}}_{<}. We define H_{i}, i ∈ [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 H_{i} and H_{i−1}. So each edge is in exactly one H_{i} or is parallel to X. Each H_{i} is 12-free.

Let F = ∑_{n≥0} a_{n}x^{n} = 1 + x + ⋯ be the GF counting 12-free hypergraphs by weight. Bounding the number of non/identifications of the endvertices of the H_{i}s by 4 if H_{i} ≠ ∅ and by 1 else, and disregarding that for t > 3 the edge X is unique, we obtain the inequality

F ≤^{∗} 1 + ∑_{t≥1} \frac{x^{t}(4F − 3)^{t}}{1 − x^{t}} ≤^{∗} 1 + \frac{1}{1 − x} ∑_{t≥1} x^{t}(4F − 3)^{t} = 1 + \frac{x(4F − 3)}{(1 − x)(1 − x(4F − 3))}.

We used that x^{t}/(1 − x^{t}) ≤^{∗} x^{t}/(1 − x). Let G be the power series satisfying the inequality as equality, that is,

G = 1 + \frac{x(4G − 3)}{(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 α = 0.10325 … of the discriminant x^{4} + 4x^{3} + 22x^{2} − 12x + 1. Induction on exponents shows that F ≤^{∗} G. Thus, for ε > 0 and n > n_{0}(ε),

a_{n} < (1/α + ε)^{n} = (9.68460 … + ε)^{n}.
□

We invest more effort and count the noncrossing hypergraphs exactly. The calculations below were performed by means of the computer algebra system MAPLE.

Theorem 4.5 Let a_{n} be the number of 12-free hypergraphs of weight n. F (x) = ∑_{n≥0} a_{n}x^{n} = 1 + x + 3x^{2} + 10x^{3} + 40x^{4} + ⋯ satisfies the equation

P_{4}(x)F^{4} + P_{3}(x)F^{3} + P_{2}(x)F^{2} + P_{1}(x)F + P_{0}(x) = 0  (12)

where P_{4}(x) = (2x)^{7}(x − 1)^{3}, P_{3}(x) = −32x^{6}(8x^{2} − 11x − 1)(x − 1)^{2}, 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} ≐ (6.06688 …)^{n}

where 6.06688 … is an algebraic number of degree 23.

Proof. Let b_{n}, respectively c_{n}, be the numbers of 12-free hypergraphs H of weight n such that the 2-set {min ⋃ H, max ⋃ H}, respectively the singleton {min ⋃ H}, is not an edge of H. Let G(x) = ∑_{n≥0} b_{n}x^{n} = 1+x+2x^{2}+⋯ and H(x) = ∑_{n≥0} c_{n}x^{n} = 1+x^{2}+⋯ be the corresponding GFs. We prove that the series F, G, and H satisfy the equations

F = 1 + \frac{xF}{1 − x} + (F − G)(F + H − 1) + \frac{x^{3}(2F + 2H − 3)^{2}(F + H − 1)}{(1 − x)(1 − x^{3})}
+\frac{(F + H − 1)x^{4}(2F + 2H − 3)^{3}}{(1 − x)(1 − x(2F + 2H − 3))}  (13)
F − G = \frac{x^{2}(3F + G − 2 − 1/(1 − x))}{1 − x^{2}}  (14)
F − H = \frac{xF}{1 − x} + \frac{x(H − 1)}{1 − x}.  (15)

Elimination of G and H from the system yields (12).

Suppose ⋃ H = [m]. We define F (H) = {X ∈ H : 1 ∈ X, |X| ≥ 2}, J(H) to be the multiset of the edges X ∈ F (H) attaining the maximum value of min(X\{1}), and j(H) = max |X|, X ∈ J(H). To prove equation (13), we partition noncrossing hypergraphs into five classes that correspond to the five summands on the right hand side.

The first class consists of H = ∅ and is counted by 1. In the remaining classes H ≠ ∅. In the second class F (H) = ∅. Such an H consists of parallel singletons {1} followed by an 12-free hypergraph and the class is counted by (x + x^{2} + ⋯)F. In the remaining classes F (H) ≠ ∅. In the third class j(H) = 2. For such an H all edges in J(H) are parallel to {1, m′}, 1 < m′ ≤ m. We decompose H in H_{1} and H_{2}: H_{1} has the edges lying in [1, m′] and H_{2} the edges lying in [m′, m] except the singletons {m′}. By the 12-freeness, each edge is either in H_{1} or in H_{2}. Hypergraphs H_{1} are counted by F − G. To count H_{2}, consider r = min ⋃ H_{2}. For {r} ∉ H_{2} there are two options (except for H_{2} = ∅): m′ and r can be identified or left separate. The counting series is 2H − 1. If {r} ∈ H_{2}, m′ and r must be distinct and the counting series is F − H. All possibilities are counted by 2H − 1 + F − H = F + H − 1. Multiplying both factors, we obtain the third summand.

In the fourth class j(H) = 3. All three-element edges in J(H) must be parallel to {m_{0} = 1, m_{1}, m_{2}}_{<}. We delete them and decompose the rest in H_{i}, i ∈ [3]. H_{i} has the edges lying in [m_{i−1}, m_{i}], where m_{3} = m, except the singletons {m_{i−1}}. By the 12-freeness, each edge nonparallel with {1, m_{1}, m_{2}} and {1} is in exactly one H_{i}. Edges parallel with {1, m_{1}, m_{2}} and {1} are counted by x^{3}/(1 − x^{3}) and 1/(1 − x). We show that H_{i}, i ∈ [2] are counted by 2F + 2H − 3. Let r_{1} = min ⋃ H_{1} and r_{2} = max ⋃ H_{1}. The non/identification of r_{2} and m_{1} gives us always two options. For {r_{1}} ∉ H_{1} the non/identification of r_{1} and 1 gives two further options. So 4H − 3 counts the possibilities. For {r_{1}} ∈ H_{1} there are just two non/identifications (r_{2} and m_{1}) and the counting series is 2(F − H). Hence 4H − 3 + 2(F − H) = 2F + 2H − 3 in total. For H_{2} the argument is the same. H_{3} is counted by F +H −1, as in the third case. Multiplying the five factors, we obtain the fourth summand.

In the fifth class t = j(H) ≥ 4. The argument is as in the fourth case, except that the edge X ∈ J(H), |X| = t is unique. We delete X and decompose the rest in H_{1}, …, H_{t} as in the previous case. Each edge distinct to X and nonparallel with {1} lies in exactly one H_{i}. Each of H_{1}, …, H_{t−1} is counted by 2F +2H −3 and H_{t} is counted by F +H −1. Not forgetting to count the singleton edges {1}, we obtain the last fifth summand

\frac{1}{1 − x} ∑_{t≥4} x^{t}(2F + 2H − 3)^{t−1}(F + H − 1).

This concludes the proof of (13).

We prove equation (14). Consider an 12-free H having at least one edge {1, m}, m > 1; recall that m is the last vertex of H. On one hand H is counted by F − G. On the other hand, consider the hypergraph H_{1} obtained by deleting the edges parallel to {1, m}. Let m_{1} = min ⋃ H_{1} and m_{2} = max ⋃ H_{1}. If m_{1} ≠ m_{2} and {m_{1}, m_{2}} ∉ H_{1}, we have four non/identifications of the pairs m_{1}, 1 and m_{2}, m. Then H_{1} is counted by 4(G−1/(1−x)). If m_{1} ≠ m_{2} and {m_{1}, m_{2}} ∈ H_{1}, we have three non/identifications and H_{1} is counted by 3(F − G). The remaining cases when H_{1} = ∅ 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 (14).

To prove equation (15), consider 12-free hypergraphs H with at least one edge {1}. They are counted by F − H. On the other hand, H arises either by appending an 12free 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 (15).

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 (12). 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 & \frac{∂A(x, F)}{∂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 α = 0.16482 … (of the third factor), we have R = α and a_{n} ≐ (1/R)^{n} = (6.06688 …)^{n}. □

Theorem 4.6 Let a_{n} be the number of simple 12-free hypergraphs of weight n. F (x) = ∑_{n≥0} a_{n}x^{n} = 1 + x + 2x^{2} + 7x^{3} + 27x^{4} + ⋯ satisfies the equation

P_{3}(x)F^{3} + P_{2}(x)F^{2} + P_{1}(x)F + P_{0}(x) = 0  (16)

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} ≐ (5.79950 …)^{n}

where 5.79950 … is an algebraic number of degree 15.

Proof. Series G(x) = 1 + x + x^{2} + ⋯ and H(x) = 1 + x^{2} + ⋯ are defined as in the previous proof (now for simple hypergraphs). We have the simpler algebraic system

F = 1 + xF + (F − G)(F + H − 1) + \frac{(1 + x)(F + H − 1)x^{3}(2F + 2H − 3)^{2}}{1 − x(2F + 2H − 3)}

(17)

F − G = x^{2}(3F + G − x − 3)  (18)
F − H = xF + x(H − 1).  (19)

Eliminating G and H, we obtain equation (16).

The proof of equations (17)–(19) 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 (16). □

The next theorem shows that order is a more appropriate counting parameter.

Theorem 4.7 Let a_{n} be the number of simple 12-free hypergraphs of order n. F (x) = ∑_{n≥0} a_{n}x^{n} = 1 + x + 5x^{2} + 109x^{3} + 3625x^{4} + ⋯ satisfies the equation

P_{3}(x)F^{3} + P_{2}(x)F^{2} + P_{1}(x)F + P_{0}(x) = 0  (20)

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} ≐ (63.97055 …)^{n}

where 63.97055 … is the only positive real root of 5x^{4} − 316x^{3} − 242x^{2} − 284x − 107.

Proof. It is not too difficult to adapt the decomposition used in the last two proofs for counting by order. We obtain the algebraic system

F = 1 + xF + \frac{1}{x}(F − G)(xF + H − 1)

+\frac{2(xF + H − 1)((x + 1)H + (x^{2} + x)F − 2x − 1)^{2}}{x^{2} − x((x + 1)H + (x^{2} + x)F − 2x − 1)}

F − G = −1 − 3x + (2x + x^{2})F + G
F − H = xF + H − 1

and proceed as before. We omit the details. However, notice that now A(x, F) in equation (20) 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. □

5 21-free graphs and maximal 21-free hypergraphs

A hypergraph is 21-free if it does not have vertices a < b < c < d and distinct (but possibly parallel) edges X, Y such that a, d ∈ X and b, c ∈ Y. Such structures could be called nonnested ([21], section 7.3, but see our remark below). We review known results for permutations, matchings, and partitions.

There is only one 21-free permutation of size n. The number of 21-free matchings with n edges is the same as in the noncrossing case, the Catalan number C_{n}. The proof goes via an easy bijection with trees and we leave it to the reader. (”Nonnested matchings” seem to absent in the extensive list of Catalan structures in exercise 6.19 of [23]).

Let us look at nonnested partitions. A related but different concept is that of nonnesting partitions. These are partitions of [n] such that if 1 ≤ a < b < c < d ≤ n are four numbers such that a, d ∈ A and b, c ∈ B for two distinct blocks A and B, then e ∈ A for some e, b < e < c (exercises 5.44 and 6.19.uu in [23]). A minor confusion arises in [21] on p. 403 where Simion speaks of nonnested partitions (or abba-free partitions in the terminology of Klazar [10]) but, apparently, means actually nonnesting partitions. The claim maid there that the numbers of nonnested and noncrossing partitions of the same order are equal is incorrect but it is true for nonnesting partitions, see exercise 6.19.uu in [23].

Anyway, if a_{n} is the number of 21-free (=nonnested=abba-free) partitions of order n and F (x) = ∑_{n≥1} a_{n}x^{n} = x + 2x^{2} + 5x^{3} + 14x^{4} + ⋯, then, as proved in [10],

F (x) = \frac{−x + 3x^{2} − 2x^{3} − x\sqrt{1 − 2x − 3x^{2}}}{−2 + 8x − 6x^{2} + 2x^{3}} .

We leave to the interested reader to check as an exercise that there exist C_{5} = 42 noncrossing but a_{5} = 41 nonnested partitions of order 5. The numbers a_{n}, {a_{n}}_{n≥1} = {1, 2, 5, 14, 41, 123, 374, 1147, 3538, …}, are closely related to the Motzkin numbers (for them consult exercises 6.37 and 6.38 in [23]). In the case of edges with more than 2 elements the nonnested condition is more restrictive than the noncrossing condition.

In [10] it was also proved that if b_{n} is the number of 21-free partitions of order n in which no block contains two consecutive numbers and F (x) = ∑_{n≥1} b_{n}x^{n} = x + x^{2} + 2x^{3} + 5x^{4} + 13x^{5} + ⋯, then

F (x) = \frac{x}{2} (1 + \sqrt{\frac{1 + x}{1 − 3x}} ) .

Further values of b_{n} are: {b_{n}}_{n≥2} = {1, 2, 5, 13, 35, 96, 267, 750, 2123, …}. This GF, in a slightly modified form, and its coefficients appeared first in Gouyou-Beauchamps and Viennot [8] (see also exercise 6.46 in [23]). Stated in our notation, they proved that the numbers b_{n} count (i) (n − 1)-element sets X of plane lattice point in which each point is connected to (0, 0) by a lattice path that makes steps only (0, 1) and (1, 0) and lies completely in X and (ii) words over {−1, 0, 1} of length n − 2 with nonnegative partial sums. In fact, they gave a bijection between the sets (i) and (ii). Very simple bijection has been recently given by Shapiro [19]. Jan Němeček [15], an undergraduate student of Charles University, has recently found a bijection between 21-free partitions and words described in (ii).

We turn to 21-free graphs and begin with characterizing the maximal simple ones. Let G be a maximal simple 21-free graph with ⋃ G = [n], n ≥ 2. We set I_{i} = {v ∈ [i + 1, n] : {i, v} ∈ G}, i ∈ [n−1]. It follows that I_{i} are nonempty intervals, max I_{i−1} = min I_{i} for every i ∈ [n − 1] (we set I_{0} = [2]), and |I_{i}| ≥ 2 whenever i, i < n − 1 is the last but one vertex of I_{0} ∪ I_{1} ∪ ⋯ ∪ I_{i−1}. We delete the n − 1 edges {i, max I_{i}}. The remaining edges form a tree T with ⋃ T = [n − 1] (1 is the root and the vertices are ordered as numbers). G can be uniquely recovered from T . Thus, as in the noncrossing case, every maximal simple 21-free graph of order n has n − 1 + n − 2 = 2n − 3 edges and there are C_{n−2} of them. (It is well known that the number of trees of order n is C_{n−1}, exercise 6.19.e in [23].)

Interestingly, this extends to all graphs: the numbers of 21-free graphs in each of the four problems (counting by order or size, allowing isolated vertices or multiple edges) are the same as those of noncrossing graphs.

Theorem 5.1 The numbers a_{n} of simple 21-free graphs of size n are the same as those of noncrossing graphs in Theorem 4.2 and the GF is given by equation (8). The numbers v_{n} of simple 21-free graphs of order n are the same as those of noncrossing graphs in Theorem 4.3 and the GF is given by equation (11).

Proof. We begin with the second problem and find the GF of the numbers v_{n}. By the last edge E = {a, n} of a simple 21-free graph G, ⋃ G = [n] we mean the shortest edge incident with the last vertex n. We define the span of E as m = 2(n−a+1). Clearly, no i ∈ [a + 1, n] is the first vertex of an edge. A new last edge E′ = {a′, n′}_{<} may be added to G by selecting one of the m positions for a′ (the vertices in [a, n], the gaps between them, and the space after n) and one of the two positions for n′ (n and the space after n). All these 2m − 3 choices (3 choices a′ = n′ = n, a′ > n′ = n, and a′ = a, n′ = n must be excluded) are available regardless of the structure of G. Consider the bivariate GF

F (x, y) = ∑_{n,m≥2} v_{n,m}x^{n}y^{m} = x^{2}y^{4} + x^{3}(3y^{4} + y^{6}) + ⋯

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 G′ = G ∪ {E′} and the span of E′ in G′, we see that the addition of E′ amounts formally to the replacement

x^{n}y^{m} → x^{n}(y^{4} + y^{6} + ⋯ + y^{m−2}) + x^{n+1}(2(y^{4} + y^{6} + ⋯ + y^{m+2}) − y^{m+2})

+x^{n+2}(y^{4} + y^{6} + ⋯ + y^{m+2})

= x^{n} (\frac{y^{m} − 1}{y^{2} − 1} − 1 − y^{2}) + x^{n+1} (2y^{4} \frac{y^{m} − 1}{y^{2} − 1} − y^{m+2}) + x^{n+2}y^{4} \frac{y^{m} − 1}{y^{2} − 1}.

In terms of the GF,

F (x, y) = x^{2}y^{4} + \frac{F (x, y) − F (x, 1)}{y^{2} − 1} − (1 + y^{2})F (x, 1) + \frac{2xy^{4}(F (x, y) − F (x, 1))}{y^{2} − 1}

−xy^{2}F (x, y) + \frac{x^{2}y^{4}(F (x, y) − F (x, 1))}{y^{2} − 1}.

This can be rewritten as

((x + x^{2})y^{4} + (x − 1)y^{2} + 2) · F (x, y) = (1 + x)^{2}y^{4} · F (x, 1) − x^{2}y^{4}(y^{2} − 1). (21)

Solving (x + x^{2})y^{4} + (x − 1)y^{2} + 2 = 0 for y^{2}, we obtain

y^{2} = \frac{1}{2x(1+x)}(1 − x − \sqrt{1 − 10x − 7x^{2}}).

This series, substituted for y^{2}, makes the left hand side of equation (21) vanish. Solving the resulting equation for F (x, 1), we get

F (x, 1) = \frac{x^{2}(y^{2} − 1)}{(1 + x)^{2}} = \frac{x − 3x^{2} − 2x^{3} − x\sqrt{1 − 10x − 7x^{2}}}{2(1 + x)^{3}} .

This coincides, after addition of 1, with formula (11).

The first problem, counting simple 21-free graphs by size, is similar and easier. It suffices to adjust the above replacement x^{n}y^{m} → ⋯ 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^{2}y^{4} to xy^{4}. Proceeding as before and adding 1 to the result, we arrive at the formula (8). □

Allowing multiple edges in the first problem corresponds to the substitution x → 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.

Theorem 5.2 Let M be the set of maximal simple 21-free hypergraphs of order n and a_{n} = |M|. Then, with F (x) = ∑_{n≥0} a_{n}x^{n} = 1 + x + x^{2} + x^{3} + 3x^{4} + 12x^{5} + ⋯ and n > 1,

F (x) = \frac{−2x^{7} + 8x^{6} − 11x^{5} + 21x^{4} − 31x^{3} + 23x^{2} − 8x + 1}{(x − 1)^{2}(4x^{4} − 15x^{3} + 16x^{2} − 7x + 1)},  (22)
max_{H∈M} e(H) = 4n − 5, and max_{H∈M} i(H) = 8n − 12.

The rough asymptotics is a_{n} ≐ (3.67871 …)^{n} where 3.67871 … is the largest positive root of x^{4} − 7x^{3} + 16x^{2} − 15x + 4.

Proof. In this proof a 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(H) and i(H). Suppose H ∈ M with ⋃ H = [n], n ≥ 2. H has at most n 1-edges contributing weight ≤ n. By the above characterization of maximal simple 21-free graphs, H has at most 2n − 3 2-edges contributing weight ≤ 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 H has at most n − 2 big edges contributing weight ≤ n − 2 + 2(n − 2) = 3n − 6. In total, e(H) ≤ n + 2n − 3 + n − 2 = 4n − 5 and i(H) ≤ n + 4n − 6 + 3n − 6 = 8n − 12. The hypergraphs

H_{1} = ({1, i, n}, {1, n}, {1, i}, {i, n}, {j} : i ∈ [2, n − 1], j ∈ [n])

and

H_{2} = ({i, i + 1, i + 2}, {i, i + 2}, {j, j + 1}, {k} : i ∈ [n − 2], j ∈ [n − 1], k ∈ [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 G is an I, J-graph, where I < J are two intervals in N, if G is simple, 21-free, ⋃ G = I ∪ J, each edge starts in I and ends in J, and G is maximal to these properties. We define the six alphabets

A_{0} = {([n], ∅) : n ∈ N_{0}} where [0] = ∅
A_{1} = {([n], {x}) : n ∈ N, x ∈ [n]}
A_{2} = {([n], X) : n ∈ N_{0}, X ⊂ [n]}
A_{3} = {([n], i, j, G) : 1 ≤ i < j ≤ n, n ≥ 2, G is an [i], [j, n]-graph}
A_{4} = {([n], i) : 1 < i ≤ n, n ≥ 2}
A_{5} = {d} (d is a symbol whose meaning is explained later).

In fact, we will use a more general notation a = ([k, l], ⋯) for the letters of A_{0}, …, A_{4}: a is understood to be identical with ([n], ⋯) where l − k + 1 = n and the structure ⋯ is moved to [n]. The length l(a) of a ∈ A_{i} is the length l − k + 1 = n of the underlying interval and l(d) = −1. The length l(u) of a word u is the sum of lengths of all its letters.

We prove that, for n ≥ 2, M is in bijection with the words u generated by the language expression

(A_{2} − A_{1}) + (A_{0}A_{4} + (A_{2} − A_{0})A_{3})(A_{5}A_{4} + A_{2}A_{3})^{∗}A_{2}.  (23)

(Here AB are words of the form ab for a ∈ A and b ∈ B, A − B is the set difference (provided B ⊂ A), A + B is the set union (provided A ∩ B = ∅), and A^{∗} means {∅} + A + AA + AAA + · · ·.) The bijection has the property that for H corresponding to u we have v(H) = l(u) + 2. We describe how to transform H in u.

Let H ∈ M with ⋃ H = [n], n ≥ 2. If n = 2, H = ({1}, {2}, {1, 2}) and we set u = a_{1} = (∅, ∅) ∈ A_{0}. Let n ≥ 3 and m ∈ [3, n] be the last vertex such that 1 and m lie in a common edge. Clearly, m is defined and the edge X with 1 = min X and m = max X is big; otherwise we could add {1, 2, m} to the edges. We distinguish the cases m = n and m < n. Let X = {x_{1} = 1, x_{2}, …, x_{t} = m}_{<}, t ≥ 3.

Suppose m = n. If t = 3, H is the above hypergraph H_{1} and we let H correspond to u = a_{1}, a_{1} = ([2, n − 1], ∅) ∈ A_{0}\{(∅, ∅)}. If t ≥ 4, X is unique and determines uniquely H. We let H correspond to u = a_{1}, a_{1} = ([2, n − 1], {x_{2}, …, x_{t−1}}) ∈ A_{2}\(A_{0} ∪ A_{1}). We obtain the first summand of equation (23).

Case m < n corresponds to the second summand. If t = 3, we take the X with the maximum x_{2}. If t ≥ 4, X is unique. There is a big edge Y = {y_{1}, …, y_{t′}}_{<} such that y_{1} ∈ [x_{t−1}, x_{t} − 1] and y_{2} ≥ x_{t}. The existence of Y follows by a similar argument as that of X. If t′ ≥ 4, Y is unique. If t′ = 3, Y is unique up to y_{2} and we take the Y with the maximum y_{2}. If t = 3, the choice of X implies y_{1} = x_{2}. We distinguish the cases t = 3 and t ≥ 4.

For t = 3 we start with u = a_{1}a_{2} … where a_{1} = ([2, x_{2} − 1], ∅) ∈ A_{0} and a_{2} = ([x_{2}, y_{2}], x_{3}) ∈ A_{4}. If t ≥ 4, u = a_{1}a_{2} … with a_{1} = ([2, x_{t−1} − 1], {x_{2}, …, x_{t−2}}) ∈ A_{2}\A_{0} and a_{2} = ([x_{t−1}, y_{2}], y_{1}, x_{t}, G_{1}). Here G_{1} is formed by the 2-edges joining [x_{t−1}, y_{1}] and [x_{t}, y_{2}]. It is easy to see that G_{1} is an [x_{t−1}, y_{1}], [x_{t}, y_{2}]-graph. Hence, a_{2} ∈ A_{3}. This gives the first factor of the second summand of (23). We distinguish the cases y_{t′} = n and y_{t′} < n.

For y_{t′} = n we finish u = a_{1}a_{2}a_{3} by a_{3} = ([y_{2}+1, n−1], {y_{3}, …, y_{t′−1}}) ∈ A_{2} (the third factor). If y_{t′} < n, there is a big edge Z = {z_{1}, …, z_{t′′}}_{<} such that z_{1} ∈ [y_{t′−1}, y_{t′} − 1] and z_{2} ≥ y_{t′}. Z is unique for t′′ ≥ 4 and for t′′ = 3 we take the Z with the largest middle element. We distinguish the cases t′ = 3 and t′ ≥ 4.

For t′ = 3 the choice of Y implies z_{1} = y_{2}. We continue u = a_{1}a_{2}a_{3}a_{4} … by a_{3} = d ∈ A_{5} and a_{4} = ([y_{2}, z_{2}], y_{3}) ∈ A_{4}. Notice that the underlying intervals of a_{2} and a_{4} overlap in y_{2}. This decrease of order by 1 is marked by a_{3} = d. For t′ ≥ 4 we continue u = a_{1}a_{2}a_{3}a_{4} … by a_{3} = ([y_{2} + 1, y_{t′−1} − 1], {y_{3}, …, y_{t′−2}}) ∈ A_{2} and a_{4} = ([y_{t′−1}, z_{2}], z_{1}, y_{t′}, G_{2}) ∈ A_{3}, where G_{2} is the [y_{t′−1}, z_{1}], [y_{t′}, z_{2}]-graph formed by the corresponding 2-edges. The word a_{3}a_{4} belongs to the second factor of the second summand in (23).

If z_{t′′} = n, we finish u by some a_{5} ∈ A_{2}. Else we take the next big edge and continue in the explained manner in the loop (A_{5}A_{4} + A_{2}A_{3})^{∗} until we eventually finish u by a letter from A_{2}. This way the u corresponding to H is obtained.

The big edges X, Y, … and the graphs G_{1}, G_{2}, … determine H completely, because the other edges are forced uniquely by maximality. These are of three types. The singletons {i}, i ∈ [n]. The 2-edges incident with the endvertices of X, Y, …, for example {y_{1}, i}, i ∈ [y_{2} + 1, y_{3}] and {j, y_{t′}}, j ∈ [y_{t′−2}, y_{t′−1} − 1]. The 3-edges sharing endvertices with those of X, Y, … that are 3-edges, for example {y_{1}, i, y_{3}}, i ∈ [x_{t}, y_{2} − 1] if t′ = 3.

Therefore H can be uniquely reconstructed from u. For the sake of brevity of the paper we omit the description of the inverse correspondence. The bijection matching M with the words defined by (23) (and transforming v(H) to l(u) + 2) is established.

We associate with the alphabet A_{i} the GF F_{i} = ∑_{a∈A_{i}} x^{l(a)}. The desired GF F is given by F = 1+x+x^{2}G, where G is the GF obtained from equation (23) by substituting F_{i} for A_{i}. A^{∗} translates as (1 − F_{A})^{−1} and the other operations in the obvious manner. We have F_{0} = (1 − x)^{−1}, F_{1} = x(1 − x)^{−2}, F_{2} = (1 − 2x)^{−1}, F_{3} = x^{2}(1 − x)^{−1}(1 − 2x)^{−1}, F_{4} = x^{2}(1 − x)^{−2}, and F_{5} = x^{−1}. Only F_{3} needs an explanation.

Each I, J-graph corresponds uniquely to |I| nonempty intervals J = J_{1}∪J_{2}∪⋯∪J_{|I|} such that max J_{i−1} = min J_{i}, min J_{1} = 1, and max J_{|I|} = n. These intervals correspond uniquely to the multisubset {max J_{1}, …, max J_{|I|−1}} of J of cardinality |I| − 1. So we have \binom{|J|+|I|−2}{|I|−1} I, J-graphs with given I and J. The number of the letters ([n], i, j, G) ∈

A_{3} with a given l = i + n − j + 1 is \binom{l−2}{0} + \binom{l−2}{1} + ⋯ + \binom{l−2}{l−2} = 2^{l−2} and the total number is 2^{0} + 2^{1} + ⋯ + 2^{n−2}. This gives F_{3}.

Substituting F_{i} for A_{i}, we get the series G and then equation (22). The radius of convergence is the least positive root of the denominator. □

Using the last theorem and the inequalities of Lemma 2.1, we obtain for p = 21 and n > n_{0} relations c_{2} = 3.67871 …, c_{3} = 4, c_{4} = 8, c_{1} < 4 · 2^{4} = 64, c_{5} < 64, and c_{6} < 2 · 64 = 128.

6 Concluding remarks

Bound (1) in general cannot be improved to O(n). For example, it is known that if the sequence u ∈ [n]^{∗} is 2-sparse, does not contain 121212, and has the maximum length, then

n2^{α(n)} ≪ |u| ≪ n2^{α(n)}.

(We use here, as it is common in some texts, ≪ as a synonym to the O(⋯) notation.) For more information see the book of Sharir and Agarwal [20].

Another extension of the problem of forbidden permutations was given by Alon and Friedgut [1]. They extend the avoidance of permutations to the words in N^{∗}, apply (6) to prove S_{n}(p) < c^{n} for unimodal p, and prove a general almost exponential bound analogous to Theorem 2.5. Our proof of that theorem is inspired by their argument. The bound they obtain is somewhat better compared to ours, due to a more complicated induction step. Many enumerative results for avoidance in N^{∗} were found by Burstein [3].

Bound (6) for the forbidden ”N” sequence was applied in Section 3 and in [1]. Third application, to a problem in combinatorial geometry, is in Valtr [24].

We remarked in Section 1 that the conjecture C1 does not hold if the forbidden reduction R is different from H_{p} with added singleton edges. But the extremal conjectures then still may hold for some Rs. For example, one sees easily that the conjecture C4 holds if R = ({1}_{1}, {1}_{2}) or R = ({1, 2}, {1, 3}). Theorem 3.3 is a result of this type.

Some extremal problems closely related to ours were investigated before. Füredi [6] proved that if G is a simple graph of order n that does not contain as a subgraph the 4-path ({1, 5}, {2, 4}, {3, 4}, {3, 5}) and has the maximum number of edges, then

n log n ≪ e(G) ≪ n log n.

See also Füredi and Hajnal [7].

Theorem 5.1 calls for a bijective explanation. It would be nice to have counterparts of Theorems 4.4–4.7 for 21-free hypergraphs. These, however, seem considerably more difficult to count than noncrossing hypergraphs. We hope to address these and related questions in future investigations.

References

[1] N. Alon and E. Friedgut, On the number of permutations avoiding a given pattern, J. Comb. Theory, Ser. A 89 (2000), 133–140.

[2] M. Bóna, The solution of a conjecture of Stanley and Wilf for all layered patterns, J. Comb. Theory, Ser. A 85 (1999), 96–104.

[3] A. Burstein, Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998.

[4] C. Domb and A. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341–358.

[5] P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math. 204 (1999), 203–229.

[6] Z. Füredi, The maximum number of unit distances in a convex n-gon, J. Comb. Theory, Ser. A 55 (1990), 316–320.

[7] Z. Füredi and P. Hajnal, Davenport–Schinzel theory of matrices, Discrete Math. 103 (1992), 233–251.

[8] D. Gouyou-Beauchamps and G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. Appl. Math. 9 (1988), 334–357.

[9] M. Klazar, A general upper bound in extremal theory of sequences, Commentat. Math. Univ. Carol. 33 (1992), 737–746.

[10] M. Klazar, On abab-free and abba-free set partitions, Eur. J. Comb. 17 (1996), 53–68.

[11] M. Klazar, Counting pattern-free set partitions I: A generalization of Stirling numbers of the second kind, Eur. J. Comb. 21 (2000), 367–378.

[12] M. Klazar, The Füredi–Hajnal conjecture implies the Stanley–Wilf conjecture, 250– 255. In: D. Krob, A. A. Mikhalev and A. V. Mikhalev (Eds.), Formal Power Series and Algebraic Combinatorics. 12^{th} International Conference, FPSAC’00, Moscow, Russia, June 2000, Proceedings, Springer, Berlin, 2000.

[13] M. Klazar and P. Valtr, Generalized Davenport–Schinzel sequences, Combinatorica 14 (1994), 463–476.

[14] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), 333-350.

[15] J. Němeček, personal communication, 2000.

[16] A. M. Odlyzko, Asymptotic enumeration methods, 1063–1232. In: R. L. Graham, M. Grötschel and L. Lovász (Eds.), Handbook of Combinatorics, Vol. 2 , North-Holland, Amsterdam, 1995.

[17] P. Podbrdský, personal communication, 2000.

[18] D. G. Rogers, The enumeration of a family of ladder graphs. Part II: Schroeder and superconnective relations, Q. J. Math., Oxf. II 31 (1980), 491–506.

[19] L. W. Shapiro, Directed animals and Motzkin paths, manuscript 1999.

[20] M. Sharir and P. K. Agarwal, Davenport–Schinzel Sequences and Their Geometric Applications, Cambridge University Press, Cambridge, UK, 1995.

[21] R. Simion, Noncrossing partitions, Discrete Math. 217 (2000), 367–409.

[22] R. Simion and F. W. Schmidt, Restricted permutations, Eur. J. Comb. 6 (1985), 383–406.

[23] R. P. Stanley, Enumerative Combinatorics, Vol. 2 , Cambridge University Press, Cambridge, UK, 1999.

[24] P. Valtr, On geometric graphs with no k pairwise parallel edges, Discrete Comput. Geom. 19 (1998), 461–469.

[25] P. Valtr, Generalizations of Davenport–Schinzel sequences, 349–389. In: R. L. Graham, J. Kratochvíl, J. Nešetřil, F. S. Roberts (Eds.), Contemporary Trends in Discrete Mathematics, American Mathematical Society, Providence, RI, 1999.