Some notation: The set will be denoted by . For every set we have the set of all subsets of , also known as the power set, which we will denote by . This notation makes some sense if you notice that each subset of can be seen as a map from to , and that the number of elements in is .
As mentioned in the previous post, generalized polygons are an important class of point-line geometries which are related to several interesting concepts in mathematics. Here I would discuss the basic definitions of point-line geometries with some examples to make this notion clear.
A point-line geometry is a pair of sets where , with referred to as points and as lines. Two points of a point-line geometry are called collinear if they are both contained in a common line, and two lines are said to intersect if they contain a common point. For example, by defining and we get a point-line geometry that has three points, three lines, two points on each line, and two lines through each point. Moreover, in this geometry through every pair of points there is a unique line and every pair of lines intersects in a unique point. Therefore, this is an example of a projective plane as discussed here.
Of course in the definition we could give the sets and whatever names we like. The names ‘points’ and ‘lines’ are chosen so that we can use the familiar terminology from euclidean geometry. In general, the notion of such point-line geometries is the same as that of a hypergraph. A hypergraph is a pair of sets where , with referred to as vertices and as edges. Thus, graphs are precisely those hypergraphs where each edge has size two. In a hypergraph if we have two vertices contained in a common edge then we say that they are adjacent, while in a point-line geometry if two points are contained in a common line then we say that they are collinear. In point-line geometries we usually make an assumption that for every pair of points there is at most one line passing through them. These point-line geometries are called partial linear spaces.
As an interesting example of a partial linear space, let’s consider the generalized quadrangles.
A generalized quadrangle () is a point-line geometry such that for every point and every line that doesn’t contain there is a unique point on collinear with .
Remark: Why is this point-line geometry a partial linear space?
A small but non-trivial example of a generalized quadrangle is given by and where, for example, if you take and then the unique point on collinear with is , with being the unique line containing and . This generalized quadrangle can be visualised as a grid (see Figure below). Note that the ordinary quadrangle is also a generalized quadrangle (otherwise we wouldn’t call them generalized quadrangles!) with and .
If we know that in a generalized quadrangle every line contains points and every point is contained in line for some fixed , then we say that has order , or in other words is a . Therefore, the grid is an example of a , and in general the grid is a . The grid for is also a but it doesn’t have any order.
With every point-line geometry (or hypergraph) we have two associated graphs, the point-collinearity graph and the incidence graph. The point-collinearity graph has the points as vertices and the edges are pairs of collinear points. So, the lines correspond to certain cliques in the point-collinearity graph. The incidence graph is a bipartite graphs with vertices as points and line, and an edge between every point line pair where the point is contained in the line .
Two important parameters of a graph are its diameter and its girth. The diameter is the maximum distance between any pair of vertices of the graph while the girth is the length of the shortest cycle in the graph. It would be a good exercise to prove that the incidence graph of any generalized quadrangle has diameter and girth which makes it a Cage. Another interesting property of generalized quadrangles that can be proved easily is that the point-collinearity graph of any is a strongly regular graph with parameters . Using this fact we can restrict the parameters for which a exists since there are many well known restrictions on the parameters of strongly regular graphs. Overall, we have the following result:
Let be a of order . Then,
- and .
- The integer divides .
- If and , then and .
For proofs of these results we refer to the standard reference on generalized quadrangles: Finite Generalized Quadrangle by S. E. Payne and J. A. Thas.