The Unity of Combinatorics

Description

Combinatorics, or the art and science of counting, is a vibrant and active area of pure mathematical research with many applications. The Unity of Combinatorics succeeds in showing that the many facets of combinatorics are not merely isolated instances of clever tricks but that they have numerous connections and threads weaving them together to form a beautifully patterned tapestry of ideas. Topics include combinatorial designs, combinatorial games, matroids, difference sets, Fibonacci numbers, finite geometries, Pascal's triangle, Penrose tilings, error-correcting codes, and many others. Anyone with an interest in mathematics, professional or recreational, will be sure to find this book both enlightening and enjoyable. Few mathematicians have been as active in this area as Richard Guy, now in his eighth decade of mathematical productivity. Guy is the author of over 300 papers and twelve books in geometry, number theory, graph theory, and combinatorics. In addition to being a life-long number-theorist and combinatorialist, Guy's co-author, Ezra Brown, is a multi-award-winning expository writer. Together, Guy and Brown have produced a book that, in the spirit of the founding words of the Carus book series, is accessible not only to mathematicians but to scientific workers and others with a modest mathematical background. Cover Title page Copyright Contents Preface Credits and Permissions Introduction Chapter 1. Blocks, sequences, bow ties, and worms 1.1. Langford sequences 1.2. Partitioning sets of integers 1.3. Penrose tilings Chapter 2. Combinatorial games 2.1. Wythoff’s game 2.2. Combinatorial games: rules and examples 2.3. Developing strategies: * P-positions and N-positions 2.4. Nim, nimbers, * and the Sprague–Grundy Theorem 2.5. Nim arithmetic and Nim algebra Chapter 3. Fibonacci, Pascal, and Catalan 3.1. Fibonacci numbers 3.2. The triangle of Pingala, Al Karaji, * Yang Hui, and Pascal 3.3. The Catalan numbers and * the central column of Pascal’s triangle Chapter 4. Catwalks, Sandsteps, and Pascal pyramids Chapter 5. Unique rook circuits Appendix Chapter 6. Sums, colorings, squared squares, and packings 6.1. Triples satisfying 𝑥+𝑦=𝑧 6.2. Coil diagrams * and the Ringel–Youngs Theorem 6.3. Squaring the square 6.4. Euler’s polyhedral formula 6.5. Packings and coverings * of the complete graph 6.6. Steiner triple systems Chapter 7. Difference sets and combinatorial designs 7.1. Difference sets 7.2. Multipliers 7.3. Difference sets, de Bruijn cycles, * and de Bruijn graphs 7.4. Block designs Chapter 8. Geometric connections 8.1. A quick tour of projective geometry 8.2. Finite projective geometries * and Singer designs 8.3. Examples: 𝑛=2, 𝑞=2 and 3 8.4. Affine planes and magic squares 8.5. Heawood’s map on the torus revisited 8.6. Ù and Nim 8.7. The automorphism group * of the Fano plane Chapter 9. The groups 𝑃𝑆𝐿(2,7) and 𝐺𝐿(3,2) and why they are isomorphic 9.1. The group 𝐺𝐿(3,2) 9.2. The group 𝑃𝑆𝐿(2,7) 9.3. Constructing an isomorphism of 𝑃𝑆𝐿(2,7) onto 𝐺𝐿(3,2) Chapter 10. Incidence matrices, codes, and sphere packings 10.1. Introducing incidence matrices 10.2. Error-correcting codes 10.3. Sphere packing 10.4. Hadamard matrices * and Hadamard difference sets 10.5. Hadamard matrices * and projective geometries Chapter 11. Kirkman’s schoolgirls, fields, spreads, and hats 11.1. Kirkman’s Schoolgirls Problem 11.2. Fifteen young ladies at school 11.3. Resolvable block designs * and Kirkman triple systems 11.4. Kirkman’s schoolgirls and difference sets 11.5. 𝐾=Rats (√2,√3,√5,√7) * and the designs it contains 11.6. Spreads in 𝑃𝐺(3,zF ₂) * and the geometry of Kirkman 11.7. Fifteen schoolgirls, fifteen hats, * and coding theory 11.8. Questions Chapter 12. (7,3,1) and combinatorics 12.1. Ù and the Heawood graph 12.2. Ù and Latin squares 12.3. Ù and round-robin tournaments Chapter 13. (7,3,1) and normed algebras 13.1. Sums of squares 13.2. The quaternions and the octonions 13.3. Beyond the octonions Chapter 14. (7,3,1) and matroids 14.1. Why matroids? 14.2. Declaration of (in)dependence 14.3. Thus, matroids 14.4. Matroids and greed Chapter 15. Coin-turning games and Mock Turtles 15.1. A review * of some combinatorial game theory 15.2. Turning Turtles 15.3. Turning Corners: coins on a grid 15.4. Mock Turtles: more turtles in a line 15.5. More about turtle-turning games Chapter 16. The (11,5,2) biplane, codes, designs, and groups 16.1. “How do you make math * exciting for students?” 16.2. Difference sets, block designs, * and biplanes 16.3. The automorphism group of the biplane 16.4. Incidence matrices, revisited 16.5. Error-correcting codes 16.6. Steiner systems 16.7. Automorphisms, transitivity, * simplicity, and the Mathieu groups Chapter 17. Rick’s Tricky Six Puzzle: More than meets the eye 17.1. Sliding-block puzzles 17.2. What is the exception? 17.3. Not much of a puzzle? 17.4. What is the automorphism group * of the Tricky Six Puzzle? 17.5. Two different group actions 17.6. The projective plane of order 4 17.7. Buy one, get several free! 17.8. The Hoffman–Singleton graph 17.9. The Steiner system 𝑆(5,6,12) 17.10. A (12,132,4) binary code * and Golay’s ternary code 𝒢₁₂ 17.11. Conclusions Chapter 18. 𝑆(5,8,24) Chapter 19. The Miracle Octad Generator 19.1. The Miracle Octad Generator (MOG) 19.2. An elementary approach 19.3. A more mathematical approach Bibliography Index Copyright Back Cover