Counting k-gons in Finite Projective Planes

Recently, the question, whether the number of k-gons embedded in a projective plane is a function of its order q only, was posed. Number of k-gons is a polynomial in q for the values of k = 3, 4, 5, 6. These polynomials were explicitly derived. It was conjectured that the number of 10-gons would be different for non-isomorphic planes.

Finite projective planes may be naturally represented as their point-line incidence graphs whose 2k-cycles correspond exactly to k-gons of the plane. This interpretation allows one to count polygons by means of cycle counting methods. Previously known algorithms cannot be used to examine the cases k = 7, 8, 9, 10 because of their high computational complexity.

In our recent work, a method to derive the explicit formulae for counting fixed length cycles in undirected graphs was proposed. Due to particular features of planes' graphs - they are bipartite and 4-cycle-free, - we could derive specific expressions for counting up to 20-cycles in graphs with such properties.

By means of the specialized explicit formula, the number of 20-cycles in 4-cycle-free bipartite graph can be counted in O(n^5) time, where n is the order of the graph. We performed computations for all projective planes of orders 9 and 16. The orders of their graphs are 182 and 546. All planes of order 9 or 16 were proved to have the same number of k-gons up to k = 10.

It is possible to evaluate the explicit formulae symbolically. By analytical transformations, we derived polynomials which express the numbers of k-gons, for k <= 10, as functions of q. These new polynomials discovered asymptotical behaviour of the number of k-gons.

The explicit formulae approach is applicable to the problem of counting subgraphs isomorphic to given graph. Thereby we counted embeddings of the finite projective plane of order 2 in other projective planes of order at most 16. The results were found to be different for non-isomorphic planes. Basing on the structure of the explicit formulae for counting cycles, we conjectured that the numbers of 14-gons would differ for non-isomorphic planes.