Discrete Mathematics Seminar - Small 3-regular graphs and 3-uniform hypergraphs of given girth

Dates

Wednesday, January 19, 2022 - 14:00 to 15:00

Speaker: Grahame Erskine (Open University)

Abstract: The cage problem is a long-standing topic in extremal graph theory, with the object being to determine the smallest possible d-regular graph of given girth g. As the girth g becomes large, the best constructions we have are asymptotically very far from the theoretical bound. There is a natural extension of this problem to the realm of hypergraphs, where in our case the girth is defined to be the length of the shortest Berge cycle in the hypergraph. We concentrate primarily on the case of 3-uniform hypergraphs, where each hyperedge contains exactly 3 vertices. By using analogues of techniques used in the graph version of the cage problem such as Cayley graphs, we find small examples of 3-uniform hypergraphs of given girth.

By considering duality in the hypergraph problem, we are able to apply our methods to different parameter sets. As a concrete example, our 3-uniform hypergraphs can be used to find new record smallest cubic (3-regular) graphs for a number of girths in the classical cage problem.

This is joint work with James Tuite (Open University).