Generalized polygon

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.

Definition

A generalized 2-gon (or a digon) is a partial linear space where each point is incident to each line. For n > 3 a generalized n-gon is an incidence structure ( $P,L,I$ ), where $P$ is the set of points, $L$ is the set of lines and $I\subseteq P\times L$ is the incidence relation, such that:

It is a partial linear space.
It has no ordinary m-gons as subgeometry for 2 < m < n.
It has ordinary n-gon as a subgeometry.
For any $\{A_1, A_2\} \subseteq P \cup L$ there exists a subgeometry ( $P', L', I'$ ) isomorphic to an ordinary n-gon such that $\{A_1, A_2\} \subseteq P' \cup L'$ .

An equivalent but sometimes simpler way to express these conditions is: consider the bipartite incidence graph with the vertex set $P \cup L$ and the edges connecting the incident pairs of points and lines.

The girth of the incidence graph is twice the diameter n of the incidence graph.

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:

all vertices of the incidence graph corresponding to the elements of $L$ have the same degree s + 1 for some natural number s; in other words, every line contains exactly s + 1 points,
all vertices of the incidence graph corresponding to the elements of $P$ have the same degree t + 1 for some natural number t; in other words, every point lies on exactly t + 1 lines.

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 ( $P,L,I$ ), is the incidence structure with notion of points and lines reversed and the incidence relation taken to be the inverse relation of $I$ . It can easily be shown that this is again a generalized n-gon.

Examples

A generalized digon is a complete bipartite graph K_s+1,t+1.

For any natural n ≥ 3, consider the boundary of the ordinary polygon with n sides. Declare the vertices of the polygon to be the points and the sides to be the lines, with set inclusion as the incidence relation. This results in a generalized n-gon with s = t = 1.

For each group of Lie type G of rank 2 there is an associated generalized n-gon X with n equal to 3, 4, 6 or 8 such that G acts transitively on the set of flags of X. In the finite case, for n=6, one obtains the Split Cayley hexagon of order (q,q) for G₂(q) and the twisted triality hexagon of order (q³,q) for ³D₄(q³), and for n=8, one obtains the Ree-Tits octagon of order (q,q²) for ²F₄(q) with q=2²n+1. Up to duality, these are the only known thick finite generalized hexagons or octagons.

Feit-Higman theorem

Walter Feit and Graham Higman proved that finite generalized n-gons with s ≥ 2, t ≥ 2 can exist only for the following values of n:

2, 3, 4, 6 or 8.

Moreover,

If n = 2, the structure is a complete bipartite graph.
If n = 3, the structure is a finite projective plane, and s = t.
If n = 4, the structure is a finite generalized quadrangle, and t^1/2 ≤ s ≤ t².
If n = 6, then st is a square, and t^1/3 ≤ s ≤ t³.
If n = 8, then 2st is a square, and t^1/2 ≤ s ≤ t².
If s or t is allowed to be 1 and the structure is not the ordinary n-gon then besides the values of n already listed, only n = 12 may be possible.

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 the other infinite (these cases are called semi-finite).

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,2n) cage. They are also related to expander graphs as they have nice expansion properties.^[1] Several classes of extremal expander graphs are obtained from generalized polygons.^[2]

References

Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics 207, New York: Springer-Verlag, doi:10.1007/978-1-4613-0163-9, ISBN 0-387-95220-9, MR 1829620 .
Feit, Walter; Higman, Graham (1964), "The nonexistence of certain generalized polygons", Journal of Algebra 1: 114–131, doi:10.1016/0021-8693(64)90028-6, MR 0170955 .
van Maldeghem, Hendrik (1998), Generalized polygons, Monographs in Mathematics 93, Basel: Birkhäuser Verlag, doi:10.1007/978-3-0348-0271-0, ISBN 3-7643-5864-5, MR 1725957 .
Stanton, Dennis (1983), "Generalized n-gons and Chebychev polynomials", Journal of Combinatorial Theory, Series A 34 (1): 15–27, doi:10.1016/0097-3165(83)90036-5, MR 685208 .
Tits, Jacques; Weiss, Richard M. (2002), Moufang polygons, Springer Monographs in Mathematics, Berlin: Springer-Verlag, ISBN 3-540-43714-2, MR 1938841 .