Abstract

Let s>=2 be an integer. A generalized triangle of order s is a bipartite (s+1)-regular graph of girth six and diameter three. It is also known as the point-line incidence graph of a finite projective plane of order s, and it is known to exist for all s which are prime powers. For each prime power s >= 9 which is not a prime, there exist at least two pairwise nonisomorphic generalized triangles or order s, and the number of isomorphism classes grows fast with s.

A generalized quadrangle of order s is a bipartite (s+1)-regular graph of girth eight and diameter four. It is known to exist for all s which are prime powers. Contrary to the case of generalized triangles, for each odd prime power s, only one (up to isomorphism) generalized quadrangle of order s is known.

We survey some recent results on generalized quadrangles, and study a relation between the existence of certain algebraically defined s-regular graphs of girth eight and diameter six and the existence of generalized quadrangles of order s. Some questions are reduced to analysis of certain algebraic varieties over finite fields and permutation polynomials. We will present some non-existence results and mention several open questions.