The British Combinatorial Conference is one of the most well known meetings for combinatorialists. This volume collects the invited talks from the 1999 conference held at the University of Kent and together these span a broad range of combinatorial topics. The nine talks are from: S. Ball, J. Dinitz, M. Dyer, K. Metsch, J. Pach, R. Thomas, C. Thomassen, N. Wormald, plus a special contribution from W. T. Tutte. All researchers into combinatorics will find this volume an outstanding and up-to-date resource.

The Rado lecture

1

(14)

The Coming of the Matroids

3

(12)

W.T. Tutte

Appendix I: geometrical terminology

11

(2)

Appendix II: binary and regular matroids

13

(2)

The Invited Lectures

15

(272)

Polynomials in Finite Geometries

17

(20)

S. Ball

Introduction

17

(1)

Definitions and useful polynomials

18

(3)

Nuclei

21

(2)

Affine blocking sets

23

(2)

Non-Desarguesian planes

25

(2)

Maximal arcs

27

(3)

Unitals

30

(7)

Applications of Combinatorial Designs to Communications, Cryptography, and Networking

37

(64)

C. J. Colbourn

J. H. Dinitz

D. R. Stinson

Background

38

(1)

Optical orthogonal codes

39

(4)

Synchronous multiple access to channels

43

(2)

Group testing and superimposed codes

45

(3)

Erasure codes and information dispersal

48

(6)

Threshold and ramp schemes

54

(5)

Authentication codes

59

(3)

Resilient and correlation-immune functions

62

(3)

Multidrop networks

65

(3)

Channel graphs and interconnection networks

68

(4)

Partial match queries on files

72

(4)

Software testing

76

(2)

Disk layout and striping

78

(2)

(t, m, s)-nets and numerical integration

80

(7)

About things not said

87

(14)

Random Walks on Combinatorial Objects

101

(36)

Martin Dyer

Catherine Greenhill

Introduction

101

(1)

Notation and preliminaries

102

(1)

A computational framework

102

(7)

Review

109

(5)

Coupling

114

(2)

Path coupling

116

(4)

Perfect sampling

120

(8)

Negative results

128

(9)

Bose-Burton Type Theorems for Finite Projective, Affine and Polar Spaces

137

(30)

Klaus Metsch

Introduction

137

(2)

Blocking configurations for projective spaces

139

(3)

Variations of the Bose-Burton result in projective spaces

142

(2)

Spreads and partial spreads in PG(d,q)

144

(2)

A result in affine spaces

146

(1)

Ovoids and Spreads of finite classical polar spaces

146

(4)

Blocking lines by points in the polar spaces Q+(2n + 1, q), U(2n + 1,q) and Q(2n,q)

150

(5)

The unitary polar spaces U(2n,q)

155

(8)

Unsolved problems

163

(4)

Geometric Graph Theory

167

(34)

Janos Pach

Introduction, basic defintions

167

(1)

Crossing-free geometric graphs

168

(2)

Unavoidable crossings

170

(3)

Forbidden geometric subgraphs---Multiple crossings

173

(3)

Forbidden geometric subgraphs---Non-crossing configurations

176

(5)

Ramsey-type results

181

(4)

Applications

185

(5)

Geometric hypergraphs

190

(11)

Recent Excluded Minor Theorems for Graphs

201

(22)

Robin Thomas

Introduction

201

(1)

Seymour's splitter theorem

202

(2)

A splitter theorem for internally 4-connected graphs

204

(3)

A splitter theorem for cyclically 5-connected cubic graphs

207

(1)

Excluding a general graph

208

(1)

The graph minor theorem

209

(1)

Linklessly embeddable graphs

210

(2)

The four colour theorem

212

(1)

Hadwiger's conjecture

213

(1)

Tutte's edge 3-colouring conjecture

214

(1)

Pfaffian orientations

215

(8)

Parity, Cycle Space, and K4-Subdivisions in Graphs

223

(16)

C. Thomassen

Introduction

223

(1)

The cycle space of a graph and generating sets of cycles

224

(2)

The cycle space and collections of cycles determining uniquely a graph up to isomorphism

226

(2)

The cycle space generated by the cycles through two fixed edges

228

(1)

The cycle space of a graph and K4-subdivisions

229

(2)

Towards a charcterization of the graphs containing no totally odd K4-subdivisions

231

(3)

Open problems

234

(5)

Models of Random Regular Graphs

239

(48)

N. C. Wormald

Introduction

239

(2)

Uniform model for random regular graphs

241

(24)

Other uniform models

265

(3)

The small subgraph conditioning method, contiguity, and superposition models

268

(15)

The generation problem

283

(3)

Algorithmically defined models

286

(1)

A wider perspective

287

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Amazon no longer offers textbook rentals. We do!

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

Surveys in Combinatorics, 1999

9780521653763

0521653762

Supplemental Materials

Summary

Table of Contents

Supplemental Materials

Rewards Program