Independent sets and RWPRI incidence geometries
by
Philippe Cara
Vrije Universiteit Brussel
Coauthors: P.J. Cameron (Queen Mary, University of London)

A subset S of a group G is called independent if we have s not in <S\{ s}> for each s in S.

For an integer n >= 1, an incidence geometry \Gamma of rank n is a graph (X, * ), whose vertices are called elements, together with a map t:X --> I={1, 2, ... , n} such that t^-1(i) is a coclique for each i in I. The relation * on X is called incidence relation and the map t is called the type function. A flag F of \Gamma is a clique of (X, *). We assume that \Gamma is firm, that is: every flag F with t(F) =/= I is contained in at least two flags of type I.

The residue \Gamma_F of a flag F, is the firm incidence geometry of rank n-|t(F)| whose elements are all a in X\F such that {a} \cup F is also a flag, together with the restrictions of * and t to these elements.

An automorphism of \Gamma is an isomorphism \alpha of graphs from (X, *) to itself such that t o \alpha = t. Let G be a group of automorphisms of \Gamma. If G acts transitively on the flags F with t(F)=I, we say that G acts flag-transitively.

We now consider pairs (\Gamma, G) where \Gamma is an incidence geometry and G is a group of automorphisms acting flag-transitively. A pair (\Gamma, G) is said to be WPRI provided that G acts primitively on the elements of at least one type i in I. We denote the element set of a residue \Gamma_F by X_F. The permutation group G_F^X_F induced by the action of the stabilizer G_F of F in G on X_F is flag-transitive. A weakly primitive pair (\Gamma, G) is said to be RWPRI if (\Gamma_F, G_F^X_F) is WPRI for every residue \Gamma_F in \Gamma.

We show that RWPRI pairs are strongly related to independent sets.

Applying this relation, we show for example that the highest possible rank for an incidence geometry \Gamma on which the symmetric group of degree n acts flag-transitively such that the pair (\Gamma, Sym(n)) is RWPRI, is n-1. We also show that this bound is tight.

Date received: February 28, 2001