![]() | ||
In combinatorial theory, a generalized polygon is an incidence structure introduced by Jacques Tits in 1959. Generalized n-gons encompass as special cases projective planes (generalized triangles, n = 3) and generalized quadrangles (n = 4). Many generalized polygons arise from groups of Lie type, but there are also exotic ones that cannot be obtained in this way. Generalized polygons satisfying a technical condition known as the Moufang property have been completely classified by Tits and Weiss. Every generalized n-gon with n even is also a near polygon.
Contents
Definition
A generalized 2-gon (or a digon) is an incidence structure with at least 2 points and 2 lines where each point is incident to each line.
For
An equivalent but sometimes simpler way to express these conditions is: consider the bipartite incidence graph with the vertex set
From this it should be clear that the incidence graphs of generalized polygons are Moore graphs.
A generalized polygon is of order (s,t) if:
We say a generalized polygon is thick if every point (line) is incident with at least three lines (points). All thick generalized polygons have an order.
The dual of a generalized n-gon (
Examples
Restriction on parameters
Walter Feit and Graham Higman proved that finite generalized n-gons of order (s, t) with s ≥ 2, t ≥ 2 can exist only for the following values of n:
2, 3, 4, 6 or 8.Generalized "n"-gons for these values are referred to as generalized digons, triangles, quadrangles, hexagons and octagons.
When Feit-Higman theorem is combined with the Haemers-Roos inequalities, we get the following restrictions,
Every known finite generalized hexagon of order (s, t) for s, t > 1 has order
where q is a prime power.
Every known finite generalized octagon of order (s, t) for s, t > 1 has order
where q is an odd power of 2.
Semi-finite generalized polygons
If s and t are both infinite then generalized polygons exist for each n greater or equal to 2. It is unknown whether or not there exist generalized polygons with one of the parameters finite (and bigger than 1) while the other infinite (these cases are called semi-finite). Peter Cameron proved the non-existence of semi-finite generalized quadrangles with three points on each line, while Andries Brouwer and Bill Kantor independently proved the case of four points on each line. The non-existence result for five points on each line was proved by G. Cherlin using Model Theory. No such results are known without making any further assumptions for generalized hexagons or octagons, even for the smallest case of three points on each line.
Combinatorial applications
As noted before the incidence graphs of generalized polygons have important properties. For example, every generalized n-gon of order (s,s) is a (s+1,2n) cage. They are also related to expander graphs as they have nice expansion properties. Several classes of extremal expander graphs are obtained from generalized polygons. In Ramsey theory, graphs constructed using generalized polygons give us some of the best known constructive lower bounds on offdiagonal Ramsey numbers.