 |
University of Wales, Bangor - School of Informatics19th British Combinatorial ConferenceInvited Speakers & Survey Articles |
 |
|
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:
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:
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.
|
|