Sharp vertex connectivity of the Markoff graphs modulo p
Abstract
For a prime p and k∈𝔽p, the generalized Markoff graph Gp,k is an undirected graph whose vertices are the solutions over the finite field 𝔽p of the normalized Markoff equation x12+x22+x32=x1x2x3+k, where two vertices are adjacent if they differ by a Vieta involution. The Markoff graph Gp is obtained from Gp,0 by removing the origin. The structure of Gp has been the subject of extensive study; in particular, a major breakthrough of Bourgain, Gamburd, and Sarnak established that Gp contains a giant connected component. Combined with Chen's remarkable divisibility theorem, this implies that Gp is connected for all sufficiently large primes p. In the same paper, Bourgain, Gamburd, and Sarnak further asked whether the family {Gp: primes p≥ 5} forms an expander family. This motivates us to investigate the robustness of connectivity in the Markoff graphs. The main result of this paper is proved in the general setting: for every prime p≥5 and every k∈𝔽p∖{4}, each connected component C of Gp,k with |V(C)|≥ 3 is $2$-connected. Reducing to the case k=0, we conclude that if the Markoff graph Gp is connected, then it is in fact $2$-connected. Consequently, the Markoff graph Gp is $2$-connected for all sufficiently large primes p. This is sharp in the sense that Gp is not $3$-connected for any prime p≥ 7.
Related
- Sharp asymmetric vertex-Ramsey properties of graphs
- Extremal spectral gap of regular graphs with bounded vertex connectivity
- Second largest eigenvalue thresholds for the vertex-connectivity of regular graphs
- Sharp Bounds on Torsional Rigidity of Metric Graphs with Signed Delta-Vertex Strengths
- Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
BibTeX
@misc{ma2026sharp,
title = {{Sharp vertex connectivity of the Markoff graphs modulo $p$}},
author = {Jie Ma and Mengxi Yang and Zichen Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.07880},
eprint = {2608.07880},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.07880},
}
RIS
TY - UNPB
TI - Sharp vertex connectivity of the Markoff graphs modulo p
AU - Jie Ma
AU - Mengxi Yang
AU - Zichen Yang
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2608.07880
UR - https://arxiv.org/abs/2608.07880
AB - For a prime p and k∈𝔽_p, the generalized Markoff graph G_p,k is an undirected graph whose vertices are the solutions over the finite field 𝔽_p of the normalized Markoff equation x_1^2+x_2^2+x_3^2=x_1x_2x_3+k, where two vertices are adjacent if they differ by a Vieta involution. The Markoff graph G_p is obtained from G_p,0 by removing the origin. The structure of G_p has been the subject of extensive study; in particular, a major breakthrough of Bourgain, Gamburd, and Sarnak established that G_p contains a giant connected component. Combined with Chen's remarkable divisibility theorem, this implies that G_p is connected for all sufficiently large primes p. In the same paper, Bourgain, Gamburd, and Sarnak further asked whether the family {G_p: primes p≥ 5} forms an expander family. This motivates us to investigate the robustness of connectivity in the Markoff graphs. The main result of this paper is proved in the general setting: for every prime p≥5 and every k∈𝔽_p∖{4}, each connected component C of G_p,k with |V(C)|≥ 3 is $2$-connected. Reducing to the case k=0, we conclude that if the Markoff graph G_p is connected, then it is in fact $2$-connected. Consequently, the Markoff graph G_p is $2$-connected for all sufficiently large primes p. This is sharp in the sense that G_p is not $3$-connected for any prime p≥ 7.
ER -