This undergraduate textbook is suitable for introductory classes in combinatorics and related topics.
The book covers a wide range of both pure and applied combinatorics, beginning with the very basics of enumeration and then going on to Latin squares, graphs and designs. The latter topic is closely related to finite geometry, which is developed in parallel. Applications to probability theory, algebra, coding theory, cryptology and combinatorial game theory comprise the later chapters. Throughout the book, examples and exercises illustrate the material, and the interrelations between the various topics is emphasized.
Readers looking to take first steps toward the study of combinatorics, finite geometry, design theory, coding theory, or cryptology will find this book valuable. Essentially self-contained, there are very few prerequisites aside from some mathematical maturity, and the little algebra required is covered in the text. The book is also a valuable resource for anyone interested in discrete mathematics as it ties together a wide variety of topics.
Author(s): Steven Dougherty
Series: Springer Undergraduate Mathematics Series
Edition: 1
Publisher: Springer
Year: 2020
Language: English
Pages: 369
Tags: Combinatorics, Latin Squares, Projective Plane, Graphs, Finite Geometries, Designs, Codes, Cryptology
Preface
Notations
Guide for Lecturers
Acknowledgements
Contents
1 Foundational Combinatorial Structures
1.1 Basic Counting
1.2 Multinomial Coefficients
1.3 Pigeonhole Principle
1.4 Permutations
1.4.1 Japanese Ladders
1.5 Generating Functions
1.5.1 Coin Counting
1.5.2 Fibonacci Sequence
2 Foundational Algebraic Structures
2.1 Modular Arithmetic
2.1.1 Euclidean Algorithm
2.1.2 Arithmetic Operations
2.1.3 Fermat's Little Theorem and Euler's Generalization
2.2 Finite Fields
2.3 Combinatorial Numbers
2.3.1 Geometric Numbers
2.3.2 Catalan Numbers
2.3.3 Stirling Numbers
2.3.4 Towers of Hanoi
3 Mutually Orthogonal Latin Squares
3.1 36 Officers and Latin Squares
3.2 Forming Latin Squares
3.3 Structure of Latin Squares
4 Affine and Projective Planes
4.1 Introduction
4.2 Definitions
4.3 Planes from Fields
4.4 Connection Between Affine Planes and MOLS
4.5 Fundamental Question
5 Graphs
5.1 Königsberg Bridge Problem
5.2 Simple Graphs
5.3 Colorings of Graphs
5.4 Directed Graphs and Relations
6 Higher Dimensional Finite Geometry
6.1 Linear Algebra
6.2 Affine Geometry
6.3 Projective Geometry
6.4 Desargues' Theorem
6.5 The Bruck–Ryser Theorem
6.6 Arcs and Ovals
6.7 Baer Subplanes
6.8 Translation Planes and Non-Desarguesian Planes
7 Designs
7.1 Designs
7.2 Biplanes
7.3 Symmetric Designs
7.4 Kirkman Schoolgirl Problem and Steiner Triple Systems
7.5 Nets and Transversal Designs
8 Combinatorial Objects
8.1 Introduction to Hadamard Matrices
8.2 Hadamard Designs
8.3 Generalized Hadamard Matrices
8.4 Latin Hypercubes
8.5 Partially Ordered Sets
8.6 Association Schemes
9 Discrete Probability—A Return to Counting
9.1 Definitions and Elementary Probability
9.2 Conditional Probability
10 Automorphism Groups
10.1 Groups
10.2 Automorphisms of a Design
10.3 Quasigroups
10.4 Difference Sets
11 Codes
11.1 Introduction
11.2 Basics of Coding Theory
11.3 Orthogonal Codes
11.4 Syndrome Decoding
11.5 The Binary Hamming Code and the Projective Plane of Order 2
11.6 Projective Geometry and Coding Theory
11.7 Sphere Packing Bound and Perfect Codes
11.8 MDS Codes
11.9 Weight Enumerators and the Assmus-Mattson Theorem
11.10 Codes of Planes
12 Cryptology
12.1 Substitution Ciphers
12.2 German Enigma Machine
12.3 Public-Key Cryptography
12.3.1 RSA Cryptosystem
12.3.2 El Gamal Cryptosystem
12.3.3 Diffie-Hellman Key Exchange
12.4 McEliece Cryptographic System
13 Games and Designs
13.1 The Game
13.2 Weight Functions
13.2.1 The Game on Planes
13.2.2 The Game on Biplanes
13.2.3 The Game on Symmetric Designs
13.2.4 The Game on Hadamard Designs
13.2.5 The Game on Nets
13.2.6 The Game on Steiner Triple Systems
14 Epilogue
Solutions to Selected Odd Problems
B.1 Problems of Chap.1摥映數爠eflinkcounting11
B.2 Problems of Chap.2摥映數爠eflinkalgebra22
B.3 Problems of Chap.3摥映數爠eflinksec233
B.4 Problems of Chap.4摥映數爠eflinksec344
B.5 Problems of Chap.5摥映數爠eflinkgraphschapter55
B.6 Problems of Chap.6摥映數爠eflinksec466
B.7 Problems of Chap.7摥映數爠eflinksec677
B.8 Problems of Chap.8摥映數爠eflinksec788
B.9 Problems of Chap.9摥映數爠eflinkProbabilityChapter99
B.10 Problems of Chap.10摥映數爠eflinksec81010
B.11 Problems of Chap.11摥映數爠eflinksec91111
B.12 Problems of Chap.12摥映數爠eflinkCryptology1212
B.13 Problems of Chap.13摥映數爠eflinkGames1313
Glossary
References
Index
