Atnaujinkite slapukų nuostatas

ErdõsKoRado Theorems: Algebraic Approaches [Kietas viršelis]

5.00/5 (2 ratings by Goodreads)
(University of Regina, Saskatchewan, Canada), (University of Waterloo, Ontario)
  • Formatas: Hardback, 350 pages, aukštis x plotis x storis: 235x158x23 mm, weight: 620 g, Worked examples or Exercises; 5 Line drawings, unspecified
  • Serija: Cambridge Studies in Advanced Mathematics
  • Išleidimo metai: 24-Nov-2015
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1107128447
  • ISBN-13: 9781107128446
Kitos knygos pagal šią temą:
ErdõsKoRado Theorems: Algebraic ApproachesDidesnis paveikslėlis
  • Formatas: Hardback, 350 pages, aukštis x plotis x storis: 235x158x23 mm, weight: 620 g, Worked examples or Exercises; 5 Line drawings, unspecified
  • Serija: Cambridge Studies in Advanced Mathematics
  • Išleidimo metai: 24-Nov-2015
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1107128447
  • ISBN-13: 9781107128446
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9781107128446.html
Raktažodžiai:
The Erdos–Ko–Rado Theorem is a fundamental result in combinatorics. Aimed at graduate students and researchers, this comprehensive text shows how tools from algebraic graph theory can be applied to prove the EKR Theorem and its generalizations. Readers can test their understanding at every step with the end-of-chapter exercises.

Aimed at graduate students and researchers, this fascinating text provides a comprehensive study of the Erdos–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.

Recenzijos

'This is an excellent book about Erdos-Ko-Rado (EKR) Theorems and how to prove them by algebraic methods The writing style is reader-friendly, and proofs are well organized and easily followed. Also, every chapter contains Exercises and Notes, which are very useful for expanding understanding and finding further reading. The reviewer recommends this book without hesitation to all graduate students and researchers interested in combinatorics.' Norihide Tokushige, MathSciNet

Daugiau informacijos

