Limit search to available items
Book Cover
E-book
Author Godsil, Chris, author

Title Algebraic Combinatorics
Edition First edition
Published Boca Raton, FL : CRC Press, 2017
Online access available from:
ProQuest Ebook Central    View Resource Record  

Copies

Description 1 online resource : text file, PDF
Contents Preface -- Contents -- 1 The Matchings Polynomial -- 1.1 Recurrences -- 1.2 Integrals -- 1.3 Rook Polynomials -- 1.4 The Hit Polynomial -- 1.5 Stirling and Euler Numbers -- 1.6 Hit Polynomials and Integrals -- Exercises -- Notes and References -- 2 The Characteristic Polynomial -- 2.1 Coefficients and Recurrences -- 2.2 Walks and the Characteristic Polynomial -- 2.3 Eigenvectors -- 2.4 Regular Graphs -- 2.5 The Spectral Decomposition -- 2.6 Some Further Matrix Theory -- Exercises -- Notes and References -- 3 Formal Power Series and Generating Functions -- 3.1 Formal Power Series -- 3.2 Limits -- 3.3 Operations on Power Series -- 3.4 Exp and Log -- 3.5 Non-linear Equations -- 3.6 Applications and Examples -- Exercises -- Notes and References -- 4 Walk Generating Functions -- 4.1 Jacobi’s Theorem -- 4.2 Walks and Paths -- 4.3 A Decomposition Formula -- 4.4 The Christoffel-Darboux Identity -- 4.5 Vertex Reconstruction -- 4.6 Cospectral Graphs -- 4.7 Random Walks on Graphs -- Exercises -- Notes and References -- 5 Quotients of Graphs -- 5.1 Equitable Partitions -- 5.2 Eigenvalues and Eigenvectors -- 5.3 Walk-Regular Graphs -- 5.4 Generalised Interlacing -- 5.5 Covers -- 5.6 The Spectral Radius of a TYee -- Exercises -- Notes and References -- 6 Matchings and Walks -- 6.1 The Path-Tree -- 6.2 Tree-Like Walks -- 6.3 Consequences of Reality -- 6.4 Christoffel-Darboux Identities -- Exercises -- Notes and References -- 7 Pfaffians -- 7.1 The Pfaffian of a Skew Symmetric Matrix -- 7.2 Pfaffians and Determinants -- 7.3 Row Expansions -- 7.4 Oriented Graphs -- 7.5 Orientations -- 7.6 The Difficulty of Counting Perfect Matchings -- Exercises -- Notes and References -- 8 Orthogonal Polynomials -- 8.1 The Definitions -- 8.2 The Three-Term Recurrence -- 8.3 The Christoffel-Darboux Formula -- 8.4 Discrete Orthogonality -- 8.5 Sturm Sequences -- 8.6 Some Examples -- Exercises -- Notes and References -- 9 Moment Sequences -- 9.1 Moments and Walks -- 9.2 Moment Generating Functions -- 9.3 Hermite and Laguerre Polynomials -- 9.4 The Chebyshev Polynomials -- 9.5 The Charlier Polynomials -- 9.7 Sheffer Sequences of Polynomials -- 9.7 Characterising Polynomials of Meixner Type -- 9.8 The Polynomials of Meixner Type -- Exercises -- Notes and References -- 10 Strongly Regular Graphs -- 10.1 Basic Theory -- 10.2 Conference Graphs -- 10.3 Designs -- 10.4 Orthogonal Arrays -- Exercises -- Notes and References -- 11 Distance-Regular Graphs -- 11.1 Some Families -- 11.2 Distance Matrices -- 11.3 Parameters -- 11.4 Quotients -- 11.5 Imprimitive Distance-Regular Graphs -- 11.6 Codes -- 11.7 Completely Regular Subsets -- 11.8 Examples -- Exercises -- Notes and References -- 12 Association Schemes -- 12.1 Generously Transitive Permutation Groups -- 12.2 p’8 and q's -- 12.3 P- and Q-Polynomial Association Schemes -- 12.4 Products -- 12.5 Primitivity and Imprimitivity -- 12.6 Codes and Anticodes -- 12.7 Equitable Partitions of Matrices -- 12.8 Characters of Abelian Groups -- 12.9 Cayley Graphs -- 12.10 Translation Schemes and Duality -- Exercises -- Notes and References -- 13 Representations of Distance-Regular Graphs -- 13.1 Representations of Graphs -- 13.2 The Sequence of Cosines -- 13.3 Injectivity -- 13.4 Eigenvalue Multiplicities -- 13.5 Bounding the Diameter -- 13.6 Spherical Designs -- 13.7 Bounds for Cliques -- 13.8 Feasible Automorphisms -- Exercises -- Notes and References -- 14 Polynomial Spaces -- 14.1 Functions -- 14.2 The Axioms -- 14.3 Examples -- 14.4 The Degree of a Subset -- 14.5 Designs -- 14.6 The Johnson Scheme -- 14.7 The Hamming Scheme -- 14.8 Coding Theory -- 14.9 Group-Invariant Designs -- 14.10 Weighted Designs -- Exercises -- Notes and References -- 15 Q- Polynomial Spaces -- 15.1 Zonal Orthogonal Polynomials -- 15.2 Zonal Orthogonal Polynomials: Examples -- 15.3 The Addition Rule -- 15.4 Spherical Polynomial Spaces -- 15.5 Harmonic Polynomials -- 15.6 Association Schemes -- 15.7 Q-Polynomial Association Schemes -- 15.8 Incidence Matrices for Subsets -- 15.9 J(y, k) is Q-Polynomial -- Exercises -- Notes and References -- 16 Tight Designs -- 16.1 Tight Bounds -- 16.2 Examples and Non-Examples -- 16.3 The Grassman Space -- 16.4 Linear Programming -- 16.5 Bigger Bounds -- 16.6 Examples -- Exercises -- Notes and References -- Appendix: Terminology -- Index of Symbols -- Index
Summary "This graduate level text is distinguished both by the range of topics and the novelty of the material it treats--more than half of the material in it has previously only appeared in research papers. The first half of this book introduces the characteristic and matchings polynomials of a graph. It is instructive to consider these polynomials together because they have a number of properties in common. The matchings polynomial has links with a number of problems in combinatorial enumeration, particularly some of the current work on the combinatorics of orthogonal polynomials. This connection is discussed at some length, and is also in part the stimulus for the inclusion of chapters on orthogonal polynomials and formal power series. Many of the properties of orthogonal polynomials are derived from properties of characteristic polynomials. The second half of the book introduces the theory of polynomial spaces, which provide easy access to a number of important results in design theory, coding theory and the theory of association schemes. This book should be of interest to second year graduate text/reference in mathematics."--Provided by publisher
Form Electronic book
ISBN 1351467514
9781351467513