skip to content

The profile of a relational structure

Tuesday 24th June 2008 - 16:20 to 17:00
Center for Mathematical Sciences

A relational structure is a set carrying a collection of relations with specified arities. Graphs, partial orders, circular orders, etc. are examples. The age of an infinite relational structure is the class of all finite structures embeddable into it, and the profile is the sequence (f0,f1,f2,...), where fn is the number of n-element structures in the age, up to isomorphism.

Quite a lot is known about the rate of growth of the profile; much less about "local" inequalities relating individual values of fn for different n. It is known that fn<=f{n+1}. There are two proofs, one using finite combinatorics and linear algebra, the other using Ramsey's Theorem.

There is a commutative associative graded algebra, the age algebra, whose Hilbert series is the generating function of the profile. Recently, Maurice Pouzet showed that, if the age of R cannot be made smaller by deleting a point, then the age algebra is an integral domain. It follows, using dimension theory, that f{m+n}>=fm+fn-1. A further conjecture on the age algebra would imply that, under the same assumption, g{m+n}>=gm+gn-1, where gn=f{n+1}-fn.

All these results apply to the situation where G is an infinite permutation group on a set Omega, and fn is the number of G-orbits on the set of n-element subsets of Omega. The assumption in the preceding paragraph translates into the condition that G has no finite orbits on Omega.

Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons