GENERALIZED DAVENPORT–SCHINZEL SEQUENCES: RESULTS, PROBLEMS, AND APPLICATIONS

Martin Klazar^{1}

Department of Applied Mathematics (KAM) and Institute for Theoretical Computer Science (ITI),

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

                         klazar@kam.mff.cuni.cz

Received: 6/28/01 , Revised: 6/14/02, Accepted: 8/10/02, Published: 8/14/02

Abstract

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.

1. Introduction

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 [55] and Klazar [29]. Both are now outdated. Sharir and Agarwal [52] and Agarwal and Sharir [3] focus on geometric applications. Survey and historic sections can be found also in [27], [36], and [61], 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 λ_{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 λ_{3}(n) was discovered in [21]. 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 [1]. 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 [33] and [35].

1Supported by the project LN00A056 of the Ministry of Education of the Czech Republic.

An s-DS sequence, where s ≥ 1 is an integer, is any finite sequence u = a_{1}a_{2} … a_{l} over a fixed infinite alphabet A satisfying two conditions:

1. For every i = 1, 2, …, l − 1 we have a_{i} ≠ a_{i+1}, which means that u contains no immediate repetition.

2. There do not exist s indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{s} ≤ l such that a_{i_{1}} = a_{i_{3}} = a_{i_{5}} = ⋯ = a, a_{i_{2}} = a_{i_{4}} = a_{i_{6}} = ⋯ = b, and a ≠ b. That is, u contains no alternating subsequence of length s.

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, …, the letters a, b, c, d, …, 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 isomorphic. For our purposes isomorphic sequences are identical. Every element of A^{∗} is isomorphic to a unique normal sequence. A sequence u is normal if it is over the alphabet {1, 2, …, n} for some integer n > 0, every i ∈ {1, 2, …, n} appears in u, and the first occurrences of 1, 2, …, n in u, if we scan u from left to right, come in this order.

Example 1. There exist exactly ten normal 4-DS sequences u using at most 3 symbols:

u = ∅, 1, 12, 121, 1213, 12131, 123, 1231, 1232, and 12321. □

N and N_{0} denote the sets {1, 2, …} and {0, 1, 2, …}. We write [n], n ∈ N, for the set {1, 2, …, n}, and [a, b], a, b ∈ N, a ≤ b, for the set {a, a + 1, …, b}. For two functions f, g : N → R, the asymptotic notation f ≪ 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 ≪_{k} g, indicate that c depends only on the mentioned parameters. The notation f = o(g) means that f(n)/g(n) → 0 as n → ∞.

Extremal functions λ_{s}(n). For a sequence u = a_{1}a_{2} … a_{l} over A, we write |u| to refer to its lentgh l. S(u) = {a_{1}, a_{2}, …, a_{l}} is the set of symbols used in u, and ∥u∥ = |S(u)| is their number. Obviously, always |u| ≥ ∥u∥. We define, for the integers s, n ≥ 1,

λ_{s−2}(n) = max{|u| : u ∈ DS_{s} & ∥u∥ ≤ n}.  (1)

The function λ_{s−2}(n) measures the maximum length of s-DS sequences using at most n symbols. It is trivial that, for every n ≥ 1 and s ≥ −1, λ_{s}(n) < ∞, λ_{−1}(n) = 0, λ_{0}(n) = 1, λ_{1}(n) = n, λ_{s}(1) = 1 (for s ≥ 0), and λ_{s}(2) = s + 1.

The notation λ_{s}(n) for the maximum lengths of DS sequences was introduced in 1986 by Hart and Sharir [21] 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 [14]; N_{s}(n) = λ_{s−1}(n). In the survey of these results in Section 2 we use both the original and the modern notation.

Example 2 ([14]). We bound λ_{s}(n) in a rough way, determine λ_{2}(n) precisely, and bound λ_{3}(n) in a finer way.

We begin with the bound

λ_{s}(n) ≤ \binom{n}{2}s + 1  (2)

which holds for all n ≥ 1 and s ≥ 0. Suppose a sequence u = a_{1}a_{2} … a_{l} satisfies condition 1 (no immediate repetition) and ∥u∥ ≤ n, but its length l exceeds the bound. Then among the l − 1 ≥ \binom{n}{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 (2).

Let us prove now that for every n ≥ 1,

λ_{2}(n) = 2n − 1.

The sequences u = 1 2 … (n − 1) n (n − 1) … 2 1 show that λ_{2}(n) ≥ 2n − 1. We prove the opposite inequality by induction on n. Certainly λ_{2}(1) = 1. In every u ∈ DS_{4} with ∥u∥ ≤ n and |u| = λ_{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∥ ≤ n−1. By induction, λ_{2}(n) = |u| ≤ |v|+2 ≤ λ_{2}(n−1)+2 = 2(n−1)−1+2 = 2n−1.

We prove that

λ_{3}(n) ≪ n log n.

Let u ∈ DS_{5} with ∥u∥ ≤ n and |u| = λ_{3}(n). Note that the maximum length implies ∥u∥ = n. For every x ∈ 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∥ ≤ n − 1. Thus λ_{3}(n) = |u| ≤ |v| + k(x) + 2 ≤ λ_{3}(n − 1) + k(x) + 2. Summing these inequalities over all x ∈ S(u), we obtain the inequality nλ_{3}(n) ≤ nλ_{3}(n−1)+λ_{3}(n)+2n, which we rewrite as

\frac{λ_{3}(n)}{n} − \frac{λ_{3}(n − 1)}{n − 1} ≤ \frac{2}{n − 1}.

Summing these inequalities for 2, 3, …, n leads to the bound λ_{3}(n) ≤ n(1+2(1^{−1} +2^{−1} + ⋯ + (n − 1)^{−1})) ≪ n log n. □

2. The Early Period

The geometric origin of λ_{s}(n). Davenport and Schinzel introduced the sequences, which now bear their names, in 1965 in [14]. They were led to them by the following geometric problem. Suppose f_{1}, …, f_{n} : R → R are n continuous functions such that the equation f_{i}(x) = f_{j}(x) has for i ≠ j at most s solutions x ∈ 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} = (−∞, a_{1}), I_{2} = (a_{1}, a_{2}), I_{3} = (a_{2}, a_{3}), …, I_{l} = (a_{l−1}, ∞) so that the pointwise minimum function f(x) = min_{j=1...n} f_{j}(x) coincides on each I_{i} with a unique function f_{j(I_{i})}, 1 ≤ j(I_{i}) ≤ n, and j(I_{i}) ≠ 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}) … j(I_{l}) is an (s + 2)-DS sequence. Thus if every pair f_{i} and f_{j}, i ≠ 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 λ_{s}(n). This is the reason for the later −2 shift of s in λ_{s−2}(n) compared to DS_{s}. However, in [14] and all works prior to 1986, max{|u| : u ∈ DS_{s} & ∥u∥ ≤ 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) = λ_{s−1}(n).

A natural example of a system {f_{i}} with |{x ∈ R : f_{i}(x) = f_{j}(x)}| ≤ s for every fixed i ≠ j is any system of distinct polynomials of degree at most s. Or, as was the case in [14], 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 ([14]). They reduced geometry to combinatorics and asked about the values of N_{s}(n). In [14] they proved that

(λ_{s−1}(n) =) N_{s}(n) ≤ n(n − 1)s + 1  (3)
(λ_{2}(n) =) N_{3}(n) = 2n − 1  (4)
(λ_{3}(n) =) N_{4}(n) < 2n(1 + log n)  (5)
(λ_{s−1}(n) =) N_{s}(n) ≪_{s} n · exp(10(s log s)^{1/2}(log n)^{1/2}).  (6)

Their proofs of (3)–(5) are reproduced in Example 2. (We have slightly corrected the proof of (3) to obtain the somewhat better bound (2). Of the two proofs of (4) in [14], we present the second one, based on “an observation, made to us by Mrs. Turan that (…) one of the integers (…) occurs only once”.) They proved further that N_{s}(n) ≥ (s^{2} −4s+3)n−C(s) (s > 3 is odd) and N_{s}(n) ≥ (s^{2} − 5s + 8)n − C(s) (s ≥ 4 is even). Modifying these constructions, they obtained the bound N_{4}(n) > 5n − c.

Davenport’s results. In the posthumously published paper [13] (edited by Schinzel), Davenport improved (5) to N_{4}(n) ≪ 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 +∞, because N_{4}(m + n) ≥ N_{5}(m) + N_{5}(n) for every m and n (easy to see from the definition). He proved more specificly that

lim_{n→∞} \frac{N_{4}(n)}{n} ≥ 8.

Davenport’s third result is the inequality N_{4}(lm + 1) ≥ 6lm − m − 5l + 2 (l, m ∈ N), which was “found in collaboration with J. H. Conway”. It implies that N_{4}(n) ≥ 5n − 8, with the strict inequality for odd n ≥ 13 and even n ≥ 18. The note added in proof (apparently by Schinzel) says that Z. Kołba proved that N_{4}(2m) ≥ 11m − 13.

The results of Roselle and Stanton. (Recall that N_{s}(n) = λ_{s−1}(n).) Roselle and Stanton proved in [56] that N_{s}(3) = 3s − 4 (for even s > 3) and N_{s}(3) = 3s − 5 (for odd s > 3). In [49] they proved that N_{s}(4) = 6s − 13 (for even s > 4) and N_{s}(4) = 6s − 14 (for odd s > 4). Finally, in [48] 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 [48] also the bound N_{4}(n) ≥ 5n − 8 is proved (n ≥ 4). In [49] Roselle and Stanton gave the general bound (s > n)

N_{s}(n) ≥ \{ \begin{matrix}\binom{n}{2}s − F (n) & s is even \\ \binom{n}{2}s − F (n) − ⌊\frac{n−1}{2}⌋ & s is odd \end{matrix} \}  (7)

where F (n) = (2n^{3}+9n^{2}−32n+9)/12 for odd n ≥ 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 (2) and (7) yield the asymptotics N_{s}(n) = (1 + o(1))\binom{n}{2}s. But what if n is bigger?

Problem 1. The bounds (2) and (7) give

\frac{n^{3}(1 + o(1))}{3} < N_{n}(n) < \frac{n^{3}(1 + o(1))}{2}.

What is the precise asymptotics of N_{n}(n)? □

Further results. Peterkin [44] 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) ≥ 7n − 13 (n > 5) and N_{6}(n) ≥ 13n − 32 (n > 5).

Burkowski and Ecklund [12] 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 [12]: “… The following question was raised by D. J. Newman: Is there a word S in some Φ_{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)….”

Dobson and Macdonald [16] obtained a slight improvement of (7). We state one of their bounds: if n and r are even, then N_{n+r}(n) ≥ \frac{1}{6}(2n^{3} + 3n^{2}(r − 2) − 2n(3r − 5) + 6r). For n > 2r + 2 this improves (7). Their other bounds are similar.

