ACO The ACO Seminar (2010-2011)

Nov. 18, 3:30pm, Wean 8220
Felix Lazebnik, University of Delaware
An Extremal Characterization of Projective Planes


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.

Back to the ACO home page