Kooperativer Bibliotheksverbund

UID:

Format: 1 online resource (xvi, 335 pages) : , digital, PDF file(s).

ISBN: 1-316-46154-8 , 1-316-46427-X , 1-316-41495-7

Series Statement: Cambridge studies in advanced mathematics ; 149

Content: Aimed at graduate students and researchers, this fascinating text provides a comprehensive study of the Erdős-Ko-Rado Theorem, with a focus on algebraic methods. The authors begin by discussing well-known proofs of the EKR bound for intersecting families. The natural generalization of the EKR Theorem holds for many different objects that have a notion of intersection, and the bulk of this book focuses on algebraic proofs that can be applied to these different objects. The authors introduce tools commonly used in algebraic graph theory and show how these can be used to prove versions of the EKR Theorem. Topics include association schemes, strongly regular graphs, the Johnson scheme, the Hamming scheme and the Grassmann scheme. Readers can expand their understanding at every step with the 170 end-of-chapter exercises. The final chapter discusses in detail 15 open problems, each of which would make an interesting research project.

Note: Title from publisher's bibliographic system (viewed on 10 Dec 2015). , Cover -- Half title -- Series -- Title -- Copyright -- Dedication -- Contents -- Preface -- 1 The Erdős-Ko-Rado Theorem -- 1.1 The original proof -- 1.2 Non-canonical intersecting set systems -- 1.3 The complete Erdős-Ko-Rado Theorem -- 1.4 The shifting technique -- 1.5 The Kruskal-Katona Theorem -- 1.6 The Hilton-Milner Theorem -- 1.7 Cross-intersecting sets -- 1.8 Separated sets -- 1.9 Exercises -- 2 Bounds on cocliques -- 2.1 A clique-coclique bound -- 2.2 Equitable partitions -- 2.3 Interlacing -- 2.4 The ratio bound for cocliques -- 2.5 Application: Erdős-Ko-Rado -- 2.6 A ratio bound for cliques -- 2.7 Ratio bound for cross cocliques -- 2.8 Cocliques in neighborhoods -- 2.9 The inertia bound -- 2.10 Inertia bound: Kneser graphs -- 2.11 Inertia bound: folded cubes -- 2.12 Fractional chromatic number -- 2.13 Homomorphisms -- 2.14 Cyclic intervals -- 2.15 Exercises -- 3 Association schemes -- 3.1 Definitions -- 3.2 Commutants -- 3.3 The conjugacy class scheme -- 3.4 A basis of idempotents -- 3.5 Some fundamental identities -- 3.6 An example -- 3.7 The clique bound -- 3.8 The clique-coclique bound -- 3.9 Exercises -- 4 Distance-regular graphs -- 4.1 Metric schemes -- 4.2 A three-term recurrence -- 4.3 Cometric schemes -- 4.4 Intersection numbers and Krein parameters -- 4.5 Coding theory -- 4.6 Sturm sequences -- 4.7 Classical parameters -- 4.8 Exercises -- 5 Strongly regular graphs -- 5.1 An association scheme -- 5.2 Eigenvalues -- 5.3 Designs -- 5.4 The Witt graph -- 5.5 Orthogonal arrays -- 5.6 Partial geometries -- 5.7 Eigenspaces of point and line graphs -- 5.8 Paley graphs -- 5.9 Paley graphs of square order -- 5.10 Exercises -- 6 The Johnson scheme -- 6.1 Graphs in the Johnson scheme -- 6.2 A third basis -- 6.3 Eigenvalues of the Johnson graph -- 6.4 A fourth basis -- 6.5 Eigenvalues of the Johnson scheme -- 6.6 Kneser graphs. , 6.7 Exercises -- 7 Polytopes -- 7.1 Convex polytopes -- 7.2 A polytope from the Johnson graph -- 7.3 Perfect matching polytopes -- 7.4 Perfect matchings in complete graphs -- 7.5 Perfect matchings in complete bipartite graphs -- 7.6 Exercises -- 8 The exact bound in the EKR Theorem -- 8.1 A certificate for maximality -- 8.2 Special cases -- 8.3 The EKR bound for 2-intersecting sets -- 8.4 Wilson's matrix -- 8.5 Eigenvalues of Wilson's matrix -- 8.6 Width and dual width -- 8.7 Equality in the width bound -- 8.8 Intersecting families of maximum size -- 8.9 Equality in the dual width bound -- 8.10 Narrow subsets -- 8.11 Exercises -- 9 The Grassmann scheme -- 9.1 q-Binomial coefficients -- 9.2 q-Commuting variables -- 9.3 Counting subspaces -- 9.4 Subspace incidence matrices -- 9.5 Another basis -- 9.6 Eigenvalues of the Grassmann scheme -- 9.7 The EKR bound for q-Kneser graphs -- 9.8 Cocliques in the q-Kneser graphs -- 9.9 t-Intersecting families -- 9.10 The certifying matrix -- 9.11 Bilinear forms graphs -- 9.12 Dual polar graphs -- 9.13 Exercises -- 10 The Hamming scheme -- 10.1 Eigenvalues of the Hamming scheme -- 10.2 Idempotents -- 10.3 Partial words -- 10.4 The EKR Theorem for words -- 10.5 The complete EKR for words -- 10.6 Cross-intersecting sets of words -- 10.7 An operation on words -- 10.8 Bounds on the size of a derived set -- 10.9 Cocliques in power graphs -- 10.10 Cocliques in product graphs -- 10.11 Notes -- 11 Representation theory -- 11.1 Representations -- 11.2 The group algebra -- 11.3 Operations on representations -- 11.4 Sums and idempotents -- 11.5 Irreducible representations -- 11.6 Schur's Lemma -- 11.7 Coordinate functions -- 11.8 Characters -- 11.9 Orthogonality of characters -- 11.10 Decomposing the regular representation -- 11.11 The conjugacy class scheme: idempotents -- 11.12 The conjugacy class scheme: eigenvalues. , 11.13 Restriction and induction -- 11.14 Exercises -- 12 Representation theory of the symmetric group -- 12.1 Permutation representations -- 12.2 Examples: orbit counting -- 12.3 Young subgroups -- 12.4 Irreducible representations -- 12.5 Kostka numbers -- 12.6 Hook length formula -- 12.7 Branching rule -- 12.8 Wreath products -- 12.9 Exercises -- 13 Orbitals -- 13.1 Arc-transitive directed graphs -- 13.2 Commutants of permutation groups -- 13.3 Generously transitive groups -- 13.4 Multiplicity-free representations -- 13.5 Multiplicity-free representations of the symmetric group -- 13.6 An equitable partition -- 13.7 A homomorphism -- 13.8 Eigenvalues of the orbital scheme -- 13.9 Eigenspaces and Young subgroups -- 13.10 Exercises -- 14 Permutations -- 14.1 The derangement graph -- 14.2 Eigenvalues of the derangement graph -- 14.3 An eigenspace of the derangement graph -- 14.4 Cocliques in the derangement graphs -- 14.5 t-Intersecting permutations -- 14.6 Transitive permutation groups -- 14.7 2-Transitive subgroups -- 14.8 Direct products -- 14.9 Exercises -- 15 Partitions -- 15.1 Intersecting partitions -- 15.2 Perfect matchings -- 15.3 Eigenvalues of the perfect matching graph -- 15.4 The perfect matching association scheme -- 15.5 Modules of the perfect matching graph -- 15.6 EKR Theorem for perfect matchings -- 15.7 Skew partitions -- 15.8 Cliques and cocliques in the skew-partition graph -- 15.9 Eigenvalues of the skew-partition graph -- 15.10 Eigenspaces of the skew-partition graph -- 15.11 3 × 3 partitions -- 15.12 Inner distributions of cliques -- 15.13 Characterizing cocliques -- 15.14 Meet tables -- 15.15 Exercises -- 16 Open problems -- 16.1 Generalize the ratio bound for cliques -- 16.2 Extend the Katona cycle proof -- 16.3 Prove the EKR Theorem for the block graph of a design -- 16.4 Prove the EKR Theorem for the orthogonal array graph. , 16.5 Find an algebraic proof of the EKR Theorem for the Paley graphs -- 16.6 Determine the chromatic number of the Johnson graphs -- 16.7 Prove the EKR Theorem for 2-transitive groups -- 16.8 Determine cocliques in groups that do not have the EKR property -- 16.9 Prove the EKR property holds for other group actions -- 16.10 Calculate the eigenvalues of the perfect matching scheme -- 16.11 Prove the EKR Theorem for partitions -- 16.12 Prove EKR Theorems for other objects -- 16.13 Find maximal cocliques in graphs from an orbital scheme -- 16.14 Develop other compression operations -- Glossary: Symbols -- Glossary: Operations and relations -- References -- Index.

Additional Edition: ISBN 1-107-12844-7

Language: English

URL: https://doi.org/10.1017/CBO9781316414958