Cayley incidence graphs Cin(G,π), introduced in 2024 as a reformulation of the Cayley bigraphs of Evra–Feigon–Maurischat–Parzanchevski, form a biregular bipartite analogue of Cayley graphs built from a group G and a T-axiom-satisfying collection π of cells. The source paper poses the problem of characterizing, in terms of group structure, the two-way relationship between this new class and the classical class of Cayley graphs: which Cayley graphs arise as the underlying Cayley graph of a non-trivial Cin(G,π) (Question 10.1), which operations on groups and cells preserve the T-axiom so that examples can be built up (Question 10.2), and which regular Cayley incidence graphs are not themselves Cayley graphs (Question 10.3). Only scattered necessary conditions (connection-set partition, clique, and eigenvalue bounds), two construction lemmas, a census for groups of order at most 16, and a single non-Cayley example of order 21 are known. The characterization problem remains open.

Background

A Cayley graph Cay⁡(G,S)\operatorname{Cay}(G,S) is the graph whose vertices are the elements of a group GG, with gg adjacent to hh exactly when h−1gh^{-1}g lies in a fixed inverse-closed subset S⊆G∖{e}S\subseteq G\setminus\{e\} called the connection set; the group acts regularly (transitively with trivial stabilizers) on the vertices by left multiplication, so Cayley graphs are vertex-transitive, and they are a standard source of explicit expander and Ramanujan graphs. Evra, Feigon, Maurischat, and Parzanchevski (2023) introduced a biregular bipartite analogue, which they called Cayley bigraphs, while constructing the first explicit bipartite biregular expanders; Árnadóttir, Gordeev, Lato, Randrianarisoa, and Vermant (2024) reformulated the definition under the name Cayley incidence graphs and began developing its basic theory.

The definition is as follows. Let GG be a group (in practice finite) and let π={C1,…,Cℓ}\pi=\{C_1,\dots,C_\ell\} be a collection of subsets of GG, called cells, each of size kk and containing the identity ee, such that any two cells intersect exactly in ee and the collection satisfies the T-axiom: for every cell C∈πC\in\pi and every s∈Cs\in C, the left translate s−1Cs^{-1}C is again a cell of π\pi. The Cayley incidence graph Cin⁡(G,π)\operatorname{Cin}(G,\pi) is the bipartite graph whose two parts are the group elements GG and the set of left translates {gC:g∈G,C∈π}\{gC:g\in G,C\in\pi\}, with gg adjacent to gCgC; it is (ℓ,k)(\ell,k)-biregular, meaning every vertex in the first part has degree ℓ\ell and every vertex in the second part has degree kk. The union S(π)=⋃iCi∖{e}S(\pi)=\bigcup_i C_i\setminus\{e\} is inverse-closed, and Cay⁡(G,S(π))\operatorname{Cay}(G,S(\pi)) is called the underlying Cayley graph of Cin⁡(G,π)\operatorname{Cin}(G,\pi): every translate gCgC induces a kk-clique (a complete subgraph on kk vertices) in it, and for k=2k=2 the Cayley incidence graph is exactly the subdivision graph — each edge replaced by a path of length two — of the underlying Cayley graph. A Cayley incidence graph is non-trivial when ℓ≥2\ell\geq 2 and k≥3k\geq 3; following the source's standing convention, non-trivial Cayley incidence graphs are assumed connected, i.e. S(π)S(\pi) generates GG. The case ℓ=1\ell=1 forces the single cell to be a subgroup and gives the coset incidence graph.

Unlike Cayley graphs, which exist for every group, the T-axiom is restrictive: the census in the 2024 paper (its Table 1) lists, for every group of order 7 through 16, the number of non-isomorphic non-trivial Cayley incidence graphs, and many groups admit none, while groups of the same order can admit widely different numbers — the existence and abundance of admissible π\pi depends delicately on group structure. Three partial results frame the open questions. First, if Cay⁡(G,S)\operatorname{Cay}(G,S) is the underlying Cayley graph of a non-trivial Cin⁡(G,π)\operatorname{Cin}(G,\pi), then SS must partition into ℓ\ell cells of size k−1k-1, the graph must contain cliques of size kk, and (by the paper's Proposition 3.3) its least adjacency eigenvalue must be at least −ℓ-\ell; these necessary conditions are far from sufficient. Second, the paper gives two T-axiom-preserving construction lemmas — for direct products of Cayley incidence graphs and for certain intersections of cell collections within one group — but no other closure operations are known. Third, on the converse side, every regular Cayley incidence graph in the paper's small census is isomorphic to a Cayley graph (for example, the incidence graph of the Fano plane (the projective plane of order 2) arises as a Cayley incidence graph on Z7\mathbb{Z}_7 and is also a Cayley graph on the dihedral group of order 14), but the paper's Example 6.12 exhibits a non-abelian group of order 21, the semidirect product Z7⋊Z3\mathbb{Z}_7\rtimes\mathbb{Z}_3, with a regular Cayley incidence graph that is not a Cayley graph; the paper also relates the class to bi-Cayley graphs, i.e. graphs admitting a group acting semiregularly (with trivial vertex stabilizers) on exactly two orbits of vertices. How completely the two classes determine each other is unknown.

Problem Statement

Determine, in terms of the structure of the group, the two-way relationship between the class of non-trivial Cayley incidence graphs and the class of Cayley graphs, as posed in Questions 10.1–10.3 of the source paper:

  1. (Question 10.1) Characterize exactly which Cayley graphs Cay⁡(G,S)\operatorname{Cay}(G,S) arise as the underlying Cayley graph Cay⁡(G,S(π))\operatorname{Cay}(G,S(\pi)) of a non-trivial Cayley incidence graph Cin⁡(G,π)\operatorname{Cin}(G,\pi), i.e. connected and with ℓ≥2\ell\geq 2 cells of size k≥3k\geq 3 satisfying the T-axiom, obtaining a structural characterization, depending on the group, that accounts for the known necessary conditions — partition of SS into ℓ\ell cells of size k−1k-1, presence of kk-cliques, least eigenvalue at least −ℓ-\ell.

  2. (Question 10.2) The source poses this generically — "what operations on groups and cells preserve the T-axiom?" — beyond the known direct-product and intersection construction lemmas. Determine which such operations preserve the T-axiom, so that Cayley incidence graphs can be built up systematically.

  3. (Question 10.3) Characterize when a regular Cayley incidence graph is not isomorphic to any Cayley graph, identifying the structural obstructions beyond the single known order-21 example and building on the census data and the relationship with bi-Cayley graphs.

References

  1. Árnadóttir, Arnbjörg Soffía; Gordeev, Alexey; Lato, Sabrina; Randrianarisoa, Tovohery; Vermant, Joannes (2024/2025). Cayley incidence graphs. Preprint arXiv:2411.19428 (2024-11-29); journal version: Ars Mathematica Contemporanea (accepted manuscript, published 2025-12-09), DOI 10.26493/1855-3974.3510.a82. https://arxiv.org/abs/2411.19428 ; https://doi.org/10.26493/1855-3974.3510.a82
  2. Evra, Shai; Feigon, Brooke; Maurischat, Kathrin; Parzanchevski, Ori (2023/2025). Ramanujan Bigraphs (preprint arXiv:2312.06507, 2023-12-11); published version: Ramanujan bigraphs and applications, FOCS 2025, pp. 2088–2096, DOI 10.1109/FOCS63196.2025.00111. https://arxiv.org/abs/2312.06507 ; https://doi.org/10.1109/FOCS63196.2025.00111