Abstract

Recently, Evra, Feigon, Maurischat, and Parzanchevksi defined a notion of Cayley incidence graphs to explicitly construct bipartite biregular expanders. Other interesting bipartite biregular graphs can be constructed with considerably less work, as for instance the difference set construction of the Fano plane can be viewed as a Cayley incidence graph. Cayley graphs are a key concept in algebraic graph theory, and this new notion gives a similar structure to biregular bipartite graphs, which we use to explore some of the theory. Since a biregular bipartite graph can be viewed as a uniform regular hypergraph, these Cayley incidence graphs relate to the notions of Cayley hypergraphs that have been defined by several authors previously. This is joint work with Arnbjörg Soffía Árnadóttir, Alexey Gordeev, Tovohery Randrianarisoa, and Joannes Vermant.