Rennie and Dobson [46] derived the inequality

(n − 2 + \frac{1}{s − 3}) · N_{s}(n) ≤ n · N_{s}(n − 1) + \frac{2n − s + 2}{s − 3}.  (8)

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 [46], gives specific bounds for N_{s}(n) in the range 5 ≤ s ≤ 12 and 5 ≤ n ≤ 12. The upper bound is obtained from (8). The lower bound is the larger of the lower bounds given by Dobson and Macdonald or (shown in italic) by Roselle and Stanton in (7).

s  5  6  7  8
n
5 22 34 41 53
6 29  46–47 56–58 72–76
7 36–37 59–62 72–77 96–102
8 43–46 72–78 89–99 120–131
9 50–56 85–96 106–123 145–164
10 57–66 98–115 123–149 170–200
11 64–77 111–136 140–177 195–239
12 71–89 124–158 157–207 220–281
s  9  10  11  12
n
5 61 73 81 93
6 85–88 102–105 115–117 132–135
7 110–119 134–143 152–159 176–184
8 140–154 170–186 192–207 223–240
9 170–193 210–234 236–261 276–303
10 201–236 250–287 284–321 332–373
11 232–283 291–345 332–387 392–450
12 263–334 332–408 381–458 452–534

Mills [40] proved the inequalities N_{4}(k^{2} + 5 − j) ≥ 6k^{2} − 2k + 16 − 6j and N_{4}(k^{2} + k + 5 − j) ≥ 6k^{2} + 4k + 15 − 6j, where 0 ≤ j < k. In [40] and [41] he determined the values of N_{4}(n) for n ≤ 21:

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ N_{4}(n) & 1 & 4 & 8 & 12 & 17 & 22 & 27 & 32 & 37 & 42 & 47 & 53 & 58 & 64 \end{matrix}

\begin{matrix}n & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ N_{4}(n) & 69 & 75 & 81 & 86 & 92 & 98 & 104 \end{matrix}

[figure: S_{2}; S_{1}; S_{3}; 2; 1; 2; 3; 2; 3; 1; 3]

Figure 1: The lower envelope of plane segments.

The values of N_{4}(n) form the sequence A002004 of the database [54]. The formula N_{4}(n) = 5n − 8, valid for 4 ≤ n ≤ 11, breaks down later, as noted already by Davenport.

Szemerédi’s general bound. In 1974, Szemerédi [57] published a remarkable result with a difficult proof: for n → ∞,

N_{s}(n) ≪_{s} n log^{∗} n.  (9)

Here log^{∗} n is the smallest integer k > 0 such that e_{k} > n, where e_{1} = e = 2.71828 … and e_{i+1} = e^{e_{i}}. (Nothing changes if we replace e by any other base b > 1.) The key part of Szemerédi’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 (9) improved considerably both (6) and (5).

Mills’ article [41] and Stanton and Dirksen’s survey [55], both published in 1976, mark the end of the early investigations of N_{s}(n) = λ_{s−1}(n). DS sequences were dormant for the next 10 years.

3. Superlinear Growth

New bounds on λ_{3}(n): enigma solved. In the middle of 1980s, the importance of DS sequences for combinatorial and computational geometry was discovered, first by Atallah [7]. 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 [14]. The functions λ_{s}(n), s > 2, remained mysterious. Despite the effort invested in the proofs of (6) and (9), the O(n) upper bounds were not in sight and the correct orders of growth of λ_{s}(n) were unclear. Stanton and Dirksen conjectured in [55] that λ_{3}(n)/n → ∞.

Example 3 ([52]). We illustrate the role of DS sequences in combinatorial geometry by a classical example, which is very similar to the problem in [14] (we discussed it in the beginning of Section 2) but is more recent. Let S_{1}, S_{2}, …, 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}, …, 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}, …, 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, …, 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, …, n}, |u| ≤ l −2. In Figure 1, n = 3, l = 10, and u = 21232313. The graph of f is the lower envelope of the system {S_{1}, …, S_{n}}, u is the minimazing sequence, and the length |u| is the 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| ≤ λ_{3}(n). □

Another geometric connection was recently studied by Alon and Onn [6]. 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, …, p} and are of length n. See also Aviran and Onn [8].

New light on λ_{3}(n) was shed by Hart and Sharir in 1986 in their breakthrough article [21]. They proved that

nα(n) ≪ λ_{3}(n) ≪ nα(n),  (10)

where α(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 → N, i ∈ N, where F_{1}(n) = 2n and F_{i+1}(n) = F_{i}(F_{i}(… F_{i}(1) …)) with n iterations of F_{i}. The inverse Ackermann function is then defined by α(n) = min{m ∈ N : A(m) ≥ n}. Alternative definitions of the hierarchy and of A(n) can be found in the literature, but these hardly affect the values of α(n). The function α(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šetřil [39].) The asymptotics (10) was not only an improvement upon (9) for s = 4, but it settled almost completely the 20 years old riddle of Davenport and Schinzel about the growth rate of λ_{3}(n).

In [21], 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 [58] who pioneered applications of α(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 [52].) Komjáth [37] proved the superlinear lower bound λ_{3}(n) ≫ nα(n) by a construction purely in terms of sequences.

Wiernik and Sharir [64] 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 ≫ nα(n) portions. We come to the natural but open

Problem 2. Can every 5-DS sequence be realized as the minimazing sequence of a system of plane segments? □

In [52], 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 pseudosegments. These are graphs of continuous functions defined on intervals, each two of them intersecting in at most one point.

Example 4 ([64, 52]). Following [52], we decribe the construction of [64] proving λ_{3}(n) ≫ nα(n). One defines, by double induction, a two-dimensional array S : N×N → 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_{1}v_{1}u_{2}v_{2} … u_{N}v_{N},

where every u_{i} is a sequence of length m containing m distinct symbols, and v_{1}, …, v_{N} are possibly empty intermediate sequences. The sequences u_{i} are called fans or m-fans and v_{i} are called 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 … m, and N(1, m) = 1. If the row k ≥ 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 ≥ 1 be already defined, as well as the sequences in the row k + 1 up to the column m ≥ 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}, …, 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}, …, 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, …, M, we create sequences w′_{i}. We set

S(k + 1, m + 1) = w′_{1}w′_{2} … w′_{M} + w′_{0} = w_{1}^{∗}z_{1}w_{2}^{∗}z_{2} … w_{M}^{∗}z_{M},

INTEGERS:ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002),#A11 10

where the + indicates the following interleaving of w′_{1}w′_{2} … 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}, …, w′_{M}, each enlarged by one term coming from the fans of w′_{0}. Thus

N(k + 1, m + 1) = N(k + 1, m) · 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 · 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 [64] or [52], a sequence of numbers 1 ≤ m_{1} < m_{2} < ⋯ such that, writing n_{k} for ∥S(k, m_{k})∥ = m_{k} · N(k, m_{k}), the inequality |S(k, m_{k})| ≥ n_{k}α(n_{k}) − 3n_{k} holds. (We owe the superlinear growth of |S(k, m_{k})| to the duplications.) Hence, for every k ∈ N,

λ_{3}(n_{k}) ≥ n_{k}α(n_{k}) − 3n_{k}.  (11)

A simple interpolation argument of [52] shows that

λ_{3}(n) ≥ \frac{1}{2}nα(n) − 2n

holds for all n ∈ N. □

Hart and Sharir [21] proved the lower bound in (10) with the constant \frac{1}{4} + o(1). The constants achieved in the upper bound were 52 + o(1) in [21] and 68 + o(1) in [52]. (The objective of these works was not really to obtain the best constants.) Klazar [26] obtained the constant 4 + o(1) and in [31] he proved that

λ_{3}(n) < 2nα(n) + O(n\sqrt{α(n)}).  (12)

Problem 3. Does the limit

lim_{n→∞} \frac{λ_{3}(n)}{nα(n)}

exist? □

If it exists, (11) and (12) show that it lies in the interval [1, 2].

We answer in positive the question from the MR review of Burkowski and Ecklund [12] that we quoted in the previous section. We know that λ_{3}(n) > cn for large n for every constant c > 0. We deduce from it that for every k ∈ N there exists a 5-DS sequence v in which every symbol appears at least k times. Let v ∈ DS_{5} be such that |v| ≥ (k + 1)∥v∥ and ∥v∥ is as small as possible. If some symbol a ∈ 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 ∈ DS_{5} such that |w| ≥ (k + 1)∥w∥ and ∥w∥ ≤ ∥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 λ_{3}(n) < 5n for n < 22.

Bounds on λ_{s}(n) for s > 3. The next obvious step was to extend the new techniques to λ_{s}(n) for s > 3. Sharir in [50] proved the upper bound

λ_{s}(n) ≪ nα(n)^{c_{s}α(n)^{s−3}}

and in [51] the lower bound

λ_{2s−1}(n) ≫_{s} nα(n)^{s−1}.

Since λ_{2s}(n) ≥ λ_{2s−1}(n), this gives lower bounds for every λ_{s}(n).

This line of research culminated in 1989 in the long and technical work of Agarwal, Sharir and Shor [4]. For s = 4 they proved the estimate

n2^{α(n)} ≪ λ_{4}(n) ≪ n2^{α(n)}.  (13)

For s > 4 they obtained strong bounds as well but they could not match completely the precision of (10) and (13). Their lower bound says that

λ_{2s}(n) ≫_{s} n2^{c_{s}α(n)^{s−1}+Q_{s}(n)},  (14)

where c_{s} = 1/(s − 1)! and Q_{s}(n) is a polynomial in α(n) of degree at most s − 2. As for the upper bound, they proved that

λ_{2s+1}(n) ≤ n2^{α(n)^{s−1} log(α(n))+C_{2s+1}(n)} and λ_{2s}(n) ≤ n2^{α(n)^{s−1}+C_{2s}(n)},  (15)

where C_{k}(n) equals 6 and 11 for k equal to 3 and 4, respectively, C_{2s+1}(n) = O(α(n)^{s−1}), and C_{2s}(n) = O(α(n)^{s−2} log(α(n))). We remark that in these bounds (and the whole [4]) log n denotes the binary logarithm with base 2, whereas in Example 2 and (5) we have the natural logarithm.

Let us summarize the current best bounds on λ_{s}(n). Cases s ≤ 1 are trivial. The formula λ_{2}(n) = 2n − 1 was proved by Davenport and Schinzel in [14], see Example 2. The functions λ_{3}(n) and λ_{4}(n) grow, up to multiplicative constants, as nα(n) and n2^{α(n)}, respectively, as proved by Hart and Sharir [21] and Agarwal, Sharir and Shor [4]. The bounds (14) and (15) of [4] estimate λ_{s}(n) for s > 4.

