Book contents
- Frontmatter
- Contents
- Preface
- 1 Ramsey classes: examples and constructions
- 2 Recent developments in graph Ramsey theory
- 3 Controllability and matchings in random bipartite graphs
- 4 Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5 Randomly generated groups
- 6 Curves over finite fields and linear recurring sequences
- 7 New tools and results in graph minor structure theory
- 8 Well quasi-order in combinatorics: embeddings and homomorphisms
- 9 Constructions of block codes from algebraic curves over finite fields
- References
8 - Well quasi-order in combinatorics: embeddings and homomorphisms
Published online by Cambridge University Press: 05 July 2015
- Frontmatter
- Contents
- Preface
- 1 Ramsey classes: examples and constructions
- 2 Recent developments in graph Ramsey theory
- 3 Controllability and matchings in random bipartite graphs
- 4 Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5 Randomly generated groups
- 6 Curves over finite fields and linear recurring sequences
- 7 New tools and results in graph minor structure theory
- 8 Well quasi-order in combinatorics: embeddings and homomorphisms
- 9 Constructions of block codes from algebraic curves over finite fields
- References
Summary
Abstract
The notion of well quasi-order (wqo) from the theory of ordered sets often arises naturally in contexts where one deals with infinite collections of structures which can somehow be compared, and it then represents a useful discriminator between ‘tame’ and ‘wild’ such classes. In this article we survey such situations within combinatorics, and attempt to identify promising directions for further research. We argue that these are intimately linked with a more systematic and detailed study of homomorphisms in combinatorics.
1 Introduction
In combinatorics, indeed in many areas of mathematics, one is often concerned with classes of structures that are somehow being compared, e.g. in terms of inclusion or homomorphic images. In such situations one is naturally led to consider downward closed collections of such structures under the chosen orderings. The notion of partial well order (pwo), or its mild generalisation well quasi-order (wqo), can then serve to distinguish between the ‘tame’ and ‘wild’ such classes. In this article we will survey the guises in which wqo has made an appearance in different branches of combinatorics, and try to indicate routes for further development which in our opinion will be potentially important and fruitful.
The aim of this article is to identify major general directions in which wqo has been deployed within combinatorics, rather than to provide an exhaustive survey of all the specific results and publications within the topics touched upon. In this section we introduce the notion of wqo, and present what is arguably the most important foundational result, Higman's Theorem. In Section 2 we attempt a broad-brush picture of wqo in combinatorics, linking it to the notion of homomorphism and its different specialised types. The central Sections 3–5 present three ‘case studies’ – words, graphs and permutations – where wqo has been investigated, and draw attention to specific instances of patterns and phenomena already outlined in Section 2. Finally, in Section 6, we reinforce the homomorphism view-point, and explore possible future developments from this angle.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2015 , pp. 261 - 294Publisher: Cambridge University PressPrint publication year: 2015
References
- 5
- Cited by