Post 2: The math of quadrangles

In this section, I’ll try to explain the mathematical ideas behind my project topic. But to keep things readable (this is a blog post, not a textbook), I’m going to sacrifice some thoroughness in favor of clarity. That is to say, I’m going to gloss over a lot of details so you don’t need a math degree to read this.

Let’s start with my project title: Using graph theoretic methods to search for new generalized quadrangles.

So there are things called generalized quadrangles, and I’m using graph theory to look for them. Now, what does this actually mean?

Firstly, graph theory. For our purposes, a graph is just a bunch of points, which may or may not be connected to each other via edges. An edge connects exactly two points together, and any two points that share an edge are called “adjacent” or “neighbors”. Graph theory is all about looking at graphs and figuring out their properties. You can then group graphs with similar properties into families of graphs. For example, the family of regular graphs is defined as all graphs in which every point has the same number of neighbors. Over time, graph theorists have discovered certain actions you can perform on a graph that modify its properties in a specific way, adding new tools to find new graphs to add to existing families.

Now, generalized quadrangles. A GQ is a geometry, which for our purposes is similar, but not quite identical, to graphs. They are also made of points, but points are connected by lines, which can pass through multiple points. Two lines can only intersect at a single point, and any two points that lie on the same line are called “collinear”. Any geometry that satisfies the following three properties is a GQ:

  1. Each point lies on the same number of lines.
  2. Each line passes through the same number of points.
  3. No triangles allowed.

By this definition, not only do rectangles count as GQ’s, but many more interesting geometries count as well.

So how do we connect the two? Well, if you construct a graph by taking a GQ’s points and adding an edge between every pair of collinear points, the resulting graph will not only be regular, but strongly regular. Such a graph is called theĀ collinearity graph of the GQ. In addition to having the properties of regular graphs, strongly regular graphs are a more exclusive club, with two additional restrictions: every pair of adjacent points has the same number of common neighbors, and every pair of non-adjacent points also has the same number of common neighbors. Using some clever counting tricks, you can calculate these properties of the resulting graph using only the properties of the GQ. Thus, there is a special relationship from GQ’s to strongly regular graphs, though as we will see the same is not true of the reverse direction.

The interesting thing is that there are still quite a few GQ’s that have not been found. For example, it is hypothesized that there exists a GQ with 6 points on each line, 8 lines through each point, and 216 total points, yet no one has been able to construct it so far. And despite us not knowing whether or not this GQ actually exists, we can still calculate the properties of its companion strongly regular graph, which would have 216 points, each point would have 40 neighbors, each pair of adjacent points would share 4 common neighbors, and each pair of non-adjacent points would share 8 common neighbors. A graph with these properties has just recently been found by Crnkovic et. al., but sadly it is not the collinearity graph of a GQ. However, some graph theory techniques, when applied to strongly regular graphs, can change its structure without changing its properties; we explored this route in the first part of our study.

Another route we pursued involves ovoids and star complements. From the paper Ovoids and bipartite subgraphs in generalized quadrangles by Makhnev, we know that should a GQ with 5 points per line and 13 lines per point, it can contain at most two ovoids. What ovoids actually are is not important at the moment. By assuming that the GQ contains at least one ovoid, we can adapt an existing search method to look for the GQ, and either we successfully find the GQ or we prove that should this GQ exist, it does not contain any ovoids.

I hope that this post has given you an adequate idea of what the basic principles behind my project are, and if you are interested in the methods we used to explore these ideas are I will be posting a third post shortly.