The (weak) Bruhat graph 
of order 
,
also called the bubble-sort graph (Araki and Kikuchi 2007), is the simple
graph having all permutations of 
as vertices, and
with a graph edge between pairs of permutations
that differ by an adjacent transposition. The 
-Bruhat graph is the Cayley
graph of the symmetric group 
generated by adjacent transpositions
(Hurlbert 2011). The Bruhat graphs of orders 1 to 4 are illustrated above.
Bruhat graphs are antipodal.
The permutations and edges corresponding to 
are illustrated above.
Special cases are summarized in the following table.
The 
-Bruhat graph is planar
for 
to 4. For 
, 6, ..., upper bounds on the ordinary crossing
numbers are 120, 4942, ... (E. Weisstein, Nov. 4, 2026), obtained using
QuickCross (Clancy et al. 2019), where each search stream is set to continue
until one week has elapsed without strictly improving its own best crossing count.
Zheng et al. (2016) gave upper bounds of 120 and 5196 for 
and 
, respectively, so while the QuickCross results match the
former bound, they improve the latter.
."
Util. Math. 101, 309-328, 2016.