The ACO Seminar (2010-2011)

For a given integer n, consider a family of all n by n bipartite graphs with no 4-cycles. Which graphs from the family contains the greatest number of 8-cycles? We show that if n = q^2 + q + 1 > 156, the incidence graph of a projective plane of order q, when it exists, has the maximum number of cycles of length eight. This characterizes projective planes as the partial planes with the maximum number of quadrilaterals. Several generalizations of this question, and related results will be discussed.

This is a joint work with Stefaan De Winter and Jacques Verstraete.