Seminar of Graph Theory - Robert Jajcay (29.9.2016)

Thursday 29.9.2016 at 9:50, Lecture room M/213

---

Robert Jajcay (Univerzita Komenského, Bratislava):
Improving Moore bounds through counting cycles

Abstract:
The Cage Problem is the problem of finding the smallest $k$-regular graphs of girth $g$, called $(k,g)$-cages, for any parameter pair $k,g \geq 3$. Moore bounds are very natural lower bounds on the orders of cages that have been around since the introduction of the Cage Problem in the 1960's. Even though they are generally assumed to be rather poor predictors of the actual orders of cages, no significant improvements on these lower bounds are known to date.

In our talk, we present a technique for improving the Moore bounds based on counting cycles of lengths close to the girth $g$ in graphs of orders close to the Moore bounds. The numbers of these cycles together with certain divisibility constraints allow us to exclude specific orders of potential cages for infinite families of parameter pairs $k,g$. We present an overview of the use of this technique in the context of cages as well as some recent results obtained in collaboration with Tatiana Jajcayova and Slobodan Filipovski.

---