Point-Line Geometries

Some notation: The set \{1, 2, \ldots, n\} will be denoted by [n]. For every set S we have the set of all subsets of S, also known as the power set, which we will denote by 2^S. This notation makes some sense if you notice that each subset of S can be seen as a map from S to \{0, 1\}, and that the number of elements in 2^{[n]} is 2^n.

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 (\mathcal{P}, \mathcal{L}) where \mathcal{L} \subseteq 2^{\mathcal{P}}, with \mathcal P referred to as points and \mathcal L 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 \mathcal{P} := [3] = \{1, 2, 3\} and \mathcal{L} := \{12, 23, 31\} 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 \mathcal{P} and \mathcal{L} 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 (V, E) where E \subseteq 2^V, with V referred to as vertices and E 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 (GQ) is a point-line geometry (\mathcal{P}, \mathcal{L}) such that for every point p and every line L that doesn’t contain p there is a unique point on L collinear with p.

Remark: Why is this point-line geometry a partial linear space?

A small but non-trivial example of a generalized quadrangle is given by \mathcal P = [9] and \mathcal L = \{123, 456, 789, 147, 258, 369\} where, for example, if you take p = 4 and L = 123 then the unique point on L collinear with p is 1 , with 147 being the unique line containing p and 1 . This generalized quadrangle can be visualised as a 3 \times 3 grid (see Figure below). Note that the ordinary quadrangle is also a generalized quadrangle (otherwise we wouldn’t call them generalized quadrangles!) with \mathcal P = \{1, 2, 3, 4\} and \mathcal L = \{12, 23, 34, 41\}.


If we know that in a generalized quadrangle \mathcal S = (\mathcal P, \mathcal L) every line contains s+1 points and every point is contained in t+1 line for some fixed s, t then we say that \mathcal S has order (s, t), or in other words \mathcal S is a GQ(s, t). Therefore, the 3 \times 3 grid is an example of a GQ(2,1), and in general the n \times n grid is a GQ(n-1, 1). The m \times n grid for m \neq n is also a GQ but it doesn’t have any order.

With every point-line geometry (\mathcal{P}, \mathcal{L}) (or hypergraph) we have two associated graphs, the point-collinearity graph and the incidence graph. The point-collinearity graph has the points \mathcal{P} 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 (p, L) where the point p is contained in the line L.

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 4 and girth 8 which makes it a Cage. Another interesting property of generalized quadrangles that can be proved easily is that the point-collinearity graph of any GQ(s, t) is a strongly regular graph with parameters ((s+1)(st+1), s(t+1), s - 1, t+1). Using this fact we can restrict the parameters (s, t) for which a GQ(s, t) exists since there are many well known restrictions on the parameters of strongly regular graphs. Overall, we have the following result:

Let S = (\mathcal P, \mathcal L) be a GQ of order s, t. Then,

  1. |\mathcal P| = (s+1)(st+1) and |\mathcal L| = (t + 1)(st+1).
  2. The integer s + t divides st(s+1)(t+1).
  3. If s > 1 and t > 1, then t \leq s^2 and s \leq t^2.

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.

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Finite Geometry and tagged , , . Bookmark the permalink.

4 Responses to Point-Line Geometries

  1. Pingback: Introduction to finite geometry I | Anurag's Math Blog

  2. Pingback: My first publication | Anurag's Math Blog

  3. Pingback: Wenger graphs | Anurag's Math Blog

  4. Pingback: Bound on Ramsey numbers from finite geometry | Anurag's Math Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s