Problem 4. What are the exact speeds of growth of λ_{5}(n) and λ_{6}(n)? And of the other λ_{s}(n) for s > 4? □

By (14) and (15),

n2^{α(n)} ≪ λ_{5}(n) ≪ nα(n)^{(1+o(1))α(n)}

and

n2^{(1+o(1))α(n)^{2}/2} ≪ λ_{6}(n) ≪ n2^{(1+o(1))α(n)^{2}}.

Bounds on λ_{s}(n) found many applications in problems and algorithms of computational geometry. We suggest to the interested reader works [3] and [52] of Agarwal and Sharir for detailed information and many references. We remark that the “Web of Science” [65] listed in the middle of the year 2002 more than 110 citations of [21], which documents the big impact of this work.

4. A Generalization of λ_{s}(n) to Any Forbidden Subsequence

A containment of sequences. The extremal function λ_{s}(n) corresponds to the (forbidden) alternating sequence ababa … 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 ⊃ N and a, b, c, d, … lie in A. Recall that two sequences u = a_{1}a_{2} … a_{l} and v = b_{1}b_{2} … b_{l} of the same length are isomorphic, if for some injection f : A → A we have a_{i} = f(b_{i}), i = 1, 2, …, 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, … and to sequences over A by the letters u, v, w, . . ..

Let u and v be two sequences. We say that u contains v and write u ⊃ v, if u has a subsequence isomorphic to v. For example, u = a_{1}a_{2} … a_{l} contains abccba if and only if there are six indices 1 ≤ i_{1} < ⋯ < i_{6} ≤ 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}}, …, 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-free.

The extremal function Ex(v, n). A sequence u = a_{1}a_{2} … a_{l} is called k-sparse if a_{i} = a_{j}, i > j, implies i − j ≥ 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 ∈ N. We associate with v the extremal function

Ex(v, n) = max{|u| : u ⊅ v & u is ∥v∥-sparse & ∥u∥ ≤ n}.  (16)

It extends λ_{s}(n): if al_{s} denotes the alternating sequence abab … of length s, then λ_{s}(n) = Ex(al_{s+2}, n). The condition that u is ∥v∥-sparse is necessary to ensure that Ex(v, n) < ∞; note that 12 … k12 … k12 … is an infinite sequence that is k-sparse and contains no u with ∥u∥ ≥ k + 1.

Ex(v, n) was introduced, albeit in a different notation, in 1992 by Adamec, Klazar and Valtr [1]. Ex(v, n) is always well defined because a modification of the argument proving (2) gives

Ex(v, n) < ∥v∥ · (\binom{n}{∥v∥}(|v| − 1) + 1) ≪_{v} n^{∥v∥}.  (17)

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.

Example 5 ([26]). We determine Ex(abba, n) exactly and then prove a linear upper bound on Ex(a_{1}a_{2} … a_{k}a_{1}a_{2} … a_{k}, n).

We prove that, for all n ∈ 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 … (n − 2) (n − 1) (n − 2) (n − 1) n (n − 1) n

show that Ex(abba, n) ≥ 3n − 2. We prove the opposite inequality. For n = 1 it is true. For n > 1 we use induction on n. Let u = a_{1}a_{2} … a_{l} be 2-sparse, abba-free, and ∥u∥ ≤ n. Suppose first that some symbol a ∈ S(u) appears in u at least four times. We select four indices 1 ≤ i_{1} < ⋯ < i_{4} ≤ l such that a_{i_{1}} = a_{i_{2}} = a_{i_{3}} = a_{i_{4}} = a and a_{j} ≠ a for j ∈ [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| ≤ 3(n − 1) − 2 + 2 = 3n − 3. Thus we may assume that every symbol appears in u at most three times, which gives |u| ≤ 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| ≤ 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| ≤ 2n − 1. Thus we may assume in addition that a_{1} ≠ a_{l} and both symbols a_{1} and a_{l} appear in u at most twice. We conclude that |u| ≤ 3n − 2.

Let v_{k} = a_{1}a_{2} … a_{k}a_{1}a_{2} … a_{k} where a_{1}, …, a_{k} are k distinct symbols from A. We prove that

Ex(v_{k}, n) ≪_{k} n.

Notice that Ex(v_{1}, n) = n and Ex(v_{2}, n) = λ_{2}(n) = 2n − 1. Let k, n ∈ 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 (17). Let u be a k-sparse sequence (∥v_{k}∥ = k) with ∥u∥ ≤ n. We assume that |u| ≥ (2n + 1)L and show that it implies u ⊃ 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 ∈ S(u) because these are only at most 2n in number. If ∥I∥ < K, the definitions of L and |I| imply I ⊃ v_{k} and we are done. So ∥I∥ = |S(I)| ≥ K. By the property of I, every a ∈ S(I) appears before I, in I, and after I. Applying twice the classical Erdős–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 ⊂ S(I) of k elements, Y = {y_{1}, y_{2}, …, y_{k}}, such that y_{1}, y_{2}, …, 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 ⊃ v_{k}. Thus |u| ≥ (2n + 1)L always forces the containment u ⊃ v_{k}. We conclude that Ex(v_{k}, n) < (2n + 1)L. □

A historical remark. The author of this survey wondered from time to time why for so long (until the apperance of [1]^{2}) nobody tried to generalize λ_{s}(n) and everybody followed so faithfully the original formulation of the problem that forbids only alternating subsequences. The extension (16) of (1) 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 (6) or (10), 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 [14], published also [15] hinting on a generalization of λ_{s}(n). The latter forgotten note is missing in all bibliographies of DS sequences we know of ([3], [20, problem E20], [26], [52], [55], …) and probably is not refered to anywhere. It is accesible in Davenport [9] where we found it. Davenport and Schinzel derive in [15] an inequality on lentghs of subsequences of a 2-sparse sequence. In the last paragraph they say:

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

…, a, …, b, …, b, …, a, … (b ≠ 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 ≤ 4. (Actually in this particular case the maximum length is 3n − 2.)

Nobody followed the hint then.

An almost linear bound on Ex(v, n). As for strengthening of (17), Klazar [23] showed by a simple combinatorial argument that Ex(v, n) ≪_{v} n^{2}. The main result of [23] says that if v is a sequence with ∥v∥ = k ≥ 2 and |v| = l ≥ 5, then for every n ∈ N

Ex(v, n) ≤ n · k2^{l−3} · (10k)^{2α(n)^{l−4}+8α(n)^{l−5}}.  (18)

2I learned about DS sequences in the fall of 1988 in the Prague combinatorial seminar that was then led by J. Nešetřil and J. Matoušek. They suggested to us, a group of undergraduate students of Charles University, to investigate generalizations of λ_{s}(n). This eventually resulted in [1] and some other works.

If k = 1 or l ≤ 4, it is easy to show that Ex(v, n) ≪_{v} n. This general bound was derived by adapting the techniques from Sharir [50].

A slight generalization: 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∥ ≤ n. It is clear that Ex(v, ∥v∥, n) = Ex(v, n) and Ex(v, k, n) = ∞ whenever k < ∥v∥ and n ≥ k — the infinite sequence 12 … k12 … k12 … is k-sparse and does not contain v. Thus one has to have k ≥ ∥v∥. For the asymptotics it brings nothing new because, as proved in [1],

Ex(v, n) ≪_{v,k} Ex(v, k, n) ≤ Ex(v, n)  (19)

for every sequence v and every k ≥ ∥v∥; the latter inequality is trivial. As for the precise values, in Klazar [28] it was proved that for n ≥ k ≥ 2,

Ex(abab, k, n) = 2n − k + 1 and Ex(abba, k, n) = 2n + ⌊\frac{n − 1}{k − 1}⌋ − 1.

For n ≤ k − 1 both functions equal to n.

As one expects, the asymptotic order of Ex(v, n) respects the containment order of sequences:

u ⊂ v ⇒ Ex(u, n) ≪_{u,v} Ex(v, n).  (20)

For ∥u∥ = ∥v∥ this is triviality, since then even Ex(u, n) ≤ Ex(v, n). For ∥u∥ < ∥v∥ this follows immediately from the first bound in (19), and ≪ cannot in general be replaced with ≤.

Blow-ups. If a ∈ A and i ∈ N, we write a^{i} for the sequence aa … a of i a’s. We call u a chain if ∥u∥ = |u|, that is, u has no repetition. Obviously, Ex(a^{i}, n) = (i − 1)n for any i ∈ 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}, …, 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) ≪ n for all i = 1, …, r then Ex(w, n) ≪ 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}} … a_{r}^{i_{r}}, where a_{j} ∈ A, a_{j} ≠ a_{j+1}, and i_{j} ∈ N. The blow-up of u is any sequence isomorphic to a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{r}^{k_{r}}, where k_{1} ≥ i_{1}, k_{2} ≥ i_{2}, …, k_{r} ≥ i_{r}. For example, 1221111 and a^{3}b^{3}a = aaabbba are blow-ups of al_{3} = aba.

If v is not a chain, then Ex(v, n) ≥ |1 2 … 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:

Problem 5. Prove (or disprove) that if u is not a chain and v is a blow-up of u, then

Ex(v, n) ≪_{u,v} Ex(u, n). □

The lower bound Ex(v, n) ≥ Ex(u, n) is trivial.

Adamec, Klazar and Valtr [1] proved that the bound in Problem 5 often holds. Namely, if a is a symbol and u, v sequences, then

Ex(a^{2}u, n) − Ex(au, n) ≪_{au} n and Ex(ua^{3}v, n) ≪_{ua^{2}v} Ex(ua^{2}v, n).  (21)

