This volume contains survey articles based on the invited lectures given at the Twenty-first British Combinatorial Conference, held in July 2007 at the University of Reading. This biennial conference is a well-established international event and the articles are of the high quality that befits the event. By its nature this volume provides an up-to-date overview of current research activity in several areas of combinatorics, ranging from graph theory to current applications of combinatorial mathematics, including efficient approximability of NP-hard optimization problems and cryptographic key management. The authors are some of the world's foremost researchers in their fields, and here they summarize existing results, and give a unique preview of work currently being written up. The book provides a valuable survey of the present state of knowledge in combinatorics. It will be useful to research workers and advanced graduate students, primarily in mathematics but also in computer science, statistics and engineering.
Author(s): Anthony Hilton, John Talbot
Series: London Mathematical Society Lecture Note Series
Edition: 1
Publisher: Cambridge University Press
Year: 2007
Language: English
Pages: 295
Cover......Page 1
London Mathematical Society Lecture Note Series 346......Page 2
Surveys in Combinatorics 2007......Page 4
9780521698238......Page 5
Contents......Page 6
Preface......Page 8
1 Introduction......Page 10
2 Hereditary and Monotone Properties......Page 12
3 Measures of Properties......Page 14
4 The Cover Inequality, the Box Theorem, and Large Hereditary Properties......Page 18
5 Hereditary Properties of Graphs......Page 21
6 Classifying Labelled Speeds......Page 25
7 Monotone Properties......Page 29
8 Unlabelled Speed......Page 30
9 Colouring Random Graphs with Hereditary Properties......Page 31
10 The Distance from a Hereditary Property......Page 33
11 Posets, Permutations, Ordered Hypergraphs, and Partitions......Page 34
12 Words......Page 39
References......Page 43
1 Introduction......Page 50
2 Bruhat order on A(R, S)......Page 51
3 Bruhat order on Z+(R, S)......Page 55
4 Ordering A(R, S) by shape of insertion tableau......Page 56
5 Bruhat order on symmetric matrices......Page 60
6 Ordering by spectral radius (index)......Page 62
7 Ordering by rank......Page 68
8 Higher-dimensional permutation arrays......Page 69
References......Page 72
1 Introduction......Page 76
2 Uniform length cycles......Page 79
3 Cycles of varying lengths......Page 89
References......Page 102
1 Introduction......Page 108
2 Perfect Graphs......Page 109
3 Claw-free Graphs......Page 112
4 Bull-free Graphs......Page 117
5 Trigraphs......Page 119
6 Even-hole-free Graphs......Page 121
7 Detecting Induced Subgraphs......Page 123
References......Page 126
1 Context......Page 130
2 Preliminaries......Page 131
3 Existence......Page 134
4 Growth estimates......Page 138
5 Orientable cyclic biembeddings......Page 144
6 Enumeration......Page 147
7 Trades......Page 150
8 Maximum genus embeddings......Page 155
9 Hamiltonian embeddings......Page 159
10 Latin squares......Page 164
11 Symmetric configurations......Page 170
12 Concluding remarks......Page 173
References......Page 177
1 Introduction......Page 184
2 Background......Page 185
3 The zeta function......Page 189
4 Equality in the Hasse–Weil bound......Page 190
5 Examples of maximal curves......Page 192
6 Theoretical background......Page 193
7 Some optimal curves......Page 195
8 The Frobenius linear series of a maximal curve......Page 197
9 Maximal curves of large genus......Page 198
10 Non-isomorphic maximal curves......Page 200
11 Singular plane curves......Page 202
12 Counting points on a plane curve......Page 205
References......Page 207
1 Introduction......Page 210
2 Efficient computation......Page 212
3 Maximal constraint satisfaction problems......Page 213
4 Approximation algorithms......Page 214
5 Constraints on two variables......Page 216
6 Some approximation resistant predicates......Page 219
7 Proof systems......Page 220
8 Constraints on three Boolean variables......Page 223
9 Max-CSP on Boolean variables of higher width......Page 225
11 Conclusions and open problem......Page 227
References......Page 228
1 Introduction......Page 232
2 Cryptographic key management......Page 233
3 Key establishment framework......Page 235
4 Preliminaries......Page 239
5 Key predistribution schemes......Page 241
6 Group key distribution schemes......Page 255
7 Group key agreement schemes......Page 265
8 Concluding remarks......Page 275
References......Page 276
1 Introduction......Page 284
2 Faithful branch-decompositions......Page 286
3 Connected branch-decompositions......Page 287
4 The partition Lemma......Page 291
References......Page 294
