Surveys in combinatorics 2007

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