A Course in Combinatorics and Graphs

✍ Scribed by Simeon Ball, Oriol Serra

• Publisher: Birkhäuser
• Year: 2024
• Tongue: English
• Leaves: 180
• Series: Compact Textbooks in Mathematics
• Edition: 1
• Category: Library

✦ Synopsis

This compact textbook consists of lecture notes given as a fourth-year undergraduate course of the mathematics degree at the Universitat Politècnica de Catalunya, including topics in enumerative combinatorics, finite geometry, and graph theory. This text covers a single-semester course and is aimed at advanced undergraduates and masters-level students. Each chapter is intended to be covered in 6-8 hours of classes, which includes time to solve the exercises. The text is also ideally suited for independent study. Some hints are given to help solve the exercises and if the exercise has a numerical solution, then this is given. The material covered allows the reader with a rudimentary knowledge of discrete mathematics to acquire an advanced level on all aspects of combinatorics, from enumeration, through finite geometries to graph theory.

The intended audience of this book assumes a mathematical background of third-year students in mathematics, allowing for a swifter useof mathematical tools in analysis, algebra, and other topics, as these tools are routinely incorporated in contemporary combinatorics. Some chapters take on more modern approaches such as Chapters 1, 2, and 9. The authors have also taken particular care in looking for clear concise proofs of well-known results matching the mathematical maturity of the intended audience.

✦ Table of Contents

Preface
Contents
1 Symbolic Enumeration
1.1 Formal Power Series
1.2 Combinatorial Classes
1.3 Examples
1.4 Rooted Plane Trees
1.5 Lagrange Inversion Formula
1.6 Notes and References
1.7 Exercises
2 Labelled Enumeration
2.1 Exponential Generating Functions
2.2 Labelled Classes
2.3 Labelled Constructions
2.4 Permutations
2.5 Set Partitions
2.6 Words
2.7 Labelled Trees
2.8 Notes and References
2.9 Exercises
3 Enumeration with Symmetries
3.1 Group Actions
3.2 Group Action on Functions
3.3 The Cycle-Index Polynomial
3.4 The Rotations of the Cube
3.5 The Number of Non-Isomorphic Graphs
3.6 General Version of Polya's Theorem
3.7 Notes and References
3.8 Exercises
4 Finite Geometries and Latin Squares
4.1 Systems of Distinct Representatives
4.2 Latin Squares
4.3 Mutually Orthogonal Latin Squares
4.4 Linear Spaces
4.5 Projective Planes
4.6 Affine Planes
4.7 Projective Spaces
4.8 Notes and References
4.9 Exercises
5 Matchings
5.1 König's Theorem
5.2 Hall's Marriage Theorem
5.3 Stable Matchings
5.4 Tutte's Theorem
5.5 Coverings and Independent Sets
5.6 Notes and References
5.7 Exercises
6 Connectivity
6.1 Vertex Connectivity
6.2 Structure of k-Connected Graphs for Small k
6.3 Menger's Theorem
6.4 Edge Connectivity
6.5 Notes and References
6.6 Exercises
7 Planarity
7.1 Plane Graphs
7.2 Kuratowski's Theorem
7.3 Wagner's Theorem
7.4 Whitney Theorem
7.5 Notes and References
7.6 Exercises
8 Graph Colouring
8.1 Vertex Colouring
8.2 Planar Graphs
8.3 Edge Colouring
8.4 List Colouring
8.5 Notes and References
8.6 Exercises
9 Extremal Graph Theory
9.1 Graphs Without Triangles
9.2 Graphs Without Complete Subgraphs
9.3 Erdős–Stone Theorem
9.4 Graphs Without Complete Bipartite Graphs
9.5 Graphs Without Even Cycles
9.6 Notes and References
9.7 Exercises
10 Hints and Solutions to Selected Exercises
References

✦ Subjects

Combinatorics; Graph Theory; Discrete Math; Enumerative Combinatorics; Polya Counting; Finite Geometries; Extremal Graph Theory