DMS Combinatorics Seminar

Speaker: Xiaonan Liu (Vanderbilt University)

Title: Counting \(k\)-cycles in \(5\)-connected planar triangulations

We show that every \(n\)-vertex \(5\)-connected planar triangulation has at most \(9n-50\) many cycles of length \(5\) for all \(n\geq 20\) and this upper bound is tight.  We also show that for every \(k\geq 6\), there exists some constant \(C(k)\) such that for sufficiently large \(n\), every  \(n\)-vertex \(5\)-connected planar graph has at most \(C(k) \cdot n^{\lfloor k/3 \rfloor}\) many cycles of length \(k\). This upper bound is asymptotically tight for all \(k\geq 6\).

Joint work with Gyaneshwar Agrahari and Zhiyu Wang.