Well quasi-order in combinatorics: embeddings and homomorphisms

doi:10.1017/CBO9781316106853.009

8 - Well quasi-order in combinatorics: embeddings and homomorphisms

Published online by Cambridge University Press: 05 July 2015

Sophie Huczynska and

Nik Ruškuc

Edited by

Artur Czumaj ,

Agelos Georgakopoulos ,

Daniel Král ,

Vadim Lozin and

Oleg Pikhurko

Show author details

Artur Czumaj: Affiliation:
University of Warwick
Agelos Georgakopoulos: Affiliation:
University of Warwick
Daniel Král: Affiliation:
University of Warwick
Vadim Lozin: Affiliation:
University of Warwick
Oleg Pikhurko: Affiliation:
University of Warwick

Book contents

Get access

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 - 294

DOI: https://doi.org/10.1017/CBO9781316106853.009 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

[1] M.H., Albert and M.D., Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), 1–15.

[2] M.H., Albert, M.D., Atkinson, M., Bouvel, N., Ruškuc and V., Vatter, Geometric grid classes of permutations, Trans. Amer. Math. Soc. 365 (2013), 5859–5881.

[3] M.H., Albert, M.D., Atkinson and N., Ruškuc, Regular closed sets of permutations, Theoret. Comput. Sci. 306 (2003), 85–100.

[4] M.H., Albert, M.D., Atkinson and V., Vatter, Subclasses of the separable permutations, Bull. London Math. Soc. 5 (2011), 859–870.

[5] M.H., Albert, N., Ruškuc and V., Vatter, Inflations of geometric grid classes of permutations, Israel J. Math. (2014). DOI 10.1007/s11856-014-1098-8.Google Scholar

[6] M.D., Atkinson, Restricted permutations, Discrete Math. 195 (1999), 27–38.

[7] M.D., Atkinson, M.M., Murphy and N., Ruškuc, Partially well-ordered closed sets of permutations, Order 19 (2002), 101–113.

[8] F.M., Abu-Khzam and M.A., Langston, Graph coloring and the immersion order, in Computing and Combinatorics, T., Warnow and B., Zhu (eds.), Lecture Notes in Computer Science 2697, Springer, Berlin, 2003, pp. 394–403.Google Scholar

[9] M., Bousquet-Mélou, Algebraic generating functions in enumerative combinatorics and context-free languages, in STACS 2005, V., Diekert and B., Durand (eds.), Lecture Notes in Computer Science 3404, Springer, Berlin, 2005, pp. 18–35.Google Scholar

[10] R., Brignall, S., Huczynska and V., Vatter, Decomposing simple permutations, with enumerative consequences, Combinatorica 28 (2008), 385–400.

[11] R., Brignall, N., Ruškuc and V., Vatter, Simple permutations: decidability and unavoidable substructures, Theoret. Comput. Sci. 391 (2008), 150–163.

[12] G., Cherlin, The Classification of Countable Homogeneous Directed Graphs and Countable Homogeneous n-Tournaments, Mem. Amer. Math. Soc. 131, AMS, Rhode Island, 1998.Google Scholar

[13] G., Cherlin, Forbidden substructures and combinatorial dichotomies: WQO and universality, Discrete Math. 311 (2011), 1534–1584.

[14] M., Chudnovsky and P., Seymour, A well-quasi-order for tournaments, J.Combin. Theory, Ser. B 101 (2011), 47–53.

[15] D.G., Corneil, H., Lerchs and L.S., Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981), 163–174.

[16] J., Daligault, M., Rao and S., Thomassé, Well-quasi-order of relabel functions, Order 27 (2010), 301–315.

[17] P., Damaschke, Induced subgraphs and well quasi-ordering, J. Graph Theory 14 (1990), 427–435.

[18] R., Diestel, Graph Theory, Graduate Texts in Mathematics 173, Springer, Berlin, 2010Google Scholar

[19] G., Ding, Subgraphs and well quasi-ordering, J. Graph Theory 16 (1992), 489–502.

[20] G., Ding, Excluding a long double path minor, J. Combin. Theory, Ser. B 66 (1996), 11–23.

[21] D., Duffus, P.L., Erdös, J., Nešetřil and L., Soukup, Antichains in the homomorphism order of graphs, Comment. Math. Univ. Carolin. 48 (2007), 571–583.

[22] S., Eilenberg, Automata, Languages and Machines Vol A, Academic Press, NY, 1974.Google Scholar

[23] J., Fiala, J., Hubicka and Y., Long, Universality of intervals of line graph order, European J. Combin. 41 (2014), 221–231.

[24] J., Fiala, D., Paulusma and J.A., Telle, Matrix and graph orders derived from locally constrained graph homomorphisms, in Mathematical Foundations of Computer Science 2005, Lecture Notes in Computer Science 3618, Springer Verlag, 2005, pp. 340–351.Google Scholar

[25] R., Fraïssé, Theory of Relations, North-Holland, Amsterdam, 1953.Google Scholar

[26] D., Glickenstein, Math 443/543 Graph Theory Notes 11, Department of Mathematics, University of Arizona, 2008.

