Surveys in Combinatorics, 1997

The book is Surveys in Combinatorics, 1997, edited by R. A. Bailey, London Mathematical Society Lecture Note Series, 241, Cambridge University Press, Cambridge, 1997. 338 pp. ISBN 0 521 59840 0.

It contains the nine invited papers given at the 16th British Combinatorial Conference, which was held at Queen Mary and Westfield College, London from 7 to 11 July 1997. Speakers, titles and abstracts follow.

J. H. Conway: M13

The group M13 has no transitive extension, but the object of the title is the next best thing: a set of permutations which is an extension of M13. We give an elementary construction, based on a moving-counter puzzle on the projective plane of order 3, and provide easy proofs of some of its properties.

Keith Edwards: The Harmonious Chromatic Number and the Achromatic Number

The harmonious chromatic number of a graph is the least number of colours in a vertex colouring such that each pair of colours appears on at most one edge. The achromatic number of a graph is the greatest number of colours in a vertex colouring such that each pair of colours appears on at least one edge. This paper is a survey of what is known about these two parameters, in particular we look at upper and lower bounds, special classes of graphs and complexity issues.

Clement Lam: Computer Construction of Block Designs

This paper uses an extended example to illustrate how to put together a BDX program to construct block designs fixed by an automorphism, given its orbit matrix. It shows how to specify the parameters and the structural information of the designs. It discusses the symmetry group of the problem and isomorph rejection. It explains how to choose a good order of generation to minimize the size of the search. It also shows how to estimate the size of a search and how to partition the problem into subproblems which can be searched in parallel on several computers.

Cheryl E. Praeger: Finite Quasiprimitive Graphs

A permutation group on a set $\Omega$ is said to be quasiprimitive on $\Omega$ if each of its nontrivial normal subgroups is transitive on $\Omega$. For certain families of finite arc-transitive graphs, those members possessing subgroups of automorphisms which are quasiprimitive on vertices play a key role. The manner in which the quasiprimitive examples arise, together with their structure, is described.

B. A. Reed: Tree Width and Tangles: A New Connectivity Measure And Some Applications

We discuss tree width, a new connectivity invariant of graphs defined by Robertson and Seymour. We present a duality result and a canonical decomposition theorem tied to this invariant. We also discuss a number of applications of these results, including Robertson and Seymour's Graph Minors Project.

Alexander Schrijver: Minor-monotone Graph Invariants

A graph parameter $\phi(G)$ is called minor-monotone if $\phi(H)\leq\phi(G)$ for any minor $H$ of $G$. We survey recent work on minor-monotone graph parameters motivated by the parameter $\mu(G)$ introduced by Colin de Verdière.

T. Szönyi: Some applications of algebraic curves in finite geometry and combinatorics

Various applications of Weil's theorem in finite geometry and combinatorics are surveyed. Several illustrative proofs are sketched. As a by-product, we give an up-to-date account on what is known about complete arcs, minimal blocking sets and (k,n)-arcs in the desarguesian plane PG(2,q).

William T. Trotter: New perspectives on interval orders and interval graphs

Interval orders and interval graphs are particularly natural examples of two widely studied classes of discrete structures: partially ordered sets and undirected graphs. So it is not surprising that researchers in such diverse fields as mathematics, computer science, engineering and the social sciences have investigated structural, algorithmic, enumerative, combinatorial, extremal and even experimental problems associated with them. In this article, we survey recent work on interval orders and interval graphs, including research on on-line coloring, dimension estimates, fractional parameters, balancing pairs, hamiltonian paths, ramsey theory, extremal problems and tolerance orders. We provide an outline of the arguments for many of these results, especially those which seem to have a wide range of potential applications. Also, we provide short proofs of some of the more classical results on interval orders and interval graphs. Our goal is to provide fresh insights into the current status of research in this area while suggesting new perspectives and directions for the future.

Dominic Welsh: Approximate Counting

I shall survey a range of very basic but provably hard counting problems which have a unifying geometrical theme. For each of them exact evaluation is #P-hard but there is no obvious obstruction to the existence of a fast randomised approximation algorithm. I shall outline the techniques which are available and describe what is currently known. In most cases the results obtained only apply to a part of the input so there remain many open questions.

R. A. Bailey

Page maintained by R. A. Bailey.