Surveys in combinatorics, 1997

Cover......Page 1
Title......Page 4
Copyright......Page 5
Contents......Page 6
Preface......Page 10
2 Definition of M_{13}......Page 16
3 The first few moves......Page 17
4 The hexads.......Page 19
5 The doublings of M_{13}......Page 20
6 The inner product......Page 23
7 The proofs......Page 24
8 Further comments......Page 25
References.......Page 26
1 Introduction......Page 28
2 Basic properties......Page 30
3 General bounds......Page 32
4 Special graphs......Page 35
5 Asymptotic results......Page 38
6 Trees......Page 41
7 Computational complexity......Page 46
8 Related topics......Page 49
9 Open problems......Page 53
References......Page 55
1 Introduction......Page 64
2 Formulating the problem for BDX.......Page 65
3 Towards a search.......Page 71
References.......Page 78
2 Partitions and quotients of permutation groups and graphs......Page 80
3 Primitive graph quotients......Page 82
4 Normal quotients of locally primitive and locally quasiprimitive graphs.......Page 85
5 Finite quasiprimitive permutation groups......Page 87
6 Finite quasiprimitive 2-arc transitive graphs......Page 91
7 Full automorphism groups of quasiprimitive graphs......Page 94
References.......Page 97
1 Introduction......Page 102
2 Graphs of bounded tree width......Page 120
3 Untangling tangles......Page 134
4 Excluding walls......Page 143
5 Graph minors revisited......Page 145
6 Packing and covering.......Page 151
7 Building a wall.......Page 160
References.......Page 173
1 Introduction......Page 178
2 Overview of ?G)......Page 179
3 Overview of A (G)......Page 181
4 Some basic facts on ?G).......Page 184
5 u(G) and A(G) for complete graphs.......Page 190
6 Clique sums.......Page 191
8 u(G) and A(G) for complete bipartite graphs.......Page 193
10 Van der Hoist's lemma......Page 194
12 Characterizing p(G) < 3......Page 196
13 Characterizing(G) < 3......Page 197
14 A Borsuk theorem for antipodal links......Page 201
15 Characterizing ?G) < 4......Page 202
16 Towards characterizing A(G) < 4......Page 204
17 An extension to oriented matroids......Page 206
18 The related graph invariant ic(G)......Page 207
References......Page 209
1 Introduction......Page 212
2 Weil's theorem and its variants.......Page 214
3 Applications of Weil's theorem in graph theory and combinatorics......Page 216
4 Applications of Weil's theorem in finite geometry......Page 222
5 The generalized Menelaus' theorem and applications: large arcs......Page 230
6 The Redei polynomial and applications: blocking sets and (k, n)- arcs......Page 235
References......Page 243
1 Introduction......Page 252
3 Classical representation theorems......Page 254
4 Dilworth's theorem for interval orders......Page 258
5 Linear extensions and dimension......Page 259
6 Linear extensions of interval orders......Page 260
7 Dimension of interval orders.......Page 261
8 Critical pairs and alternating cycles......Page 263
9 Interval orders and shift graphs......Page 264
10 Interval orders and overlap graphs......Page 267
11 Semi-orders and balancing pairs......Page 270
12 Interval orders and extremal problems......Page 272
13 Interval orders and hamiltonian paths......Page 274
14 On-line and un-cooperative coloring......Page 276
15 Fractional dimension and ramsey theory for probability spaces......Page 279
16 Higher-dimensional analogues for graphs......Page 281
17 Higher dimensional analogues for orders......Page 284
18 Intervals, angles and spheres......Page 286
19 Tolerances, thresholds and gaps......Page 287
References......Page 292
1 Introduction......Page 302
2 Counting to within a ratio......Page 304
3 Randomised approximation schemes......Page 306
4 Rapidly mixing Markov chains......Page 309
5 Computing in a convex body......Page 312
6 Partial orders......Page 315
7 Graph problems.......Page 317
8 Contingency tables......Page 323
9 Matroid problems......Page 324
10 Zonotopes......Page 328
References......Page 332
Author Index......Page 340
Subject Index......Page 346