By symmetry, also Ex(ua^{2}, n) − Ex(ua, n) ≪_{ua} n. Let v = a_{1}^{k_{1}}a_{2}^{k_{2}} … a_{r}^{k_{r}} be any blow-up of u = a_{1}^{i_{1}}a_{2}^{i_{2}} … a_{r}^{i_{r}} such that k_{j} > i_{j} implies i_{j} ≥ 2 or j = 1 or j = r. Applying the bounds (21), it is easy to see that then Ex(v, n) ≪ Ex(u, n). Both extremal functions are then of the same asymptotic order. For example, a^{4}bc^{5}ab^{2} and abc^{2}ab 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^{2}v (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 (21) and whether it changes asymptotics is unknown. Surprisingly, this does happen for certain tree generalizations of Ex(v, n), as shown by Valtr in [61]. This is a contrary evidence showing that perhaps blow-ups may change asymptotics.

Example 6 ([1]). We prove the first bounds of (19) and (21). We begin with (19). Let v be a fixed sequence, k ≥ ∥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| ≫_{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∥ ≥ 2k − 1. Then there must be an a ∈ 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∥ ≤ 2k − 2 for every I. Thus |I| ≤ Ex(v, 2k − 2) for every I and |w| ≥ 1 + |u|/(1 + Ex(v, 2k − 2)). This finishes the proof of the first bound in (19).

Now we prove that Ex(a^{2}u, n) = Ex(au, n) + O(n), where the constant in O depends on the sequence au. Let k = ∥a^{2}u∥ and v be a k-sparse and a^{2}u-free sequence with ∥v∥ ≤ n. First, we show that there is a constant c > 0 depending only on a^{2}u 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| ≥ |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^{2}u, 3k − 3) + 1. So ∥I∥ ≥ 3k − 2 and there must be a subset Y ⊂ S(I), |Y | = k − 1, such that every y ∈ 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 ∈ Y and we delete from v the rest of I. The resulting sequence w is clearly k-sparse, x was deleted, and |w| ≥ |v| − (Ex(a^{2}u, 3k − 3) + 2 − k). We can set c = Ex(a^{2}u, 3k − 3) + 2 − k.

In this way we delete from v, one by one, the first appearances of all x ∈ S(v). At most cn elements are deleted and the resulting subsequence w is k-sparse. Clearly, w ⊅ au because otherwise v ⊃ a^{2}u would be forced. Thus |v| ≤ |w|+cn ≤ Ex(au, n)+cn and Ex(a^{2}u, n) ≤ Ex(au, n) + O(n). Trivially, Ex(a^{2}u, n) ≥ Ex(au, n). □

The two-letter theorem. If u has at most two symbols, then either u ⊃ ababa and Ex(u, n) ≥ λ_{3}(n) ≫ nα(n), or u is contained in a blow-up of abab. The main result of [1] says that for the latter u’s we have Ex(u, n) ≪_{u} n. We obtain the characterization ([1, Theorem 5]) that is in [61] called the two-letter theorem: If ∥u∥ ≤ 2 then

Ex(u, n) ≪_{u} n ⟺ u ⊅ ababa.  (22)

It follows from (20) and from the discussion after Problem 5 that the proof of (22) (given λ_{3}(n) ≫ nα(n)) reduces to proving that Ex(ab^{2}a^{2}b, n) ≪ n. By (21), this implies Ex(a^{i}b^{j}a^{k}b^{l}, n) ≪_{m} n, where m = max(i, j, k, l), for every choice of the exponents i, j, k, l ∈ N_{0}.

More results and errors on blow-ups. In [36, p. 467] the first author wrote: “However, it may be checked that the method [of Hart and Sharir] (…) works for a^{i}b^{i}a^{i}b^{i}a^{i} as well and so Ex(a^{i}b^{i}a^{i}b^{i}a^{i}, n) = Θ(nα(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.

Problem 6. Prove (or disprove) that Ex(v, n) ≪_{v} nα(n) for every blow-up v of ababa. That is, prove (or disprove) that

Ex(ab^{2}a^{2}b^{2}a, n) ≪ nα(n). □

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^{i}b^{i}a^{i}b^{i}a^{i}, n) ≪_{i} nα(n) in [36, 3.2] must be considered as unproved.

A simpler proof of the two-letter theorem was given in Klazar [27]. In particular, he proved that

7n − 9 ≤ Ex(ab^{2}a^{2}b, n) ≤ 8n − 7

and Ex(a^{i}b^{i}a^{i}b^{i}, n) < (1 + o(1))32i^{2} · n. The method of [27] was extended in Klazar [25] to the blow-ups of the sequences v_{k} of Example 5. In [25] he proved that, for i ∈ N and k distinct symbols a_{1}, a_{2}, …, a_{k},

Ex(a_{1}^{i}a_{2}^{i} … a_{k}^{i}a_{1}^{i}a_{2}^{i} … a_{k}^{i}, n) ≪_{i,k} n.  (23)

Two general questions on the growth of Ex(v, n). Is the equivalence (22) valid for sequences using more than two symbols? Klazar and Valtr realized that the answer was “no”. A specific example is given in Klazar [24]: u_{1} = abcbadadbcd ⊅ ababa but Ex(u_{1}, n) ≫ nα(n). A more extremal example in this direction is given in [31]:

u_{2} = abcbadadbecfcfedef ⊅ ababa but Ex(u_{2}, n) ≫ n2^{α(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 [64] and [4] 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.

Problem 7. We conjecture that for every constant c > 0 there exists a sequence u such that

u ⊅ ababa but Ex(u, n) ≫ n2^{α(n)^{c}}. □

In other words, in view of (18), we conjecture that every extremal function Ex(v, n) is majorized (for n > n_{0}) by some Ex(u, n), u ⊅ ababa. Below we will see that u ⊅ abab implies Ex(u, n) ≪_{u} n.

Another attractive but at present hopeless question is whether nα(n) is the smallest superlinear growth of extremal functions.

Problem 8. Is it true that for every sequence u either Ex(u, n) ≪ n or Ex(u, n) ≫ nα(n)? □

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 ≤ n_{1} < n_{2} < … and 1 ≤ m_{1} < m_{2} < … of N, and two increasing functions f, g : N → R^{+} with f(n)/g(n) → ∞, such that f(n_{i}) ≪ Ex(u, n_{i}) ≪ f(n_{i}) and g(m_{i}) ≪ Ex(u, m_{i}) ≪ g(m_{i}) as i → ∞. Valtr [61, Proposition 3] shows that for every sequence u,

lim sup_{n→∞} \frac{Ex(u, n)}{n} = ∞ ⟹ lim inf_{n→∞} \frac{Ex(u, n)}{n} = ∞.

So in any case one cannot select g(n) = n. If u is irreducible, which means that there is no nontrivial decomposition u = u_{1}u_{2} with S(u_{1}) ∩ S(u_{2}) = ∅, then it is easy to prove the stronger result that lim_{n→∞} Ex(u, n)/n exists (it may equal ∞).

Insertions and intertwinings. We proceed to the remaining two operations which compose w from v_{1}, …, v_{r} so that Ex(w, n) can be bounded in terms of Ex(v_{1}, n), …, Ex(v_{r}, n). They constitute the main result of Klazar and Valtr [36].

Let a and b be two distinct symbols and u_{1}, u_{2}, and v be three sequences. The insertion of v in u = u_{1}a^{2}u_{2} gives the sequence w = u(v) = u_{1}avau_{2}. The intertwining of u = u_{1}a^{2}u_{2}a and b gives the sequence w = u[b] = u_{1}ab^{2}au_{2}ab. We can bound Ex(u(v), n) only under the assumption that S(u_{1}a^{2}u_{2})∩S(v) = ∅. Similarly, we can bound Ex(u[b], n) only under the assumption that b ∉ S(u_{1}a^{2}u_{2}a). The insertion is a binary operation in the sense that it is determined completely by two sequences u, v and an immediate repetition … aa … in u. In the similar sense the intertwining is an unary operation.

Let u = u_{1}a^{2}u_{2} and v be two sequences with S(u) ∩ S(v) = ∅, and u(v) arise by inserting v in u. If v is a chain, it is easy to see that Ex(u(v), n) ≤ Ex(u, n). If v is not a chain then, as proved in [36],

Ex(u(v), n) = Ex(u_{1}avau_{2}, n) ≪_{u,v} Ex(v, Ex(u, n)).  (24)

Let u = u_{1}a^{2}u_{2}a be a sequence, b be a symbol such that b ∉ S(u), and u[b] arise by intertwining u with b. Then, as proved in [36],

Ex(u[b], n) = Ex(u_{1}ab^{2}au_{2}ab, n) ≪_{u} Ex(u, n).  (25)

By symmetry, we have the analogous statement for bau_{1}ab^{2}au_{2}. The lower bounds

Ex(u(v), n) ≫_{u,v} max(Ex(u, n), Ex(v, n)) and Ex(u[b], n) ≫_{u} Ex(u, n)

are immediate from (20). Simpler proofs of (24) and (25) were given in Valtr [61]. Blowing-up u[b], we obtain from (25) for i, j ∈ N the bounds

Ex(u_{1}ab^{i}au_{2}ab^{j}, n) ≪_{u,i,j} Ex(u, n)

(remember the condition b ∉ S(u)).

Linear sequences. It is natural (but difficult) to investigate the class of the linear sequences

Lin = {v : Ex(v, n) ≪ 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 ∉ Lin by (10).

Problem 9. What are the elements of Lin? □

The bounds (21), (24), and (25) 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 ∈ N, a^{i} ∈ L; (ii) if au ∈ L then a^{i}u ∈ L for every i ∈ N, and if ua ∈ L then ua^{i} ∈ L for every i ∈ N; (iii) if ua^{2}v ∈ L then ua^{i}v ∈ L for every i ∈ N; (iv) if u = u_{1}a^{2}u_{2}, v ∈ L and S(u) ∩ S(v) = ∅ then u_{1}avau_{2} ∈ L; and (v) if u = u_{1}a^{2}u_{2}a ∈ L and b ∉ S(u) then u_{1}ab^{2}au_{2}ab ∈ L, and if u = au_{1}a^{2}u_{2} ∈ L and b ∉ S(u) then bau_{1}ab^{2}au_{2} ∈ L. Then ([36]),

L ⊂ Lin.

Observe that, by the way of definition, L is closed to the containment and to all blow-ups.

Problem 10. Decide if there is a sequence u ∈ Lin\L. □

By (20), u ⊂ v ∈ Lin implies that u ∈ Lin. Hence we can characterize Lin by means of the class of minimal nonlinear sequences

B = {u : u ∉ Lin but v ∈ Lin whenever v ⊂ u & |v| < |u|}.

Namely, we have the equivalence u ∈ Lin ⟺ ∀v ∈ B [v ⊄ 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 ∈ B and (ii) B has at least two elements. The first property follows from the facts that λ_{3}(n) ≫ nα(n) (by (10)), abab ∈ Lin (Example 2), ab^{2}a ∈ Lin (Example 5), and aba^{2} ∈ Lin (trivial). As for (ii), it follows from the examples given after the bound (23). Might B be infinite?

Problem 11. Is the set B of minimal nonlinear sequences finite or infinite? □

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

Interesting sequences in the class 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_{1}au_{2}a … au_{k}, where u_{1}, …, u_{k} are possibly empty sequences, the sets S(u_{i}) are mutually disjoint, and a ∉ S(u_{i}) for every i = 1, …, k. By induction, u_{i} ∈ L for every i = 1, …, k. Inserting in a^{k+1} the sequences u_{1}, …, u_{k}, we conclude (applying k times the closure property (iv)) that u ∈ L. Thus Ex(u, n) ≪_{u} n for every abab-free sequence u. In particular,

DS_{4} ⊂ Lin.

Recall that u_{1} = abcbadadbcd ∉ Lin and u_{1} ⊅ ababa. Thus DS_{5} ⊄ Lin.

Intertwinings and blow-ups yield an immediate proof of the two-letter theorem: a^{3} ∈ L by (i), ab^{2}a^{2}b ∈ L by (v), and a^{i}b^{i}a^{i}b^{i} ∈ L (i ≥ 2) by (ii) and (iii). Hence every a^{i_{1}}b^{i_{2}}a^{i_{3}}b^{i_{4}} (i_{j} ≥ 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 … (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 ⊅ abba but abcadbcd ∉ 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^{i}2^{i} … (k − 1)^{i}k^{i}(k − 1)^{i} … 2^{i}1^{i}2^{i} … (k − 1)^{i}k^{i}

belongs to L and thus is linear. The bound

Ex(u_{N}(k, i), n) ≪_{i,k} n  (26)

is an important result of [36] and a considerable strengthening of (23).

It follows by a case analysis that every ababa-free sequence u with ∥u∥ ≤ 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 ∉ L.

Problem 12. Is it true that Ex(abacacbc, n) ≪ n? And what about the blow-ups of abacacbc? □

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∥ ≤ 3,

u and \overline{u} contain none of \{ababa, abacabc, abacacb\} ⇒ Ex(u, n) ≪_{u} n.

In the opposite direction we know only that ababa ⊂ u implies the nonlinearity of u.

5. Geometric Graphs, Colored Trees, 0-1 Matrices, Ordered Bipartite Graphs, Permutations, and Set Partitions

Geometric graphs. Generalized DS sequences found interesting applications in the combinatorics of 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 cross if their relative interiors intersect, and they are parallel if they form two opposite sides of a convex quadrilateral.

Katchalski and Last [22] proved, using the bound (4), that any geometric graph with n vertices and no two parallel edges has at most 2n − 1 edges. Valtr [60] 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. (Another nice application of (4) in combinatorial geometry was given by Edelsbrunner and Sharir in the article [17] with a self-explaining title.) Applying the N-sequence bound (26), Valtr proved in [60] more

[figure]

Figure 2: Geometric graphs with n vertices and 2n − 2 edges, no two of them “parallel”.

generally that every geometric graph with n vertices and no k pairwise parallel edges has ≪_{k} n edges. From this he derived that if k pairwise crossing edges are forbidden, then the number of edges is ≪_{k} n log n. (For these results see also [61].) This improves the previous bound ≪_{k} n log^{2k−6} n (for k > 2) of Agarwal et al. [2] (based on the bound ≪_{k} n log^{2k−4} n of Pach, Shahrokhi and Szegedy [43]). Whether the bound ≪_{k} n holds is open. It is known to hold only for k = 2 (the classical case of planar graphs) and k = 3 ([2]).

Precisely speaking, the bounds ≪_{k} n log^{2k−6} n of [2] and ≪_{k} n log n of [60] are in a sense incomparable. The former bound holds, as stated in [2], for the more general representation of edges by curves (details are in [2] given only for the case of segments). The latter stronger bound applies on the more special representation by segments. In [59] 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 [3] and [52].

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_{1}v_{2} … 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 (16) to colored trees? Can one prove for colored trees an analogue of, say, λ_{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:

1. The coloring is proper, which means that no edge is monochromatic.

2. No subgraph of the colored tree T is a subdivision of the properly 2-colored 4-vertex

path •−∘−•−∘.

3. No subgraph of the colored tree T is a subdivision of the properly 2-colored 4-vertex

star {•−∘−• \atop •} .

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 → N, that there are no four distinct vertices v_{1}, …, v_{4} ∈ V such that f(v_{1}) = f(v_{3}) ≠ 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}, …, v_{3} ∈ V such that f(v_{1}) = f(v_{2}) = f(v_{3}) ≠ 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.

Example 7 ([29]). We prove that for every n ∈ N,

T (abab, n) = 2n − 1.  (27)

So if T ranges over the larger set of all trees, T (abab, n) still equals Ex(abab, n) = λ_{2}(n) = 2n − 1.

The lower bound T (abab, n) ≥ 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) ≤ 2n − 1. Let T = (V, E) be a tree and f : V → {1, 2, …, n} be a coloring satisfying the conditions 1, 2, and 3. We show that |V | ≤ 2n − 1. We may assume that n > 1 and that b(T) = #{v ∈ V : deg_{T} (v) ≥ 3} > 0; else T is a path and |V | ≤ Ex(abab, n) = 2n − 1. Formally, we proceed by induction on the sum n + b(T). We use the operation of 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} ∪ P_{2} ∪ … ∪ P_{l} ∪ C where l ≥ 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)\V (C) = {v} ∪ V (P_{1}) ∪ … ∪ V (P_{l}). If this is not the case, then f(u_{1}) = f(u_{2}) for two distinct u_{1}, u_{2} ∈ V (T)\V (C), and either (i) {u_{1}, u_{2}} ⊂ {v} ∪ V (P_{i}) for some i or (ii) u_{1} ∈ V (P_{i}) and u_{2} ∈ V (P_{j}) for some i ≠ 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 | ≤ 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 | ≤ 2(n − 1) − 1 + 2 = 2n − 1.

Thus we may assume that on the vertices in V (T)\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}, …, 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^{∗})| ≤ 2n − 1.

To this end we define a binary relation R on the set of colors appearing in V (P_{1}) ∪ … ∪ V (P_{l}). We set aRb iff a ≠ b and there is a path Q = (v_{0}, …, v_{k}) in C ∪ {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 ∪ {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. □

For a general sequence u ∈ 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:

1. Two distinct vertices with the same color have distance at least ∥u∥ edges.

2. No subgraph of the colored tree T is a subdivision of the path of |u| vertices that is colored according to u.

[figure: 1; 3; 4; 5; 6; 2; 1; 6; 3; 1; 2; 6; 3; 2; 4; 1; 5; 1; 4; 2; 5; 2]
Figure 3: The bound T (abba, n) ≥ 5n − 8 for n = 6.

3. No subgraph of the colored tree T is a subdivision of the properly 2-colored 4-vertex

star {•−∘−• \atop •} .

We keep the condition 3 and modify the first two conditions in the obvious way. For ∥u∥ > 1 this works fine, T (u, n) < ∞. For u = a^{i} the first condition is void and for i ≥ 4 we would still have T (a^{i}, n) = ∞ (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) extends Ex(u, n).

This generalization of Ex(u, n) to colored trees, T (u, n), was considered first in [26]. From the results on T (u, n) proved in Klazar [30] we mention the extension of (18) to colored trees and the exact values (n > 1)

T (a^{i}, n) = \{ \begin{matrix}(2i − 3)n − 2i + 4 & … & i ≥ 2 is even \\ (2i − 4)n − 2i + 6 & … & i ≥ 3 is odd \end{matrix}

(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) ≠ Ex(abba, n).

Example 8 ([62]). We show that T (abba, n) ≥ 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.

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 [62] a more general example is given showing that

T (a^{i}b^{i}a^{i}, n) ≥ 9in − O(i + n). □

In [26] and [29] we posed as a problem to show that T (abba, n) ≪ n. This was accomplished in [62] by Valtr who proved more generally that

T (a^{i}b^{i}a^{i}, n) ≤ 24in.

Thus 5n − 8 ≤ T (abba, n) ≤ 48n.

Problem 13. Improve these bounds. Or, better, determine the function T (abba, n) exactly. □

The theory of tree extremal functions was much advanced by Valtr in [61] and [63]. 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 [61] and [63]. 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 ([61], [63]) says: for ∥u∥ ≤ 2,

T (u, n) ≪_{u} n ⟺ u ⊅ ababa & u ⊅ ab^{2}a^{2}b.

In fact ([61], [63]), T (ab^{2}a^{2}b, n) ≫ nα(n). Comparing this with (27), we see that for colored trees blow-ups change asymptotics.

0-1 matrices and ordered bipartite graphs. Recall the notation [n] = {1, 2, …, n} and [a, b] = {a, a + 1, …, b}. Füredi and Hajnal [18] investigated the following class of extremal problems for 0-1 matrices. Let N : [k] × [l] → {0, 1} and M : [m] × [n] → {0, 1} be two 0-1 matrices of types k × l and m × n, respectively. We say that M contains N if there are increasing injections f : [k] → [m] and g : [l] → [n] such that, for all i ∈ [k] and j ∈ [l], M(f(i), g(j)) = 1 whenever N(i, j) = 1. In other words, M has a (not necessarily contiguous) k × 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 × 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) ≪ 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üredi and Hajnal investigated f(n; N) for each of these N. One of their results related to DS sequences says that

nα(n) ≪ f(n; ( \begin{matrix}1 & & 1 \\ & 1 & & 1 \end{matrix} )) ≪ nα(n);

the upper bound is obtained from (10) 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 = ( \begin{matrix}1 \\ & & 1 \\ & 1 & & 1 \end{matrix} )

and the upper bound f(n; N) ≪ nα(n) for

N = ( \begin{matrix}& 1 \\ & & & 1 \\ 1 & & 1 \end{matrix} ) and N = ( \begin{matrix}& 1 \\ & & & 1 \\ 1 \\ & & 1 \end{matrix} ) .

In the end of [18] the authors pose a question whether f(n; P) ≪_{P} n holds for all permutation matrices P. In [34] 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 G = ([n], [n + 1, n + m], H) where, for all i ∈ [m] and j ∈ [n + 1, n + m], {i, j} ∈ 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; H) is defined as the maximum number |H| of the edges of a bipartite graph G = ([n], [n + 1, 2n], H) such that G does not contain H. For a permutation p = a_{1}a_{2} … a_{k} of [k], the permutation bipartite graph G_{p} is defined as

G_{p} = ([k], [k + 1, 2k], {{i, k + a_{i}} : i = 1, 2, …, k}).

The question of Füredi and Hajnal asks if, for any fixed permutation p, every G = ([n], [n + 1, 2n], H) not containing G_{p} as an ordered subgraph must have ≪ n edges.

Permutations. Alon and Friedgut [5] applied generalized DS sequences to a problem in enumerative combinatorics. Let p = a_{1}a_{2} … a_{m} and q = b_{1}b_{2} … 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}} … b_{i_{m}}, 1 ≤ i_{1} < i_{2} < … < i_{m} ≤ n, such that b_{i_{r}} < b_{i_{s}} ⟺ a_{r} < a_{s} for every r and s. Else we say that q avoids p. Let S_{n}(p) be the number of permutations of [n] avoiding p. The Stanley–Wilf conjecture (stated, for example, in Bóna [10]) asserts that for any given permutation p,

S_{n}(p) < c^{n}  (28)

holds for every n ∈ N and a constant c > 1 depending only on p. Using the general bound (18), Alon and Friedgut proved for every p the upper bound

S_{n}(p) < β_{p}(n)^{n},  (29)

where β_{p}(n) is an extremely slowly growing function defined in terms of α(n). Using the N-sequence bound (26), they proved also that (28) holds for all unimodal p. (Recall that p = a_{1}a_{2} … a_{m} is unimodal if it first decreases and then increases or vice versa.) Bóna [11] proved that (28) holds for all permutations p of the form p = a_{1}a_{2} … a_{m} = s_{1}s_{2} … 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}.

Example 9 ([34]). We give a simpler proof of the bound (29). We translate the problem from permutations to ordered bipartite graphs G and work with the above described extremal function f(n; G) and the permutation graphs G_{p}. Let, for a permutation p, G_{n}(p) be the number of all ordered bipartite graphs G = ([n], [n + 1, 2n], H) such that G ⊅ G_{p}. Clearly,

S_{n}(p) ≤ G_{n}(p)

because now we count many more p-free objects. Let us suppose that we have a bound f(n; G_{p}) < nγ(n), where γ(n) = γ_{p}(n) is a nondecreasing function. Let n ∈ N be fixed and m = ⌈n/2⌉. We claim that

G_{n}(p) < 15^{mγ(m)} · G_{m}(p).

To prove this inductive inequality, we transform every G = ([n], [n+1, 2n], H) counted by G_{n}(p) to a G′ = ([m], [m+1, 2m], H′) counted by G_{m}(p). For i ∈ [m] and j ∈ [m+1, 2m], we let {i, j} ∈ H′ iff in G the sets {2i − 1, 2i} and {2j − 1, 2j} are connected by at least one edge. In other words, to get G′, we identify in G the vertices in each of the pairs (1, 2), (3, 4), … and (n + 1, n + 2), (n + 3, n + 4), … and replace the arising multiple edges by simple edges. Every edge of G′ can be obtained in at most 2^{2·2} − 1 = 15 ways. Thus if G′ has e edges, there are at most 15^{e} graphs G that transform to G′. Also, G ⊅ G_{p} implies G′ ⊅ G_{p}, and therefore e ≤ f(m; G_{p}) < mγ(m). Hence we obtain the inductive inequality. Iterating it until m = 1 and denoting m_{0} = n, m_{i} = ⌈m_{i−1}/2⌉, we obtain the bound

S_{n}(p) ≤ G_{n}(p) < 2 · 15^{∑_{i≥1} m_{i}γ(m_{i})} < 2 · 15^{γ(n) ∑_{i≥1} m_{i}} < 15^{2nγ(n)} = (225^{γ(n)})^{n} .

We have obtained (29) with β_{p}(n) = 225^{γ_{p}(n)}. If γ_{p}(n) is almost constant, so is β_{p}(n). To find such a γ_{p}(n), we reduce bipartite graphs to sequences. We associate with every G = ([n], [n + 1, 2n], H) the sequence u = N_{1}N_{2} … N_{n} ∈ [n + 1, 2n]^{∗}, where N_{i} is the (arbitrarily ordered) list of the neighbours of i ∈ [n] in G. Let p be a fixed permutation of [k]. It follows that G ⊅ G_{p} implies u ⊅ w where w = a_{1}a_{2} … a_{k}a_{1}a_{2} … a_{k} … a_{1}a_{2} … a_{k} consists of 2k repetitions of the segment of k distinct symbols a_{1}, …, 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}, …, N_{n}, we obtain a subsequence v of u, |v| ≥ |u| − (k − 1)(n − 1), which is k-sparse. Invoking (18), we obtain the required bound:

|H| = |u| ≤ (k − 1)(n − 1) + |v| < kn + Ex(w, n)
< kn + n · k2^{l−3} · (10k)^{2α(n)^{l−4}+8α(n)^{l−5}} =: nγ_{p}(n),

where l = 2k^{2}. □

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_{1}a_{2} … 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 ∼, we can formulate the containment of sequences ⊂ in the following way. A partition u = ([k], ∼_{u}) is contained in another partition v = ([l], ∼_{v}), if there is an increasing injection f : [k] → [l] such that the equivalence x ∼_{u} y ⟺ f(x) ∼_{v} f(y) holds for every x, y ∈ [k].

An important and interesting class of partitions is the noncrossing partitions. A partition P of [l] is noncrossing, if there are no four numbers 1 ≤ x_{1} < x_{2} < x_{3} < x_{4} ≤ l and no two distinct blocks B_{1} and B_{2} of P such that x_{1}, x_{3} ∈ B_{1} and x_{2}, x_{4} ∈ 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 [53] wrote an interesting survey of results on noncrossing partitions and related topics. The seminal work introducing noncrossing partitions was that of Kreweras [38], followed shortly by Poupard [45]. In the same year 1972, Mullin and Stanton published independently their article [42] on enumeration of 4-DS sequences. Other enumerative works on 4-DS sequences are Roselle [47], Gardy and Gouyou-Beauchamps [19], and Klazar [28]. See also Klazar [32] for a more general approach to the enumeration of u-free set partitions.

Although one can read in the MR review of [31] (with the main result (12)) that “The author improves previous results to show that the number N_{5}(n) [λ_{3}(n)] of finite sequences …”, 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 [6] applied in an enumerative problem (of bounding the numbers of separable partitions of points on the moment curve) the extremal bounds (2) and (7).

Problem 14. Let r_{l} be the number of ababa-free partitions of [l]. In other words,

r_{l} = #{u : u ⊅ ababa & |u| = l & u is normal}.

What can be said about the numbers r_{l}? What is their asymptotics? □

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} ≥ ∑_{i≥0} \binom{l}{2i} · (2i − 1)!!

where (2i − 1)!! = 1 · 3 · 5 · . . . · (2i − 1) and (−1)!! = 1.

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

Problem 15. Let s_{l} be the number of abcabc-free partitions of [l]. In other words,

s_{l} = #{u : u ⊅ abcabc & |u| = l & u is normal}.

What can be said about the numbers s_{l}? What is their asymptotics? □

The hypergraph bound (31) (proved in [33]) 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} ≥ s_{k}s_{l} for every k, l ∈ N. Hence s_{l}^{1/l} tends to a finite limit.

