BCC logo

University of Wales, Bangor - School of Informatics

19th British Combinatorial Conference

Invited Speakers & Survey Articles

Maths at Bangor

Invited Speakers

Survey Articles

(printed in: Surveys in Combinatorics, 2003, London Mathematical Society Lecture Notes 307, CUP, June 2003)

1. Lars Andersen (Aalborg) & Chris Rodger (Auburn):
Decompositions of complete graphs: embedding partial edge-colourings and the method of amalgamations

We consider decompositions of the edges of complete graphs, mainly with each part inducing a spanning subgraph with specified properties.
We give special attention to embedding questions, where a decomposition of the edges of a complete subgraph of a complete graph is given, and the question is to extend the decomposition to a full decomposition with the desired properties.
One way to obtain decomposition and embedding results simultaneously is by the method of amalgamations of vertices, to which we devote a large part of the paper. 2. Simon Blackburn (Royal Holloway):
Combinatorial schemes for protecting digital content

When digital information is widely distributed in some fashion, the distributor would often like to limit who can access the content (this is true for subscription digital T.V. for example) or would like to trace the source of pirate copies of the information (music CDs being an example here).
The paper will survey some of the schemes that have been proposed to achieve these aims, especially emphasising the underlying combinatorics involved. 3. Alexandre Borovik (UMIST):
Matroids and Coxeter groups

The paper describes a few ways in which the concept of a Coxeter group (in its most ubiquitous manifestation, the symmetric group) emerges in the theory of ordinary matroids:

These observations suggest a very natural generalisation of matroids; the new objects are called Coxeter matroids and are related to other Coxeter groups in the same way as (classical) matroids are related to the symmetric group. 4. Pavol Hell (British Columbia):
Algorithmic aspects of graph homomorphisms

Homomorphisms are useful models for a wide variety of combinatorial problems dealing with mappings and assignments, typified by scheduling and channel assignment problems. Homomorphism problems generalize graph colourings, and are in turn generalized by constraint satisfaction problems; they represent a robust intermediate class of problems - with greater modeling power than graph colourings, yet simpler and more manageable than general constraint satisfaction problems. We will discuss various homomorphism problems from a computational perspective.
One variant, with natural applications, gives each vertex a list of allowed images. Such list homomorphisms generalize list colourings, pre-colouring extensions, and graph retractions. Many algorithms for finding homomorphisms adapt well to finding list homomorphisms.
Another variant generalizes the kinds of partitions that homomorphisms induce, to allow both homomorphism type constraints, and constraints that correspond to homomorphisms in the complementary graphs. Surprizingly, the resulting problems (which we shall call semi-homomorphism partition problems) cover a great variety of concepts arising in the study of perfect graphs. We illustrate some of the ideas leading to efficient algorithms for these problems. 5. Dina Ghinelli (Rome) & Dieter Jungnickel (Augsburg):
Finite projective planes with a large abelian group

Let Pi be a finite projective plane of order n, and let G be a large abelian (or, more generally, quasi-regular) collineation group of Pi; to be specific, we assume |G| > (n^2+n+1)/2. Such planes have been classified into eight cases by Dembowski and Piper in 1967. We survey the present state of knowledge about the existence and structure of such planes. We also discuss some geometric applications, in particular to the construction of arcs and ovals. Technically, a recurrent theme will be the amazing strength of the approach using various types of difference sets and the machinery of integral group rings. 6. Imre Leader (Cambridge):
Partition Regular Equations

A finite or infinite matrix A is called partition regular if whenever the natural numbers are finitely coloured there exists a monochromatic vector x with Ax = 0. Many of the classical results of Ramsey theory, such as van der Waerden's theorem or Schur's theorem, may be naturally rephrased as assertions that certain matrices are partition regular.
While the structure of finite partition regular matrices is well understood, very little is known in the infinite case. In this survey paper we will review some known results and then proceed to some new results. 7. Kendra Nelsen & Arun Ram (Wisconsin-Madison):
Kostka-Foulkes poylnomials and Macdonald spherical functions

Generalised Hall-Littlewood polynomials (Macdonald spherical functions) and generalised Kostka-Foulkes polynomials (q-weight multiplicities) arise in many places in combinatorics, representation theory, geometry, and mathematical physics.
This paper attempts to organise the different definitions of these objects and prove the fundamental combinatorial results from "scratch", in a presentation which, hopefully, will be accessible and useful for both the non-expert and researchers currently working in this very active field.
The combinatorics of the affine Hecke algebra plays a central role.
The final section of this paper can be read independently of the rest of the paper. It presents, with proof, Lascoux and Schutzenberger's positive formula for the Kostka-Foulkes polynomials in the type A case. 8. Diane Donovan (Queensland), Ebadollah Mahmoodian (Sharif, Iran) Colin Ramsay (Queensland) & Anne Street (Queensland):
Defining sets in combinatorics: a survey

In a given class of combinatorial structures, there may be many distinct objects with the same parameters. Two questions arise naturally:

These questions are obviously related, the first leading to the concept of a trade, and the second to that of a defining set.
This survey deals with defining sets in block designs, graphs and some related structures. The corresponding trades in each structure are also discussed briefly. 9. Günter Ziegler & Volker Kaibel (T.U., Berlin):
Counting lattice triangulations

We discuss the problem to count, or, more modestly, to estimate the number f (m,n) of unimodular triangulations of the planar grid of size m x n.
Among other tools, we employ recursions that allow one to compute the (huge) number of triangulations for small m and rather large n by dynamic programming; we show that this computation can be done in polynomial time if m is fixed, and present computational results from our implementation of this approach.
We also present new upper and lower bounds for large m and n, and report about results obtained from a computer simulation of the random walk that is generated by flips.