TOPICS
Search

Bellaterra Graph


The Bellaterra graph at level n has the 2^n binary words of length n as vertices, with edges defined by three involutions beta_a,beta_b,beta_c. These fix the empty word and satisfy beta_a(0w)=0beta_c(w), beta_a(1w)=1beta_b(w), beta_b(0w)=0beta_b(w), beta_b(1w)=1beta_c(w), and beta_c(xw)=(1-x)beta_a(w). All labels and edge multiplicities are retained. A fixed word contributes one to the corresponding diagonal entry of the adjacency matrix, giving row sum three (Kharlampovich and Vdovina 2026).

Kharlampovich and Vdovina (2026) report a graph diameter bound 2n+2, improving the previous quadratic-in-n bound to the sharp order Theta(n), where Theta is big-Theta notation. Their argument uses their recent Ramanujan result for this family.


See also

Adjacency Matrix, Aleshin Graph, Expander Graph

Explore with Wolfram|Alpha

References

Kharlampovich, O. and Vdovina, A. "Aleshin Graphs Are Expanders." 22 Oct 2026. https://arxiv.org/abs/2610.30662.

Cite this as:

Weisstein, Eric W. "Bellaterra Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BellaterraGraph.html

Subject classifications