ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 5 Klazar, Martin, Charles University, Prague, Czech Republic Combinatorics of a containment relation that generalizes Davenport–Schinzel sequences. A finite sequence u = a_{1}a_{2} … a_{k} is contained in another sequence v = b_{1}b_{2} … b_{l} if v has a subsequence b_{i_{1}}b_{i_{2}} … b_{i_{k}} that differs from u only by an injective renaming of symbols. For example, baba is contained in 516641234. Let Forb(u) be sequences not containing u (D. –S. sequences are the sequences Forb(ababa …)). We discuss extremal and enumerative results and problems connected with the sets Forb(u) for various sequences u. Reference: M. Sharir and P. K. Agarwal, Davenport–Schinzel sequences and their geometric applications, Cambridge University Press, 1995. M. Klazar, Combinatorial aspects of Davenport–Schinzel sequences, Discrete Math. 165–166 (1997), 431–445.