Generalized polygon

Last updated January 30, 2023

In mathematics, 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 an incidence structure with at least 2 points and 2 lines where each point is incident to each line.

For $n\geq 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\leq m<n$ .
It has an 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 converse relation of $I$ . It can easily be shown that this is again a generalized n-gon.

Examples

The incidence graph of 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²ⁿ⁺¹. Up to duality, these are the only known thick finite generalized hexagons or octagons.

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. Another proof of the Feit-Higman result was given by Kilmoyer and Solomon.

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,

If n = 2, the incidence graph is a complete bipartite graph and thus "s", "t" can be arbitrary integers.
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.

Every known finite generalized hexagon of order (s, t) for s, t > 1 has order

(q, q): the split Cayley hexagons and their duals,
(q³, q): the twisted triality hexagon, or
(q, q³): the dual twisted triality hexagon,

where q is a prime power.

Every known finite generalized octagon of order (s, t) for s, t > 1 has order

(q, q²): the Ree-Tits octagon or
(q², q): the dual Ree-Tits octagon,

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.^[1] 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.^[2] Several classes of extremal expander graphs are obtained from generalized polygons.^[3] In Ramsey theory, graphs constructed using generalized polygons give us some of the best known constructive lower bounds on offdiagonal Ramsey numbers.^[4]

Related Research Articles

In geometry, a polygon is a plane figure that is described by a finite number of straight line segments connected to form a closed polygonal chain. The bounded plane region, the bounding circuit, or the two together, may be called a polygon.

Jacques Tits was a Belgian-born French mathematician who worked on group theory and incidence geometry. He introduced Tits buildings, the Tits alternative, the Tits group, and the Tits metric.

A finite geometry is any geometric system that has only a finite number of points. The familiar Euclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where the pixels are considered to be the points, would be a finite geometry. While there are many systems that could be called finite geometries, attention is mostly paid to the finite projective and affine spaces because of their regularity and simplicity. Other significant types of finite geometry are finite Möbius or inversive planes and Laguerre planes, which are examples of a general type called Benz planes, and their higher-dimensional analogs such as higher finite inversive geometries.

In mathematics, a building is a combinatorial and geometric structure which simultaneously generalizes certain aspects of flag manifolds, finite projective planes, and Riemannian symmetric spaces. Buildings were initially introduced by Jacques Tits as a means to understand the structure of exceptional groups of Lie type. The more specialized theory of Bruhat–Tits buildings plays a role in the study of $p$ -adic Lie groups analogous to that of the theory of symmetric spaces in the theory of Lie groups.

In Euclidean geometry, a regular polygon is a polygon that is direct equiangular and equilateral. Regular polygons may be either convex, star or skew. In the limit, a sequence of regular polygons with an increasing number of sides approximates a circle, if the perimeter or area is fixed, or a regular apeirogon, if the edge length is fixed.

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

In finite geometry, the Fano plane is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines cannot exist with this pattern of incidences in Euclidean geometry, but they can be given coordinates using the finite field with two elements. The standard notation for this plane, as a member of a family of projective spaces, is $PG(2, 2)$ . Here $PG$ stands for "projective geometry", the first parameter is the geometric dimension and the second parameter is the order.

In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related and 0 if they are not. There are variations; see below.

<span class="mw-page-title-main">Incidence structure</span>

In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore all the properties of this geometry except for the relation of which points are on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane.

In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An incidence structure is what is obtained when all other concepts are removed and all that remains is the data about which points lie on which lines. Even with this severe limitation, theorems can be proved and interesting facts emerge concerning this structure. Such fundamental results remain valid when additional concepts are added to form a richer geometry. It sometimes happens that authors blur the distinction between a study and the objects of that study, so it is not surprising to find that some authors refer to incidence structures as incidence geometries.

<span class="mw-page-title-main">Happy ending problem</span>

In mathematics, the "happy ending problem" is the following statement:

In mathematics, a translation plane is a projective plane which admits a certain group of symmetries. Along with the Hughes planes and the Figueroa planes, translation planes are among the most well-studied of the known non-Desarguesian planes, and the vast majority of known non-Desarguesian planes are either translation planes, or can be obtained from a translation plane via successive iterations of dualization and/or derivation.

<span class="mw-page-title-main">Generalized quadrangle</span>

In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles. A generalized quadrangle is by definition a polar space of rank two. They are the generalized n-gons with n = 4 and near 2n-gons with n = 2. They are also precisely the partial geometries pg(s,t,α) with α = 1.

In mathematics, in the field of geometry, a polar space of rank n, or projective indexn − 1, consists of a set P, conventionally called the set of points, together with certain subsets of P, called subspaces, that satisfy these axioms:

In graph theory, a Moore graph is a regular graph whose girth is more than twice its diameter. If the degree of such a graph is $d$ and its diameter is $k$ , its girth must equal $2 k + 1$ . This is true, for a graph of degree $d$ and diameter $k$ , if and only if its number of vertices equals

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

In mathematics, Moufang polygons are a generalization by Jacques Tits of the Moufang planes studied by Ruth Moufang, and are irreducible buildings of rank two that admit the action of root groups. In a book on the topic, Tits and Richard Weiss classify them all. An earlier theorem, proved independently by Tits and Weiss, showed that a Moufang polygon must be a generalized 3-gon, 4-gon, 6-gon, or 8-gon, so the purpose of the aforementioned book was to analyze these four cases.

In mathematics, a near polygon is an incidence geometry introduced by Ernest E. Shult and Arthur Yanushka in 1980. Shult and Yanushka showed the connection between the so-called tetrahedrally closed line-systems in Euclidean spaces and a class of point-line geometries which they called near polygons. These structures generalise the notion of generalized polygon as every generalized 2n-gon is a near 2n-gon of a particular kind. Near polygons were extensively studied and connection between them and dual polar spaces was shown in 1980s and early 1990s. Some sporadic simple groups, for example the Hall-Janko group and the Mathieu groups, act as automorphism groups of near polygons.

References

↑ Cherlin, Gregory (2005). "Locally finite generalized quadrangles with at most five points per line". Discrete Mathematics. 291 (1–3): 73–79. doi: 10.1016/j.disc.2004.04.021 .
↑ Tanner, R. Michael (1984). "Explicit Concentrators from Generalized N-Gons". SIAM Journal on Algebraic and Discrete Methods. 5 (3): 287–293. doi:10.1137/0605030. hdl: 10338.dmlcz/102386 .
↑ Nozaki, Hiroshi (2014). "Linear programming bounds for regular graphs". arXiv: 1407.4562 [math.CO].
↑ Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech (2010). "Some constructive bounds on Ramsey numbers". Journal of Combinatorial Theory, Series B. 100 (5): 439–445. doi: 10.1016/j.jctb.2010.01.003 .

Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, New York: Springer-Verlag, doi:10.1007/978-1-4613-0163-9, ISBN 978-0-387-95220-8, MR 1829620 .
Feit, Walter; Higman, Graham (1964), "The nonexistence of certain generalized polygons", Journal of Algebra, 1 (2): 114–131, doi: 10.1016/0021-8693(64)90028-6 , MR 0170955 .

Haemers, W. H.; Roos, C. (1981), "An inequality for generalized hexagons", Geometriae Dedicata, 10 (1–4): 219–222, doi:10.1007/BF01447425, MR 0608143 .

Kantor, W. M. (1986). "Generalized polygons, SCABs and GABs". Buildings and the Geometry of Diagrams. Lecture Notes in Mathematics. Vol. 1181. Springer-Verlag, Berlin. pp. 79–158. CiteSeerX 10.1.1.74.3986 . doi:10.1007/BFb0075513. ISBN 978-3-540-16466-1.
Kilmoyer, Robert; Solomon, Louis (1973), "On the theorem of Feit-Higman", Journal of Combinatorial Theory, Series A , 15 (3): 310–322, doi: 10.1016/0097-3165(73)90076-9 , MR 0357157
Van Maldeghem, Hendrik (1998), Generalized polygons, Monographs in Mathematics, vol. 93, Basel: Birkhäuser Verlag, doi:10.1007/978-3-0348-0271-0, ISBN 978-3-7643-5864-8, 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 0685208 .
Tits, Jacques; Weiss, Richard M. (2002), Moufang polygons, Springer Monographs in Mathematics, Berlin: Springer-Verlag, ISBN 978-3-540-43714-7, MR 1938841 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Cherlin, Gregory (2005). "Locally finite generalized quadrangles with at most five points per line". Discrete Mathematics. 291 (1–3): 73–79. doi: 10.1016/j.disc.2004.04.021 .

[2] Tanner, R. Michael (1984). "Explicit Concentrators from Generalized N-Gons". SIAM Journal on Algebraic and Discrete Methods. 5 (3): 287–293. doi:10.1137/0605030. hdl: 10338.dmlcz/102386 .

[3] Nozaki, Hiroshi (2014). "Linear programming bounds for regular graphs". arXiv: 1407.4562 [math.CO].

[4] Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech (2010). "Some constructive bounds on Ramsey numbers". Journal of Combinatorial Theory, Series B. 100 (5): 439–445. doi: 10.1016/j.jctb.2010.01.003 .

[1]

[2]

[3]

[4]