6. Hypergraphs

A hypergraph containment. The containment of sequences discussed through this survey is a special case of the hypergraph containment introduced in Klazar [33]. In Section 6 we survey some of the results of [33] and [35].

A hypergraph H = (E_{i} : i ∈ I) is a finite list of finite nonempty subsets E_{i} of N = {1, 2, …}, which are called edges. The edges may be repeated (we allow E_{i} = E_{j} for i ≠ j). Simple hypergraphs have no repeated edges. The elements of ⋃ H = ⋃_{i∈I} E_{i} ⊂ N are called 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 ([33, 35]).

A hypergraph H′ = (E′_{i} : i ∈ I′) is contained in another hypergraph H = (E_{i} : i ∈ I), in symbols H′ ⊂ H, if there is an increasing injection F : ⋃ H′ → ⋃ H and an injection f : I′ → I such that the implication

x ∈ E′_{i} ⟹ F (x) ∈ E_{f(i)}

holds for every vertex x ∈ ⋃ H′ and every index i ∈ I′. If H′ ⊄ H, we say also that H is H′-free. If H′ and H 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 H_{1} = (E_{1}, E_{2}), E_{1} = E_{2} = {1}, be the hypergraph consisting of the singleton edge {1} repeated twice. Then H is H_{1}-free iff H is a partition. Let H_{2} = ({1, 3}, {2, 4}). Then H = (E_{i} : i ∈ I) ⊃ H_{2} iff there are four vertices x_{1}, …, x_{4} ∈ ⋃ H, x_{1} < x_{2} < x_{3} < x_{4}, and two (not necessarily distinct) edges E_{i}, E_{j} in H, i ≠ j, such that x_{1}, x_{3} ∈ E_{i} and x_{2}, x_{4} ∈ E_{j}. (H_{2}-free hypergraphs generalize noncrossing partitions.)

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