[27] R., Govindana and S., Ramachandramurthi, A weak immersion relation on graphs and its applications, Discrete Math. 230 (2001), 189–206.

[28] P., Hell and J., Nešetřil, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications 28, OUP, Oxford, 2004.

[29] C.W., Henson, Countable homogeneous relational systemsand N0-categorical theories, J. Symbolic Logic 37 (1972), 494–500.

[30] G., Higman, Ordering by divisibility in abstract algebras, Proc. Lon-don Math. Soc. 2 (1952), 326–336.Google Scholar

[31] W., Hodges, Model Theory, Cambridge University Press, Cambridge, 1993.Google Scholar

[32] J.E., Hopcroft and J.D., Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading MA, 1979.Google Scholar

[33] J., Hubička and J., Nešetřil, Universal partial order represented by means of oriented trees and other simple graphs, European J. Combin. 26 (2005), 765–778.

[34] S., Huczynska and N., Ruškuc, Homomorphic image orders on combinatorial structures, Order (2014), to appear.

[35] I., Kim, On Containment Relations in Directed Graphs, PhD thesis, Princeton, 2013.

[36] N., Korpelainen and V., Lozin, Bipartite induced subgraphs and well quasi-ordering, J. Graph Theory 67 (2011), 235–249.

[37] N., Korpelainen and V., Lozin, Two forbidden induced subgraphs and well quasi-ordering, Discrete Math. 311 (2011), 1813–1822.

[38] N., Korpelainen, V., Lozin and I., Razgon, Boundary properties of well quasi-ordered sets of graphs, Order 30 (2013), 723–735.

[39] I., Kříž and J., Sgall, Well-quasi-ordering depends on the labels, Acta Sci. Math. 55 (1991), 59–65.

[40] I., Kříž and R., Thomas, On well-quasi-ordering finite structures with labels, Graphs Combin. 6 (1990), 41–49.

[41] J.B., Kruskal, Well-quasi-ordering, the tree theorem and Vaszsonyi's conjecture, Trans. Amer. Math. Soc. 95 (1960), 210–225.

[42] J.B., Kruskal, The theory of well quasi-ordering: a frequently discovered concept, J. Combin. Theory, Ser. A 13 (1972), 297–305.

[43] K., Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math. 15 (1930), 271–283.

[44] C., Landraitis, A combinatorial property of the homomorphism relation between countable order types, J. Symbolic Logic 44 (1979), 403–411.

[45] B., Latka, Finitely constrained classes of homogeneous directed graphs, J. Symbolic Logic 59 (1994), 124–139.

[46] R., Laver, On Frai'ssé's order type conjecture, Ann. Math. (2) 93 (1971), 89–111.

[47] E., Lehtonen, Labeled posets are universal, European J. Combin. 29 (2008), 493–506.

[48] C-H., Liu, Graph Structures and Well Quasi-Ordering, PhD Thesis, Georgia Institute of Technology, 2014.Google Scholar

[49] W., Mader, Wohlquasigeordnete Klassen endlicher Graphen, J. Combin. Theory, Ser. B 12 (1972), 105–122.

[50] A., Marcus and G., Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory, Ser. A 107 (2004), 153160.Google Scholar

[51] M.M., Murphy, Restricted Permutations, Antichains, Atomic Classes and Stack Sorting, Ph.D.Thesis, University of St Andrews, 2003.Google Scholar

[52] M.M., Murphy and V., Vatter, Profile classes and partial well-order for permutations, Electron. J. Combin. 9 (2003), R17.Google Scholar

[53] C.St.J.A., Nash-Williams, On well-quasi-ordering finite trees. Math. Proc. Cambridge Philos. Soc. 59 (1963), 833–835.

[54] C.St.J.A., Nash-Williams, On well-quasi-ordering infinite trees, Math. Proc. Cambridge Philos. Soc. 61 (1965), 697–720.

[55] J., Nešetřil and P., Ossona de Mendez, Sparsity. Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer, Heidelberg, 2012.Google Scholar

[56] M., Petkovšek, Letter graphs and well-quasi-order by induced sub-graphs, Discrete Math. 244 (2002), 375–388.

[57] M., Pouzet, Un bel ordre dábritement et ses rapports avec les bornes d'une multirelation, C. R. Acad. Sci. Paris Ser AB 274 (1972), 1677–1680.Google Scholar

[58] A., Pultr and V., Trnková, Combinatorial, Algebraic, and Topological Representations of Groups, Semigroups, and Categories, North-Holland Mathematical Library 22, North-Holland, Amsterdam, 1980.Google Scholar

[59] N., Robertson and P., Seymour, Graph minors. XX. Wagners conjecture, J. Combin. Theory, Ser.B 92 (2004), 325–357.

[60] N., Robertson and P., Seymour, Graph minors. XXIII. Nash-Williams' immersion conjecture, J. Combin. Theory, Ser. B 100 (2010), 181–205.Google Scholar

[61] R.P., Stanley, Enumerative Combinatorics Vol 2, Cambridge Studies in Advanced Mathematics 62, CUP, Cambridge, 1999.Google Scholar

[62] V., Vatter, Small permutation classes, Proc. London Math. Soc. 103 (2011), 879–921.

[63] K., Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590.