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.