Exponential and almost exponential bounds. For a fixed hypergraph F and n ∈ N, we are interested in the number

a(F, n) = #{H : H is simple & ⋃ H = [n] & H ⊅ F}.

The simplicity of H is needed to make a(F, n) finite. The forbidden hypergraph F, however, may be arbitrary, not necessarily simple. (If F = H_{1} = ({1}, {1}) from the above example, a(F, n) counts the partitions of [n] and equals to the nth Bell number.) One of the basic problems here is to determine all hypergraphs F for which a(F, n) < c^{n} for a constant c > 1. The candidates for such F are the permutation hypergraphs H_{p} (with added singleton edges); these are slightly modified graphs G_{p}. For a permutation p = a_{1}a_{2} … a_{k} of [k] we define

H_{p} = ({i, k + a_{i}} : i = 1, …, k).

For example, H_{1,3,2} = ({1, 4}, {2, 6}, {3, 5}). If a hypergraph F 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 H_{p} is F-free. Thus for such an F we have

a(F, n) ≥ (⌊n/2⌋)! = exp((\frac{1}{2} + o(1))n log n)

and the numbers a(F, n) grow superexponentially. It is clear that F satisfies neither of (i)–(iii) if and only if it is a disjoint union of several singleton edges and a hypergraph isomorphic to some H_{p}. We say briefly that F is of the form H_{p}+singletons. For example, we may have

F = ({1}, {3}, {7}, {2, 9}, {4, 6, }, {5, 8}).

We conjecture that a(F, n) < c^{n} if and only if, for some permutation p, F = H_{p}+singletons. This strengthens the Stanley–Wilf conjecture.

To prove our conjecture, it is enough to prove a(H_{q}, n) < c^{n} for every permutation q; every H_{p}+singletons is contained in an appropriate H_{q}.

Problem 16. Prove (or disprove) that for any given permutation p,

a(H_{p}, n) < c^{n}

holds for every n ∈ N and a constant c > 1. □

In [33] we proved, using (18), a slightly weaker bound: for every permutation p there is an almost constant function β_{p}(n) defined in terms of the inverse Ackermann function α(n), such that

a(H_{p}, n) < β_{p}(n)^{n}.  (30)

Note that this strengthens (29) (and our strengthening of (29) in Example 9) because now we count many more p-free objects. In [33] we also proved, using the N-sequence bound (26), that the exponential bound in Problem 16 holds for certain permutations: if p = a_{1}a_{2} … a_{k} first dicreases and then increases, or if p^{−1} first increases and then dicreases, then

a(H_{p}, n) < c^{n}  (31)

for all n ∈ 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

a(F, n) \{ \begin{matrix}< β_{p}(n)^{n} & … & F ⊂ H_{p} for some p \\ > n^{(1/2+o(1))n} & … & F ⊄ H_{p} for every p, \end{matrix} \}  (32)

we conjecture that β_{p}(n) may be replaced with a constant, and can prove this for some particular permutations p.

Two hypergraph extremal functions. For a hypergraph H = (E_{i} : i ∈ I), we denote by v(H) = | ⋃ H| the number of vertices, by e(H) = |I| the number of edges, and by i(H) = ∑_{i∈I} |E_{i}| the number of vertex-edge incidences. For a fixed hypergraph F and n ∈ N, we define two extremal functions

