Expansion Properties of Levi Graphs

Dominic Lanphier1, Christopher Miller2, Jason Rosenhouse3, Amber Russell4
1 DEPT. OF MATHEMATICS, WESTERN KENTUCKY UNIV., BOWLING GREEN, KY 42101, USA,
2DEPT. OF MATHEMATICS, FAIRFIELD UNIVERSITY, FAIRFIELD, CT 06824, USA
3DEPT. OF MATH. AND STAT., JAMES MADISON UNIV., HARRISON- BURG, VA 22801, USA,
4DEPT. OF MATH. AND STAT., MISSISSIPPI STATE UNIV., MISS. ST, MS 39762, USA

Abstract

The Levi graph of a balanced incomplete block design is the bipartite graph whose vertices are the points and blocks of the design, with each block adjacent to those points it contains. We derive upper and lower bounds on the isoperimetric numbers of such graphs, with particular attention to the special cases of finite projective planes and Hadamard designs.