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 &gt\; 1 and g &gt\; 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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20180611-C-Bis
 hnoi.html
END:VEVENT
END:VCALENDAR