H_{e}(F, n) = max{e(H) : H ⊅ F & H is simple & v(H) ≤ n}
H_{i}(F, n) = max{i(H) : H ⊅ F & H is simple & v(H) ≤ n}.

The simplicity of H is again needed that H_{e}(F, n) and H_{i}(F, n) be well defined. The forbidden F may be arbitrary. Obviously, H_{e}(F, n) ≤ H_{i}(F, n) for every F and n. In most cases we have, up to a constant factor, also the opposite inequality:

Example 10 ([35]). Suppose that no two edges E_{1} and E_{2} of F satisfy E_{1} < E_{2}. Let p = v(F) and q = e(F) > 1 (the case q = 1 is trivial). Then for every n ∈ N,

H_{i}(F, n) ≤ (2p − 1)(q − 1) · H_{e}(F, n).  (33)

For the proof suppose that H is a simple and F-free hypergraph with v(H) ≤ n. We transform H in a new hypergraph H′. If E = {v_{1}, v_{2}, …, v_{s}} is an edge of H, v_{1} < v_{2} < ⋯ < v_{s}, we keep it if s < p. If s ≥ p, we replace E with t = ⌊|E|/p⌋ new edges {v_{1}, …, v_{p}}, {v_{p+1}, …, v_{2p}}, …, {v_{(t−1)p+1}, …, v_{tp}}. The new edges have each p elements and are mutually separated in the way that is excluded in F. The new hypergraph H′ may not be simple. Therefore we define a simple hypergraph H′′ by keeping from every family of repeated edges of H′ only one edge. We observe two things: (i) no edge of H′ is repeated more than q − 1 times and (ii) H′′ is F-free. If (i) were false, there would be q distinct edges E_{1}, …, E_{q} in H such that | ⋂_{i=1}^{q} E_{i}| ≥ p. But this implies the contradiction F ⊂ H. As for (ii), since the new p-element edges born from an edge E of H are separated, every copy of F in H′′ may use for every E only at most one of them. But then it would be a copy of F in H as well, which is again impossible. Both observations and the definitions of H′ and H′′ imply

i(H) ≤ \frac{(2p − 1) · i(H′)}{p} ≤ \frac{(2p − 1)(q − 1) · i(H′′)}{p}
≤ (2p − 1)(q − 1) · e(H′′)
≤ (2p − 1)(q − 1) · H_{e}(F, n). □

The inequality (33) holds, for example, for all permutation hypergraphs F = H_{p}. On the other hand, there exists a class of somewhat singular hypergraphs F for which H_{i}(F, n) ≪̸ H_{e}(F, n). For F = ({1}, {2}) one can quickly show that H_{e}(F, n) = 1 but H_{i}(F, n) = n. More generally, in [35] we have shown that if F = ({1}, {2}, …, {k}) then H_{e}(F, n) = 2^{k−1} − 1 (n ≥ k − 1) and H_{i}(F, n) = (k − 1)n − (k − 2) (n is large enough).

Problem 17. Is it true that for every F ≠ ({1}, {2}, …, {k}) one has the estimate H_{i}(F, n) ≪_{F} H_{e}(F, n)? □

Linear and almost linear bounds on H_{i}(F, n). In [33] we proved, by means of (18), an extremal analogue of (30): for every permutation p,

H_{i}(H_{p}, n) < n · γ_{p}(n)  (34)

where γ_{p}(n) is defined in terms of α(n) and thus grows to infinity extremely slowly. (This proof now may be simplified by means of the inequality (33).) Similarly, in [33] we proved, by means of (26), that if p = a_{1}a_{2} … a_{k} is a permutation that first dicreases and then increases, or if p^{−1} first increases and then dicreases, then

H_{i}(H_{p}, n) ≪_{p} n.  (35)

Problem 18. Prove (or disprove) that for every permutation p we have H_{i}(H_{p}, n) ≪_{p} n. □

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 [33] we prove first the bounds (34) and (35) and from them we derive, respectively, the bound (30) and (31) 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 (32)?

Problem 19. Identify the class of hypergraphs Ψ such that

