Splinter Group:
Algebraic Combinatorics

Organizer: Emil Skoeldberg (National University of Ireland, Galway)

All talks will be held in Room AC204.

Speakers include:

Wednesday, April 8 2009

14:15 - 14:45

Andreas Distler (University of St Andrews):
The Enumeration of Semigroups of Order 9

In contrast to the case of groups, only the semigroups with up to 8 elements are known. There are 1,843,973,431 of them. They were first constructed in 1994 by Satoh, Yamah and Tokizawa using an implementation developed specifically for this purpose. Their program essentially performed a backtrack search on the entries in an 8\!\times\! 8 multiplication table.
  In this talk I will present an approach using more of the structural properties of semigroups to obtain the number of semigroups of order 9. Most semigroups S have a very simple structure. That is, the product of any three elements in S is 0 and 0x = x0=0 for all x\in S. The name for such semigroups is {\it 3-nilpotent}. We have developed a formula for their number for any finite order, using Polya's enumeration method.
  In the next step of our approach, a Constraint Satisfaction Problem (CSP) is formulated having the remaining semigroups - less than 1\,\% for orders 8 and 9 - as solutions. Further case splits eliminate computational bottlenecks by using additional structure for individual cases. For bands (i.\,e. idempotent semigroups) for example, we exploit the underlying semilattice structure of rectangular bands. The resulting CSP instances are solved by the CSP solver Minion.

14:45 - 15:15

David Quinn (NUI Galway):
The Incidence Algebras of (Non-pure) Constructible and Shellable Posets

Considering the incidence algebra of a poset as a quotient of the quiver on the Hasse diagram with the ideal generated by path equivalences. We examine the relationship between a Groebner Basis of this ideal and the condition that the poset be either constructible or shellable. In doing so we also introduce a natural extension of constructible to include non pure complexes.

15:15 - 15:45

Alessandro Conflitti (CMUC, Portugal):
Whitney Numbers of Order Ideals of Generalized Fences, Crowns and Garlands

We give explicit formulae for the rank polynomial and Whitney numbers of the distributive lattice of order ideals of fences with higher asymmetric peaks, crown poset and garland poset, ordered by inclusion.