Colloquium by Anurag Bishnoi (Freie Universität Berlin): New upper bounds on some cage numbers

Jun 11, 2018 | 04:00 PM s.t.

The cage problem asks for the smallest number c(k, g) of vertices in a k-regular graph of girth g. The (k, g)-graphs which have c(k, g) vertices are known as cages. While cages are known to exist for all integers k > 1 and g > 2, an explicit construction is known only for some small values of k, g and three infinite families for which g is 6, 8 or 12 and k − 1 is a prime power: corresponding to the generalized g/2-gons of order k − 1.

To improve the upper bounds on c(k, 6), c(k, 8) and c(k, 12), when k - 1 is not a prime power, one of the main techniques that has been used so far is to construct small (k, g) graphs by picking a prime power q ≥ k and then finding a small k-regular subgraph of the incidence graph of a generalized g/2-gon of order q. In this talk I will present new constructions in generalized quadrangles and hexagons which improve the known upper bound on c(k, 8) when k = p^{2h} and c(k, 12) when k = p^h, where p is an arbitrary prime. Moreover, we will see a spectral lower bound on the number of vertices in a k-regular induced subgraph of an arbitrary regular graph, which in particular will prove the optimality of a known construction in projective planes.


(Joint work with John Bamberg and Gordon Royle)

Time & Location

Jun 11, 2018 | 04:00 PM s.t.

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005 (ground floor)
Campus map

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)