H_{e}(F, n), H_{i}(F, n) \{ \begin{matrix}< n · γ_{F}(n) & … & F ∈ Ψ \\ > n · δ_{F}(n) & … & F ∉ Ψ \end{matrix}

holds. Here the functions γ_{F}(n) and δ_{F}(n) grow to infinity, any γ_{F}(n) is defined in terms of α(n) and thus is almost constant, and any δ_{F}(n) is much faster than any γ_{F}(n). □

Unlike in enumeration, now we cannot hope to replace every γ_{F}(n) with a constant. This, of course, comes as no surprise. By a reduction to 5-DS sequences, it is easily shown ([35]) that for F = ({1, 3}, {1, 5}, {2, 4}, {2, 6}) one has H_{e}(F, n) ≫ nα(n). This F is an example of a star forest. These are simple hypergraphs F 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 [35] we proved that for every star forest F,

H_{i}(F, n) < n · γ_{F}(n)  (36)

where γ_{F}(n) is an almost constant function defined in terms of α(n). Note that by (33), it suffices to prove this bound for H_{e}(F, n). So, in Problem 19, the class Ψ must contain all star forests. Does it consist only from star forests? Since star forests generalize permutation hypergraphs H_{p}, the bound (36) generalizes the bound (34). However, (34) can be probably improved to a ≪ n bound.

One more almost linear bound and back to abab. In the definition (16), 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 H we have v(H) = i(H) but the proper measure of size for hypergraphs is i(H). We generalize the approach of (16) as follows. Suppose that F is a fixed partition with q = e(F) > 1. Then for every F-free hypergraph H (really every, even not simple) we have the inequality ([35])

i(H) < (q − 1)v(H) + e(H) · γ_{F}(e(H))  (37)

where γ_{F}(n) is an almost constant function defined in terms of α(n). The bound (37) is an extension of (18) to hypergraphs. We can also apply (37) to bound H_{i}(F, n) (almost linearly) in terms of H_{e}(F, n) in situations when (33) does not apply.

We conclude our survey by returning to the pattern abab, alias •−∘−•−∘, alias ({1, 3}, {2, 4}).

Example 11 ([33, 35]). We prove that, denoting abab = ({1, 3}, {2, 4}), for every n > 1,

H_{e}(abab, n) = 4n − 5 and H_{i}(abab, n) = 8n − 12.

We begin with the case when G is a simple abab-free graph with the vertex set [n] (so G has only two-element edges). We prove by induction on n that e(G) ≤ 2n − 3. For n = 2 this is true. Let n > 2 and deg(1) ≥ 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 G to I_{1} and I_{2} are simple abab-free graphs and every edge of G, except possibly of {1, n}, lies in I_{1} or in I_{2}. By induction,

e(G) ≤ 1 + 2|I_{1}| − 3 + 2|I_{2}| − 3 = 2(|I_{1}| + |I_{2}|) − 5 = 2n − 3.

In the graph case, e(G) ≤ 2v(G) − 3.

Let now H be a simple abab-free hypergraph with the vertex set [n]. We look at the big edges of H 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 H and five not necessarily distinct vertices v_{1}, …, v_{5} ∈ ⋃ H such that v_{2} < v_{3} < v_{4}, v_{1} < v_{3} < v_{5}, {v_{1}, v_{3}, v_{5}} ⊂ E_{1}, and {v_{2}, v_{3}, v_{4}} ⊂ E_{2}. Moreover, we may assume that v_{1} ≠ v_{2} or v_{4} ≠ v_{5} because E_{1} ≠ E_{2} (H is simple). But then H 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 H.

Not forgetting singleton edges, we conclude that

e(H) ≤ n + (2n − 3) + (n − 2) = 4n − 5
i(H) ≤ n + 2(2n − 3) + (n − 2) + 2(n − 2) = 8n − 12.

The abab-free hypergraphs

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

show that these bounds are tight. □

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.

Acknowledgments. I am indebted to Jiří Matoušek 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.

References

[1] R. Adamec, M. Klazar and P. Valtr, Generalized Davenport–Schinzel sequences with linear upper bound, Discrete Mathematics, 108 (1992), 219–229. [Zentralblatt für Mathematik und ihre Grenzgebiete 768.05007 and Mathematical Reviews 93k:05015.]

[2] 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. [Zbl 880.05050 and MR 98f:05046.]

[3] P. K. Agarwal and M. Sharir, Davenport–Schinzel sequences and their geometric applications. In: J.-R. Sacks and J. Urrutia (editors), Handbook of Computational Geometry, Elsevier, Amsterdam, 2000; pp. 1–47. [Zbl 991.24846 and MR CMP 1 746 674.] [4] 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. [Zbl 697.05003 and MR 90m:11034.]

[5] N. Alon and E. Friedgut, On the number of permutations avoiding a given pattern, J. Comb. Theory, Ser. A, 89 (2000), 133–140. [Zbl 991.47660 and MR 2000i:05007.]

[6] N. Alon and S. Onn, Separable partitions, Discrete Applied Mathematics, 91 (1999), 39–51. [Zbl 926.05011 and MR 2000j:05010.]

[7] M. I. Atallah, Some dynamic computational geometry problems, Computers and Mathematics with Applications, 11 (1985), 1171–1181. [Zbl 586.68085 and MR 87b:68095.]

[8] S. Aviran and S. Onn, Momentopes, the complexity of vector partitioning, and Davenport-Schinzel sequences, Discrete and Computational Geometry, 27 (2002), 409–417. [Zbl and MR .]

[9] B. J. Birch, H. Halberstam and C. A. Rogers (editors), The Collected Works of Harold Davenport. Volume IV, Academic Press, London, 1977. [Zbl 383.01022 and MR 58#27141.]

[10] M. Bóna, Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps, J. Comb. Theory, Ser. A, 80 (1997), 257–272. [Zbl 0887.05004 and MR 98j:05003.]

[11] M. Bóna, The solution of a conjecture of Stanley and Wilf for all layered patterns, J. Comb. Theory, Ser. A, 85 (1999), 133–140. [Zbl 919.05002 and MR 99i:05005.]

[12] F. J. Burkowski and E. F. Ecklund, Jr., Exclusion sequences with regularity conditions. In: F. Hoffman et al. (editors), The Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton 1974 (USA), Congressus Numerantium X, Utilitas Mathematica Publishing, Inc., Winnipeg, 1974; pp. 261–266. [Zbl 313.05004 and MR 52#2901.]

[13] H. Davenport, A combinatorial problem connected with differential equations II, Acta Arithmetica, 17 (1971), 363–372. [Zbl 216.30204 and MR 44#2619.]

[14] H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations, American Journal of Mathematics, 87 (1965), 684–694. [Zbl 132.00601 and MR 32#7426.]

[15] H. Davenport and A. Schinzel, A note on sequences and subsequences, Elemente der Mathematik, 20 (1965), 63–64. [Zbl 132.25101 and MR — not reviewed.]

[16] A. J. Dobson and S. O. Macdonald, Lower bounds for the lengths of Davenport–Schinzel sequences, Utilitas Mathematica, 6 (1974), 251–257. [Zbl 299.05010 and MR 50#9781.]

[17] 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. [Zbl 712.52009 and MR 90k:52019.]

[18] Z. Füredi and P. Hajnal, Davenport–Schinzel theory of matrices, Discrete Math., 103 (1992), 233–251. [Zbl 776.05024 and MR 93g:05026.]

[19] D. Gardy and D. Gouyou-Beauchamps, Enumerating Davenport-Schinzel sequences, RAIRO. Informatique Théorique et Applications, 26 (1992), 387–402. [Zbl 769.05007 and MR 93k:05011.]

[20] R. K. Guy, Unsolved Problems in Number Theory, Springer, Berlin, 1981. [Zbl 474.10001 and MR 83k:10002.] (Second edition appeared in 1994.)

[21] S. Hart and M. Sharir, Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes, Combinatorica, 6 (1986), 151–177. [Zbl 636.05003 and MR 88f:05004.]

[22] M. Katchalski and H. Last, On geometric graphs with no two edges in convex position, Discrete Comput. Geom., 19 (1998), 399–404. [Zbl 908.05033 and MR 99d:52015.]

[23] M. Klazar, A general upper bound in extremal theory of sequences, Commentationes Mathematicae Universitatis Carolinae, 33 (1992), 737–746. [Zbl 781.05049 and MR 94g:05095.]

[24] M. Klazar, Two results on a partial ordering of finite sequences, Commentat. Math. Univ. Carol., 34 (1993), 697–705. [Zbl 789.05090 and MR 95i:05108.]

[25] M. Klazar, A linear upper bound in extremal theory of sequences, J. Comb. Theory, Ser. A, 68 (1994), 454–464. [Zbl 808.05096 and MR 95m:11033.]

[26] M. Klazar, Combinatorial Aspects of Davenport–Schinzel Sequences, Ph.D. thesis, Charles University, Prague, 1995.

[27] M. Klazar, Extremal functions for sequences, Discrete Math., 150 (1996), 195–203. [Zbl 851.05093 and MR 97c:05019.]

[28] M. Klazar, On abab-free and abba-free set partitions, European Journal of Combinatorics, 17 (1996), 53–68. [Zbl 840.05004 and MR 96j:05019.]

[29] M. Klazar, Combinatorial aspects of Davenport–Schinzel sequences, Discrete Math., 165-166 (1997), 431–445. [Zbl 948.05008 and MR 98d:05149.]

[30] M. Klazar, Extremal problems for colored trees and Davenport-Schinzel sequences, Discrete Math., 197-198 (1999), 469–482. [Zbl 936.05060 and MR 99k:05004.]

[31] M. Klazar, On the maximum lengths of Davenport–Schinzel sequences. In: R. L. Graham et al. (editors), Contemporary Trends in Discrete Mathematics, Štiřín Castle 1997 (Czech Republic), American Mathematical Society, Providence RI, 1999; pp. 169–178. [Zbl 938.05004 and MR 2000h:11023.]

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

[33] M. Klazar, Counting pattern-free set partitions. II: Noncrossing and other hypergraphs, Electronic Journal of Combinatorics, 7 (2000), R34. [Zbl 944.05002 and MR 2000m:05007.]

[34] M. Klazar, The Füredi–Hajnal conjecture implies the Stanley–Wilf conjecture. In: D. Krob, A. A. Mikhalev and A. V. Mikhalev (editors), Formal Power Series and Algebraic Combinatorics, Moscow 2000 (Russia), Springer, Berlin, 2000; pp. 250–255. [Zbl 954.05048 and MR 2001k:05005.]

[35] M. Klazar, Extremal problems (and a bit of enumeration) for hypergraphs with linearly ordered vertex sets, ITI Series 2001-021, technical report, 40 pages.

[36] M. Klazar and P. Valtr, Generalized Davenport–Schinzel sequences, Combinatorica, 14 (1994), 463–476. [Zbl 812.05067 and MR 96h:05206.]

[37] P. Komjáth, A simplified construction of nonlinear Davenport–Schinzel sequences, J. Comb. Theory, Ser. A, 49 (1988), 262–267. [Zbl 673.05001 and MR 89m:11019.]

[38] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math., 1 (1972), 333–350. [Zbl 231.05014 and MR 46#8852.] [39] M. Loebl and J. Nešetřil, Fast and slow growing (a combinatorial study of unprovability). In:

A. D. Keedwell (editor), Surveys in Combinatorics, 1991, Cambridge University Press, Cambridge, UK, 1991; pp. 119–160. [Zbl 735.03017 and MR 93d:03061.] (London Mathematical Society Lecture Note Series, 166.)

[40] W. H. Mills, Some Davenport–Schinzel sequences. In: R. S. D. Thomas and H. C. Williams (editors), The 3rd Manitoba Conference on Numerical Mathematics, Winnipeg 1973 (USA), Congressus Numerantium IX, Utilitas Mathematica Publishing Inc., Winnipeg, 1974; pp. 307–314. [Zbl 321.05006 and MR 50#135.]

[41] W. H. Mills, On Davenport–Schinzel sequences, Utilitas Math., 9 (1976), 87–112. [Zbl 337.05006 and MR 53#10703.]

[42] R. C. Mullin and R. G. Stanton, A map-theoretic approach to Davenport–Schinzel sequences, Pacific Journal of Mathematics, 40 (1972), 167–172. [Zbl 233.05013 and MR 46#1745.]

[43] J. Pach, F. Shahrokhi and M. Szegedy, Applications of the crossing number, Algorithmica, 16 (1996), 111–117. [Zbl 0851.68088 and MR 97h:05054.]

[44] C. R. Peterkin, Some results on Davenport–Schinzel sequences. In: R. S. D. Thomas and H. C. Williams (editors), The 3rd Manitoba Conference on Numerical Mathematics, Winnipeg 1973 (USA), Congressus Numerantium IX, Utilitas Mathematica Publishing Inc., Winnipeg, 1974; pp. 337–344. [Zbl 324.05008 and MR 50#136.]

[45] Y. Poupard, Étude et dénombrement parallèles des partitions non croisées d’un cycle et des découpages d’un polygone convexe, Discrete Math., 2 (1972), 279–288. [Zbl 252.05005 and MR 46#3369.]

[46] B. C. Rennie and A. J. Dobson, Upper bounds for the lengths of Davenport–Schinzel sequences, Utilitas Math., 8 (1975), 181–185. [Zbl 364.05004 and MR 52#13624.]

[47] D. P. Roselle, An algorithmic approach to Davenport–Schinzel sequences, Utilitas Math., 6 (1974), 91–93. [Zbl 306.05010 and MR 50#9780.]

[48] D. P. Roselle and R. G. Stanton, Results on Davenport–Schinzel sequences. In: R. Mullin, K. B. Reid and D. P. Roselle (editors), Louisiana Conference on Combinatorics, Graph Theory and Computing, Baton Rouge 1970 (USA), Louisiana State University, Baton Rouge, 1970; pp. 249–267. [Zbl 239.05004 and MR 43#68.]

[49] D. P. Roselle and R. G. Stanton, Some properties of Davenport–Schinzel sequences, Acta Arith., 17 (1971), 355–362. [Zbl 215.33203 and MR 44#1641.]

[50] H. Sharir, Almost linear upper bounds on the length of general Davenport–Schinzel sequences, Combinatorica, 7 (1987), 131–143. [Zbl 636.05004 and MR 89f:11037.]

[51] H. Sharir, Improved lower bounds on the length of Davenport–Schinzel sequences, Combinatorica, 8 (1988), 117–124. [Zbl 672.05015 and MR 89j:11024.]

[52] M. Sharir and P. K. Agarwal, Davenport–Schinzel Sequences and Their Geometric Applications, Cambridge University Press, Cambridge, UK, 1995. [Zbl 834.68113 and MR 96e:11034.]

[53] R. Simion, Noncrossing partitions, Discrete Math., 217 (2000), 367–409. [Zbl 959.05009 and MR 2001g:05011.]

[54] N. J. A. Sloane (2000), The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/˜ njas/sequences/.

[55] R. G. Stanton and P. H. Dirksen, Davenport–Schinzel sequences, Ars Combinatoria, 1 (1976), 43–51. [Zbl 335.05001 and MR 53#13106.]

[56] R. G. Stanton and D. P. Roselle, A result on Davenport–Schinzel sequences. In: P. Erdős, A. Rényi and V. T. Sós (editors), Combinatorial Theory and Its Applications, Balatonfüred 1969 (Hungary), Colloquia Mathematica Societatis János Bolyai 4, Vol. II, Nort-Holland, Amsterdam, 1970; pp. 1023–1027. [Zbl 215.33202 and MR 46#3324.]

[57] E. Szemerédi, On a problem of Davenport and Schinzel, Acta Arith., 25 (1974), 213–224. [Zbl 291.05003 and MR 49#244.]

[58] R. E. Tarjan, Efficiency of a good but not linear set union algorithm, Journal of the Association for Computing Machinery, 22 (1975), 215–225. [Zbl 307.68029 and MR 56#17194.]

[59] P. Valtr, Graph drawing with no k pairwise crossing edges. In: G. DiBattista (editor), Graph Drawing’97, Rome 1997 (Italy), Springer, Berlin, 1997; pp. 205–218. [Zbl — not reviewed and MR 99e:68166.] (Lecture Notes in Computer Science, 1353.)

[60] P. Valtr, On geometric graphs with no k pairwise parallel edges, Discrete Comput. Geom., 19 (1998), 461–469. [Zbl 908.05035 and MR 99a:05138.]

[61] P. Valtr, Generalizations of Davenport–Schinzel sequences. In: R. L. Graham et al. (editors), Contemporary Trends in Discrete Mathematics, Štiřín Castle 1997 (Czech Republic), American Mathematical Society, Providence RI, 1999; pp. 349–389. [Zbl 942.68104 and MR 2001d:68185.]

[62] P. Valtr, On an extremal problem for colored trees, Eur. J. Comb., 20 (1999), 115–121. [Zbl 924.05040 and MR 99k:05061.]

[63] P. Valtr, Davenport–Schinzel trees, submitted.

[64] A. Wiernik and M. Sharir, Planar realizations of nonlinear Davenport–Schinzel sequences by segments, Discrete Comput. Geom., 3 (1988), 15–47. [Zbl 636.68043 and MR 89h:11088.]

[65] http://www.isinet.com/isi/