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:
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.
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
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
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:
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.