skip to content


Nick Gill (University of South Wales)
On Cherlin's conjecture for finite permutation groups

Motivated by questions arising in model theory, Cherlin has made an interesting conjecture concerning finite permutation groups. Work of Wiscons has reduced the conjecture to the following statement: The only almost simple BINARY permutation groups are Sn acting on n points. (The adjective “binary” means, roughly, that the orbits on k-tuples can be deduced from the orbits on 2-tuples, for any k>2.)

We will report on current work aimed at proving Cherlin’s conjecture. We will focus on the case where our permutation group is a group of Lie type (for instance PGLn(q)); in this situation we can say rather a lot. This is joint work with Francis Hunt (USW) and Pablo Spiga (Milano-Bicocca).

Robert Gray (University of East Anglia)
Young tableaux, Kashiwara crystals and combinatorial semigroup theory

The Plactic monoid is a fundamental algebraic object which captures a natural monoid structure carried by the set of semistandard Young tableaux. It arose originally in the work of Schensted (1961) on algorithms for finding the maximal length of a nondecreasing subsequence of a given word over the ordered alphabet An = {1 < 2 < . . . < n}. The output of Schensted’s algorithm is a tableau and, by identifying pairs of words that lead to the same tableau, one obtains the Plactic monoid Pl(An) of rank n. Alternatively, the Plactic monoid may be defined by a finite presentation with generating symbols An and certain finite set of defining relations which were originally determined in work of Knuth (1970). A third way of obtaining this monoid comes from Kashiwara’s theory of crystal bases. Crystal basis theory was introduced by Kashiwara in the 90s. It provides an important tool for studying integral representations of certain quantum groups Uq(g). A crystal basis can be viewed as a certain finite coloured directed graph. The corresponding crystal graph is then built from the crystal basis in an inductive way using Kashiwara crystal graph operators. The vertices of the crystal graph may be identified with words over a finite alphabet, and a natural congruence may be defined on these words, given in terms of the crystal structure on the vertices. In this way, associated with each crystal graph is a monoid. In the case that g is the special linear Lie algebra sln+1 the monoid that arises from this construction turns out to be the Plactic monoid Pl(An). In this talk I will explain these three different ways of looking at the Plactic monoid, and how they lead to the general notion of a crystal monoid. Then I will present some recent joint work with A. J. Cain and A. Malheiro on the problem of constructing complete rewriting systems, and finding biautomatic structures, for crystal monoids.

Jan Kratochvil (Charles University, Czech Republic)
Geometric intersection graphs: is extending partial representations hard?

Geometric intersection graphs (such as interval graphs, circular arc
graphs, rectangle intersection graphs and many others) are studied for
their applied motivations and interesting complexity aspects. Many of
these classes allow elegant combinatorial characterizations, and very
often optimization problems that are hard on general graphs can be solved
efficiently on intersection graphs when a representation is given. This
makes the question of recognition of these classes important, and indeed,
many of these classes can be recognized in polynomial time.

It is a common experience (at least of architects and construction
companies) that building from scratch is easier (and cheaper) than
restoring an existing structure. And similarly, extending a partial
solution (to a graph theory problem) is often provably harder than finding
a solution from scratch. (Examples from graph coloring will be shown.) In
this context it is natural to pose the following question: Given a graph
and a partial representaton of a specified type (i.e., a representation of
an induced subgraph by intersections of certain geometric objects), can
this partial representation be extended to a representation of the entire
graph? How difficult is it to decide or to construct such an extension? The
talk will survey known results and open problems in this area.

Kitty Meeks (University of Glasgow)
The complexity of finding and counting small subgraphs

Suppose we are given a graph on n vertices, and we are interested in subgraphs on k vertices (where k is much smaller than n) which have certain properties. This situation arises in many practical applications, including computational biology, network security and the analysis of social networks.

There are a number of natural algorithmic questions we can ask in this setting. Can we efficiently decide whether there is at least one subgraph with the desired property? Can we count how many subgraphs have the desired property? If we know there is at least one subgraph with the desired property, can we *find* such a subgraph, or indeed list all such subgraphs, efficiently?

In this talk, I will give an overview of both positive and negative answers to these questions, as well as discussing how diverse areas of combinatorics - from Ramsey Theory, through graph minors, to poset lattices - have been used to provide answers.

Some of this talk will be based on joint work with Mark Jerrum (QMUL).

Jan Arne Telle (University of Bergen, Norway)
The graph formulation of the union-closed sets conjecture

In 1979 Frankl conjectured that in a finite non-trivial union-closed collection of sets there has to be an element that belongs to at least half the sets. The conjecture is still wide open. We show that it is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show in this talk that it holds also for the chordal bipartite graphs, where all induced cycles have length 4. We will also discuss if there are any advantages to attacking the union-closed conjecture through its graph formulation.