The ACO Seminar (2010-2011)
, 3:30pm, Wean 8220
, 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