Post 3: The method

In the previous post, I laid out two routes that we explored over the course of our project: reverse-engineering an existing graph to find a similar graph that corresponds to a generalized quadrangle, and assuming the existence of an ovoid in order to adapt an existing search method. I’ll go over what I did for each of these, and I’ll start out by mentioning that all my code is available in my GitHub repository, which I’ll link at the end. Like my last post, I will be leaving out some of the more technical details that complicate the explanation without offering any important context or information in return.

So first, the reverse-engineering method. We already know that Crnkovic et. al.’s graph has the properties that we’re looking for, but not the structure. There are graph theory methods available that change the structure of a graph without disturbing its properties, one of which is known as Godsil-McKay switching. The gist of this switching method is that if you can split a graph into several partitions that fulfill a specific set of properties, you can then remove all edges that span between two partitions and add edges between all points that did not have a neighbor in another partition and end up with a graph with the same properties as the original. In essence, you are creating a limited area in which all edges are switched to non-edges and all non-edges are switched to edges. We hoped that by trying several partitioning methods on the Crnkovic graph, we might be able to create a new graph with the same properties but a different structure. To do this, we made use of the GAP programming language with the GRAPE package to provide functions to create and manipulate graphs. Based on work done by Abiad and Haemers in their paper Switched symplectic graphs and their 2-ranks, I created a program that takes in the Crnkovic graph and a list describing the partition method. We then ran this program for all 2152 different partitions consisting of 4 points, and did not find any new graphs. To expand the search space to all partitions created by 6 points would be computationally infeasible, so we stopped here.

Another switching method we experimented with was based on Crnkovic et. al.’s method of finding their graph. Based on their paper, we created a program that searches for graphs in certain promising groups and subgroups with a specified number of points, with each point being represented by a right coset in the group. This method did not turn up any interesting graphs for 216, 225, or 245 points.

The other route we explored was assuming the presence of an ovoid. In doing so, we could use the star complement method used previously by multiple graph theory studies to essentially “grow” a graph from a core subgraph. To do this, I wrote a program in Python with the NumPy and Numba packages for faster numerical processing. The program takes in a list of vertices to test, and attempts to add each one to our core subgraph. If it fulfills all the conditions required, it is added; otherwise it fails and the program moves on to the next vertex to test. Our primary concern is that the unfiltered search space for potential new vectors is massive and would take decades to crunch through, and we are currently in the process of cutting out sections of the search space.