BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: The cage problem asks for the smallest number c(k\, g) of vert
ices 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 integ
ers k >\; 1 and g >\; 2\, an explicit construction is known only for so
me small values of k\, g and three infinite families for which g is 6\, 8 o
r 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 th
at has been used so far is to construct small (k\, g) graphs by picking a p
rime power q ≥ k and then finding a small k-regular subgraph of the inciden
ce graph of a generalized g/2-gon of order q. In this talk I will present n
ew 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 boun
d 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 c
onstruction in projective planes. (Joint work with John Bamberg and Gor
don Royle)
DTSTAMP:20181105T173500
DTSTART:20180611T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin\n Institut für Informatik\n Takustr. 9\n
14195 Berlin\n room 005 (ground floor)
SEQUENCE:0
SUMMARY:Anurag Bishnoi (Freie Universität Berlin): New upper bounds on some
cage numbers
UID:89455378@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20180611-C-Bishnoi.html
END:VEVENT
END:VCALENDAR