Graduate text focusing on algebraic methods that can be applied to prove the ErdsKoRado Theorem and its generalizations.
Preface xiii
1 The Erdos-Ko-Rado Theorem 1(23)
1.1 The original proof
2(4)
1.2 Non-canonical intersecting set systems
6(1)
1.3 The complete Erdos-Ko-Rado Theorem
7(3)
1.4 The shifting technique
10(1)
1.5 The Kruskal-Katona Theorem
11(4)
1.6 The Hilton-Milner Theorem
15(2)
1.7 Cross-intersecting sets
17(2)
1.8 Separated sets
19(2)
1.9 Exercises
21(3)
2 Bounds on cocliques 24(25)
2.1 A clique-coclique bound
24(3)
2.2 Equitable partitions
27(2)
2.3 Interlacing
29(1)
2.4 The ratio bound for cocliques
30(3)
2.5 Application: Erdos-Ko-Rado
33(2)
2.6 A ratio bound for cliques
35(1)
2.7 Ratio bound for cross cocliques
36(2)
2.8 Cocliques in neighborhoods
38(1)
2.9 The inertia bound
39(1)
2.10 Inertia bound: Kneser graphs
40(1)
2.11 Inertia bound: folded cubes
40(1)
2.12 Fractional chromatic number
41(2)
2.13 Homomorphisms
43(1)
2.14 Cyclic intervals
44(1)
2.15 Exercises
45(4)
3 Association schemes 49(21)
3.1 Definitions
50(1)
3.2 Commutants
51(1)
3.3 The conjugacy class scheme
52(2)
3.4 A basis of idempotents
54(4)
3.5 Some fundamental identities
58(2)
3.6 An example
60(2)
3.7 The clique bound
62(2)
3.8 The clique-coclique bound
64(4)
3.9 Exercises
68(2)
4 Distance-regular graphs 70(17)
4.1 Metric schemes
71(2)
4.2 A three-term recurrence
73(1)
4.3 Cometric schemes
74(2)
4.4 Intersection numbers and Krein parameters
76(1)
4.5 Coding theory
77(2)
4.6 Sturm sequences
79(4)
4.7 Classical parameters
83(1)
4.8 Exercises
84(3)
5 Strongly regular graphs 87(25)
5.1 An association scheme
87(1)
5.2 Eigenvalues
88(2)
5.3 Designs
90(4)
5.4 The Witt graph
94(2)
5.5 Orthogonal arrays
96(4)
5.6 Partial geometries
100(3)
5.7 Eigenspaces of point and line graphs
103(2)
5.8 Paley graphs
105(2)
5.9 Paley graphs of square order
107(1)
5.10 Exercises
108(4)
6 The Johnson scheme 112(14)
6.1 Graphs in the Johnson scheme
112(2)
6.2 A third basis
114(2)
6.3 Eigenvalues of the Johnson graph
116(2)
6.4 A fourth basis
118(2)
6.5 Eigenvalues of the Johnson scheme
120(2)
6.6 Kneser graphs
122(1)
6.7 Exercises
123(3)
7 Polytopes 126(9)
7.1 Convex polytopes
126(2)
7.2 A polytope from the Johnson graph
128(1)
7.3 Perfect matching polytopes
129(2)
7.4 Perfect matchings in complete graphs
131(2)
7.5 Perfect matchings in complete bipartite graphs
133(1)
7.6 Exercises
133(2)
8 The exact bound in the EKR Theorem 135(26)
8.1 A certificate for maximality
135(4)
8.2 Special cases
139(1)
8.3 The EKR bound for 2-intersecting sets
140(2)
8.4 Wilson's matrix
142(2)
8.5 Eigenvalues of Wilson's matrix
144(4)
8.6 Width and dual width
148(2)
8.7 Equality in the width bound
150(1)
8.8 Intersecting families of maximum size
151(2)
8.9 Equality in the dual width bound
153(4)
8.10 Narrow subsets
157(2)
8.11 Exercises
159(2)
9 The Grassmann scheme 161(23)
9.1 q-Binomial coefficients
162(1)
9.2 q-Commuting variables
162(2)
9.3 Counting subspaces
164(3)
9.4 Subspace incidence matrices
167(2)
9.5 Another basis
169(1)
9.6 Eigenvalues of the Grassmann scheme
170(2)
9.7 The EKR bound for q-Kneser graphs
172(1)
9.8 Cocliques in the q-Kneser graphs
173(2)
9.9 t-Intersecting families
175(1)
9.10 The certifying matrix
176(4)
9.11 Bilinear forms graphs
180(1)
9.12 Dual polar graphs
181(1)
9.13 Exercises
182(2)
10 The Hamming scheme 184(26)
10.1 Eigenvalues of the Hamming scheme
185(2)
10.2 Idempotents
187(2)
10.3 Partial words
189(2)
10.4 The EKR Theorem for words
191(2)
10.5 The complete EKR for words
193(1)
10.6 Cross-intersecting sets of words
194(1)
10.7 An operation on words
195(1)
10.8 Bounds on the size of a derived set
196(4)
10.9 Cocliques in power graphs
200(3)
10.10 Cocliques in product graphs
203(5)
10.11 Exercises
208(2)
11 Representation theory 210(22)
11.1 Representations
210(1)
11.2 The group algebra
211(1)
11.3 Operations on representations
212(2)
11.4 Sums and idempotents
214(1)
11.5 Irreducible representations
215(2)
11.6 Schur's Lemma
217(1)
11.7 Coordinate functions
218(2)
11.8 Characters
220(1)
11.9 Orthogonality of characters
221(2)
11.10 Decomposing the regular representation
223(2)
11.11 The conjugacy class scheme: idempotents
225(1)
11.12 The conjugacy class scheme: eigenvalues
226(2)
11.13 Restriction and induction
228(2)
11.14 Exercises
230(2)
12 Representation theory of the symmetric group 232(13)
12.1 Permutation representations
232(1)
12.2 Examples: orbit counting
233(2)
12.3 Young subgroups
235(1)
12.4 Irreducible representations
235(2)
12.5 Kostka numbers
237(1)
12.6 Hook length formula
238(1)
12.7 Branching rule
239(3)
12.8 Wreath products
242(1)
12.9 Exercises
243(2)
13 Orbitals 245(15)
13.1 Arc-transitive directed graphs
245(2)
13.2 Commutants of permutation groups
247(1)
13.3 Generously transitive groups
248(1)
13.4 Multiplicity-free representations
249(1)
13.5 Multiplicity-free representations of the symmetric group
250(1)
13.6 An equitable partition
251(2)
13.7 A homomorphism
253(1)
13.8 Eigenvalues of the orbital scheme
254(2)
13.9 Eigenspaces and Young subgroups
256(2)
13.10 Exercises
258(2)
14 Permutations 260(19)
14.1 The derangement graph
261(1)
14.2 Eigenvalues of the derangement graph
262(2)
14.3 An eigenspace of the derangement graph
264(2)
14.4 Cocliques in the derangement graphs
266(2)
14.5 t-Intersecting permutations
268(1)
14.6 Transitive permutation groups
269(2)
14.7 2-Transitive subgroups
271(4)
14.8 Direct products
275(1)
14.9 Exercises
276(3)
15 Partitions 279(29)
15.1 Intersecting partitions
280(2)
15.2 Perfect matchings
282(2)
15.3 Eigenvalues of the perfect matching graph
284(1)
15.4 The perfect matching association scheme
285(1)
15.5 Modules of the perfect matching graph
286(3)
15.6 EKR Theorem for perfect matchings
289(1)
15.7 Skew partitions
289(2)
15.8 Cliques and cocliques in the skew-partition graph
291(2)
15.9 Eigenvalues of the skew-partition graph
293(2)
15.10 Eigenspaces of the skew-partition graph
295(3)
15.11 3 x 3 partitions
298(1)
15.12 Inner distributions of cliques
299(2)
15.13 Characterizing cocliques
301(1)
15.14 Meet tables
302(3)
15.15 Exercises
305(3)
16 Open problems 308(13)
16.1 Generalize the ratio bound for cliques
308(1)
16.2 Extend the Katona cycle proof
309(1)
16.3 Prove the EKR Theorem for the block graph of a design
310(1)
16.4 Prove the EKR Theorem for the orthogonal array graph
311(1)
16.5 Find an algebraic proof of the EKR Theorem for the Paley graphs
311(1)
16.6 Determine the chromatic number of the Johnson graphs
312(1)
16.7 Prove the EKR Theorem for 2-transitive groups
313(1)
16.8 Determine cocliques in groups that do not have the EKR property
314(1)
16.9 Prove the EKR property holds for other group actions
315(1)
16.10 Calculate the eigenvalues of the perfect matching scheme
315(1)
16.11 Prove the EKR Theorem for partitions
316(1)
16.12 Prove EKR Theorems for other objects
317(1)
16.13 Find maximal cocliques in graphs from an orbital scheme
318(1)
16.14 Develop other compression operations
319(2)
Glossary: Symbols 321(2)
Glossary: Operations and relations 323(1)
References 324(8)
Index 332
Christopher Godsil is a professor in the Combinatorics and Optimization Department at the University of Waterloo, Ontario. He authored (with Gordon Royle) the popular textbook Algebraic Graph Theory. He started the Journal of Algebraic Combinatorics in 1992 and he serves on the editorial board of a number of other journals, including the Australasian Journal of Combinatorics and the Electronic Journal of Combinatorics. Karen Meagher is an associate professor in the Department of Mathematics and Statistics at the University of Regina, Saskatchewan, Canada. Her research area is graph theory and discrete mathematics in which she has published around 25 journal articles.