Previous Seminars - 2007 to 2008

Previous seminars from: 2019/20, 2018/19, 2017/18, 2016/17, 2015/16, 2014/15, 2013/14, 2012/13, 2011/12, 2010/11, 2008/09, 2007/08

Wednesday 21st of May

Steve Linton
(University of St Andrews)
Bounding the growth rate of the class of permutations generated by two stacks in parallel (and related problems).

In Dunedin in February, Mike Atkinson, Michael Albert and I found new lower and upper bounds on the growth rate of some classical closed classes of permutations. I will explain our techniques and some interesting questions that arise.

Wednesday 7th of May

Steve Linton
(University of St Andrews)
Finding Canonical Images of Subspaces

At the Ohio Groups & Computation meeting last month Eamonn O'Brien raised the following challenge problem that arises from isomorphism testing for p-groups: Given a 3 dimensionsional subspace of the 28 dimensional exterior square of the natural module for G=GL(8,2), find a canonical member of it's G-orbit. I have a solution to this, which I'd like to explain, and some areas where I'm seeking help to take it further.

Wednesday 12th December

Mickael Gastinaeu
(Institut de Mecanique Celeste, Paris,
Parallel multiplication of sparse multivariate polynomials on Symmetric Multi-Processing Systems

Main topics of the presentation:

-- representation of polynomials in the specialised computer algebra system TRIP (

-- memory management of the objects

-- work sharing

Thursday 6th Decemeber

Stanislav Zivny (joint work with David Cohen and Peter Jeavons)

The Expressive Power of Valued Constraints In this talk we intruduce valued constraints and the algebraic

property which characterise the expressive power of valued constraints. We investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases a large class of valued constraints, of all possible arities, can be expressed by using valued constraints of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy. We also show the connection between the expressive power of valued constraints and the problem of submodular function minimisation.

Wednesday 24th of October

Fiona Brunk
(St Andrews)
Intersection problems in combinatorics

The Erdos-Ko-Rado Theorem, published in 1961, states that if k<=n/2 and n is large, then the family of all k-element subsets of {1,2,...,n} containing {1,2,...,t} is the unique largest family of k-element subsets of {1,2,...,n} such that each pair of subsets intersects in t elements. This sparked a sequence of papers on 'Erdos-Ko-Rado type theorems' for other types of sets/words/ permutations/graphs and so on. I will discuss some of these theorems in my talk.

Thursday 6th September

Chris Jefferson
Solving CSPs with Groebner Bases

Groebner Bases are a powerful algebraic tool which are used in a variety of settings. I will show how they can be effectively used to solve constraint problems, and also how they can be used to solve a number of related problems, including solution counting and the implementation of progagation algorithms.