Configurations can be studied from a graph-theoretical viewpoint via the so-called Levi graphs and lie at the heart of graphs, groups, surfaces, and geometries, all of which are very active areas of mathematical exploration. In this self-contained textbook, algebraic graph theory is used to introduce groups; topological graph theory is used to explore surfaces; and geometric graph theory is implemented to analyze incidence geometries.
After a preview of configurations in Chapter 1, a concise introduction to graph theory is presented in Chapter 2, followed by a geometric introduction to groups in Chapter 3. Maps and surfaces are combinatorially treated in Chapter 4. Chapter 5 introduces the concept of incidence structure through vertex colored graphs, and the combinatorial aspects of classical configurations are studied. Geometric aspects, some historical remarks, references, and applications of classical configurations appear in the last chapter.
With over two hundred illustrations, challenging exercises at the end of each chapter, a comprehensive bibliography, and a set of open problems, Configurations from a Graphical Viewpoint is well suited for a graduate graph theory course, an advanced undergraduate seminar, or a self-contained reference for mathematicians and researchers.
Author(s): Tomaz Pisanski, Brigitte Servatius
Series: Birkhäuser Advanced Texts Basler Lehrbücher
Publisher: Birkhäuser
Year: 2013
Language: English
Commentary: Vector PDF, Front Cover
Pages: 295
1 Introduction
1.1 Hexagrammum Mysticum
1.1.1 The Fano Plane
1.1.2 The Miquel Configuration\d\+\r
1.1.3 The Pappus Configuration
1.1.4 Pappus-Like Configurations
1.1.5 The Tetrahedron
1.1.6 Overview
1.2 Exercises
2 Graphs
2.1 Basic Definitions
2.2 Examples of Graphs
2.2.1 Paths
2.2.2 Cycles
2.2.3 Complete Bipartite Graphs and Multipartite Graphs
2.2.4 Wheel Graphs
2.2.5 Prism Graphs
2.2.6 Antiprism Graphs
2.2.7 Platonic and Archimedean Graphs
2.2.8 Polyhedral Graphs
2.2.9 Generalized Petersen Graphs
2.2.10 Cages
2.2.11 Planar Graphs
2.3 Regularity
2.3.1 Regular Graphs
2.3.2 Cubic Graphs and LCF Notation
2.3.3 Regularity and Bipartite Graphs
2.3.4 Semiregular Bipartite Graphs
2.3.5 Permutations
2.3.6 Directed Graphs and Multigraphs
2.4 Operations on Graphs
2.4.1 Graph Complement
2.4.2 Graph Union
2.4.3 Graph Join, Cone, and Suspension
2.4.4 One-Point Union and Connectivity
2.4.5 Cartesian Product
2.4.6 Tensor Product
2.4.7 Strong Product
2.4.8 Line Graph
2.4.9 Subdivision Graph
2.4.10 Graph Square
2.5 Graph Colorings
2.5.1 Vertex Colorings
2.5.2 Edge Colorings
2.6 From Geometry to Graphs and Back
2.6.1 Metric Space and Distance Function
2.6.2 Distances in Graphs
2.6.3 Intersection Graphs
2.6.4 Intersection Graphs of a Family of Balls
2.6.5 Convex Sets
2.6.6 Representations and Drawings of Graphs
2.6.7 Generalized Petersen Graphs as Unit Distance Graphs
2.7 Exercises
3 Groups, Actions, and Symmetry
3.1 Groups
3.1.1 Graph Automorphisms
3.1.2 Definition of Groups
3.1.3 Subgroups
3.1.4 Cosets
3.1.5 Group Homomorphisms and Isomorphisms
3.2 Cayley Graphs
3.2.1 Definition of the Cayley Graph
3.2.2 Examples of Cayley Graphs
3.3 Group Actions
3.3.1 Permutation Groups
3.3.2 Actions on Cayley Graphs
3.3.3 Primitive Versus Imprimitive Actions
3.3.4 Burnside’s Theorem
3.3.5 The Escher Problem
3.4 Symmetry and Transitivity
3.4.1 Vertex- and Edge-Transitive Graphs
3.4.2 Semisymmetric Graphs
3.4.3 Arc-Transitive Graphs
3.4.4 s-Arc Transitivity
3.4.5 1=2-Arc Transitivity
3.4.6 Automorphisms of Generalized Petersen Graphs
3.5 Voltage Graphs and Covering Graphs
3.5.1 Quotient Graphs
3.5.2 Pregraphs Revisited
3.5.3 Pregraphs on a Single Vertex
3.5.4 Voltage Graphs and Regular Coverings
3.5.5 Voltage Assignments on B.1I 1/
3.5.6 Generalized Petersen Graphs as Coverings
3.5.7 f0; 1g Voltage
3.5.8 Permutation Voltage Assignments and Ordinary Coverings
3.5.9 Cages as Covering Graphs
3.6 Automorphisms of the Symmetric Group
3.7 Exercises
4 Maps
4.1 Geometric Surfaces
4.1.1 Polyhedral Graphs
4.1.2 Polygonal Surfaces
4.1.3 The Topology of Polygonal Surfaces
4.2 Maps and Flags
4.2.1 A Graph Theoretical Approach to Surfaces
4.2.2 Dual Constructions
4.2.3 Flag Orbits and Orientability
4.2.4 Map Projections
4.3 The Classification of Surfaces
4.3.1 Vertex Splitting and Edge Contraction
4.3.2 Reduction to a Unitary Map
4.3.3 Assembling Crosscaps
4.3.4 Assembling Handles
4.3.5 Crosscaps Canceling Handles
4.3.6 Normal Forms
4.4 Operations on Maps
4.4.1 Uniform Flag Operations
4.4.2 The Medial
4.4.3 Truncation
4.4.4 Barycentric Subdivision and Combinatorial Map
4.4.5 Semiuniform Subdivisions
4.4.6 Edge and Vertex Joins
4.5 Map Automorphisms
4.5.1 Regular Maps and Fundamental Regions
4.5.2 Harmonious Maps
4.5.3 Self-dual Maps
4.5.4 Automorphisms of Planar Graphs of Low Connectivity
4.6 Exercises
5 Combinatorial Configurations
5.1 A Combinatorial Approach to Configurations
5.1.1 Incidence Structures
5.1.2 Coset Incidence Structures
5.1.3 Lineal Incidence Structures
5.1.4 Regularity of Incidence Structures
5.1.5 Definition of Combinatorial Configurations
5.2 Combinatorial (v_3) Configurations of Small Order
5.3 Classical Configurations
5.3.1 The Fano Plane
5.3.2 The M¨obius–Kantor Configuration
5.3.3 The Pappus Configuration
5.3.4 The Desargues Configuration
5.3.5 The Cremona–Richmond Configuration
5.3.6 The Reye Configuration
5.3.7 Mobius (8_4) Incidence Structures
5.4 Autopolar Combinatorial Configurations
5.5 Cyclic Haar Graphs and Cyclic Configurations
5.5.1 Cyclic Haar Graphs as Cyclic Covering Graphs Over a Dipole
5.5.2 Cyclic Haar Graphs as Certain Cayley Graphs for the Dihedral Group
5.5.3 Associating a Cyclic Haar Graph to a Number
5.5.4 Isomorphisms of Cyclic Haar Graphs
5.5.5 Cyclic Configurations and Cyclic Haar Graphs
5.6 Exercises
6 Geometric Configurations
6.1 Geometric Planes
6.1.1 From Euclid to Descartes and Beyond
6.1.2 The Projective Plane
6.1.3 Homogeneous Coordinates
6.1.4 Calculations in the Real Projective Plane
6.1.5 The Theorems of Pappus and Desargues
6.1.6 Proving Desargues from Pappus
6.2 Finite Projective Planes
6.2.1 Affine and Projective Realizations over Finite Fields
6.3 Realization of Classical Configurations
6.3.1 Fano Plane
6.3.2 The Mobius–Kantor Configuration
6.3.3 The Pappus Configuration
6.3.4 The Desargues Configuration
6.3.5 The Cremona–Richmond Configuration
6.3.6 The Reye Configuration
6.4 Representations and Realizations
6.4.1 The Dimension of a Realization
6.4.2 Lifting Configurations
6.4.3 General Lifting
6.5 The Grunbaum Incidence Calculus
6.6 Constructing Treelike Configurations
6.7 Realizing the Gray Graph and Bouwer Graph
6.8 The Zindler Degree of Regularity of an Incidence Structure
6.9 Polycirculants and Polycyclic Configurations
6.9.1 Cubic Circulants
6.9.2 Bicirculants
6.10 Exercises
References
Index
