Pavol Hell and Jaroslav Nešetřil
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0004
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter focuses on the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs. The difference is noticeable with even just one graph. For instance, a ...
More
This chapter focuses on the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs. The difference is noticeable with even just one graph. For instance, a graph having only the identity homomorphisms to itself is called rigid; rigid graphs are the building blocks of many constructions. Many useful constructions of rigid graphs are provided, and it is shown that asymptotically almost all graphs are rigid; infinite rigid graphs with arbitrary cardinality are also constructed. The homomorphisms among a set of graphs impose the algebraic structure of a category, and every finite category is represented by a set of graphs. This is the generalization of the theorem of Frucht from Chapter 1. Also, as in the case studied by Frucht, it is shown that the representing graphs can be required to have any of a number of graph theoretic properties. However, these properties cannot include having bounded degrees — somewhat surprisingly, since Frucht proved that cubic graphs represent all finite groups.Less
This chapter focuses on the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs. The difference is noticeable with even just one graph. For instance, a graph having only the identity homomorphisms to itself is called rigid; rigid graphs are the building blocks of many constructions. Many useful constructions of rigid graphs are provided, and it is shown that asymptotically almost all graphs are rigid; infinite rigid graphs with arbitrary cardinality are also constructed. The homomorphisms among a set of graphs impose the algebraic structure of a category, and every finite category is represented by a set of graphs. This is the generalization of the theorem of Frucht from Chapter 1. Also, as in the case studied by Frucht, it is shown that the representing graphs can be required to have any of a number of graph theoretic properties. However, these properties cannot include having bounded degrees — somewhat surprisingly, since Frucht proved that cubic graphs represent all finite groups.
A. A. Ivanov
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198527596
- eISBN:
- 9780191713163
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198527596.003.0005
- Subject:
- Mathematics, Pure Mathematics
This chapter shows that N[3] is the extraspecial group Q[3] ≅ 21+12 + extended by a group R of order 3 acting fixed-point freely on Q[3]/Z[3] (where Z[3] is the centre of Q[3]/) and ...
More
This chapter shows that N[3] is the extraspecial group Q[3] ≅ 21+12 + extended by a group R of order 3 acting fixed-point freely on Q[3]/Z[3] (where Z[3] is the centre of Q[3]/) and that G[3] is the automorphism group Aut (M22) of the sporadic Mathieu group M22. Shpectorov's geometric characterization of M22 in terms of a Petersen type geometry is used. The sporadic Mathieu group M22 appears before any specific completions of G can be considered.Less
This chapter shows that N[3] is the extraspecial group Q[3] ≅ 21+12 + extended by a group R of order 3 acting fixed-point freely on Q[3]/Z[3] (where Z[3] is the centre of Q[3]/) and that G[3] is the automorphism group Aut (M22) of the sporadic Mathieu group M22. Shpectorov's geometric characterization of M22 in terms of a Petersen type geometry is used. The sporadic Mathieu group M22 appears before any specific completions of G can be considered.
Pavol Hell and Jaroslav Nešetřil
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up ...
More
This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up in more detail in later chapters. It gives the flavour of combinatorial aspects, algorithmic aspects, retractions, duality, constraint satisfaction problems, as well as structural properties of homomorphism composition. The highlights of this chapter include a simple proof of the Colouring Interpolation Theorem, a generalization of the No-Homomorphism Lemma, the construction of a triangle-free graph to which all cubic triangle-free graphs are homomorphic, a case of the Edge Reconstruction Conjecture, and a generalization of a theorem of Frucht on graphs with prescribed automorphism groups.Less
This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up in more detail in later chapters. It gives the flavour of combinatorial aspects, algorithmic aspects, retractions, duality, constraint satisfaction problems, as well as structural properties of homomorphism composition. The highlights of this chapter include a simple proof of the Colouring Interpolation Theorem, a generalization of the No-Homomorphism Lemma, the construction of a triangle-free graph to which all cubic triangle-free graphs are homomorphic, a case of the Edge Reconstruction Conjecture, and a generalization of a theorem of Frucht on graphs with prescribed automorphism groups.
Matt Clay
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691158662
- eISBN:
- 9781400885398
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691158662.003.0006
- Subject:
- Mathematics, Geometry / Topology
This chapter discusses the automorphisms of free groups. Every group is the collection of symmetries of some object, namely, its Cayley graph. A symmetry of a group is called an automorphism; it is ...
More
This chapter discusses the automorphisms of free groups. Every group is the collection of symmetries of some object, namely, its Cayley graph. A symmetry of a group is called an automorphism; it is merely an isomorphism of the group to itself. The collection of all of the automorphisms is also a group too, known as the automorphism group and denoted by Aut (G). The chapter considers basic examples of groups to illustrate what an automorphism is, with a focus on the automorphisms of the symmetric group on three elements and of the free abelian group. It also examines the dynamics of an automorphism of a free group and concludes with a description of train tracks, a topological model for the free group, and the Perron–Frobenius theorem. Exercises and research projects are included.Less
This chapter discusses the automorphisms of free groups. Every group is the collection of symmetries of some object, namely, its Cayley graph. A symmetry of a group is called an automorphism; it is merely an isomorphism of the group to itself. The collection of all of the automorphisms is also a group too, known as the automorphism group and denoted by Aut (G). The chapter considers basic examples of groups to illustrate what an automorphism is, with a focus on the automorphisms of the symmetric group on three elements and of the free abelian group. It also examines the dynamics of an automorphism of a free group and concludes with a description of train tracks, a topological model for the free group, and the Perron–Frobenius theorem. Exercises and research projects are included.
Roman Kossak and James H. Schmerl
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198568278
- eISBN:
- 9780191718199
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198568278.003.0005
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
This chapter makes use of an induced version of Ramsey's Theorem to prove several results: the Abramson-Harrington theorem on omitting large indiscernible sets and Hanf numbers for models of ...
More
This chapter makes use of an induced version of Ramsey's Theorem to prove several results: the Abramson-Harrington theorem on omitting large indiscernible sets and Hanf numbers for models of arithmetic; a theorem characterizing the possible automorphism groups of models; and a theorem based on countable recursively saturated models being generated by a set of indiscernibles.Less
This chapter makes use of an induced version of Ramsey's Theorem to prove several results: the Abramson-Harrington theorem on omitting large indiscernible sets and Hanf numbers for models of arithmetic; a theorem characterizing the possible automorphism groups of models; and a theorem based on countable recursively saturated models being generated by a set of indiscernibles.
Benson Farb and Dan Margalit
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691147949
- eISBN:
- 9781400839049
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691147949.003.0009
- Subject:
- Mathematics, Geometry / Topology
This chapter deals with the Dehn–Nielsen–Baer theorem, one of the most beautiful connections between topology and algebra in the mapping class group. It begins by defining the objects in the ...
More
This chapter deals with the Dehn–Nielsen–Baer theorem, one of the most beautiful connections between topology and algebra in the mapping class group. It begins by defining the objects in the statement of the Dehn–Nielsen–Baer theorem, including the extended mapping class group and outer automorphism groups. It then considers the use of the notion of quasi-isometry in Dehn's original proof of the Dehn–Nielsen–Baer theorem. In particular, it discusses a theorem on the fundamental observation of geometric group theory, along with the property of being linked at infinity. It also presents the proof of the Dehn–Nielsen–Baer theorem and an analysis of the induced homeomorphism at infinity before concluding with two other proofs of the Dehn–Nielsen–Baer theorem, one inspired by 3-manifold theory and one using harmonic maps.Less
This chapter deals with the Dehn–Nielsen–Baer theorem, one of the most beautiful connections between topology and algebra in the mapping class group. It begins by defining the objects in the statement of the Dehn–Nielsen–Baer theorem, including the extended mapping class group and outer automorphism groups. It then considers the use of the notion of quasi-isometry in Dehn's original proof of the Dehn–Nielsen–Baer theorem. In particular, it discusses a theorem on the fundamental observation of geometric group theory, along with the property of being linked at infinity. It also presents the proof of the Dehn–Nielsen–Baer theorem and an analysis of the induced homeomorphism at infinity before concluding with two other proofs of the Dehn–Nielsen–Baer theorem, one inspired by 3-manifold theory and one using harmonic maps.