Nov. 18, 3:30pm, Wean 8220

Felix Lazebnik, University of Delaware

An Extremal Characterization of Projective Planes

Felix Lazebnik, University of Delaware

An Extremal Characterization of Projective Planes

Abstract:

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.