TOPICS
Search

Bruhat Graph


BruhatGraphs

The (weak) Bruhat graph B_n of order n is the simple graph having have all permutations of {1,2,...,n} as vertices, and with an edge between pairs of permutations that differ by an adjacent transposition. The n-Bruhat graph is the Cayley graph of the symmetric group S_n generated by adjacent transpositions (Hurlburt 2011). The Bruhat graphs of orders 1 to 4 are illustrated above.

Bruhat graphs are antipodal.

BruhatGraph4

The permutations and edges corresponding to B_4 are illustrated above.

Special cases are summarized in the following table.


See also

Cayley Graph, Transposition, Truncated Octahedral Graph

Explore with Wolfram|Alpha

References

Hurlburt, G. "A Linear Optimization Technique for Graph Pebbling." 28 Jan 2011. https://arxiv.org/abs/1101.5641.

Cite this as:

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

Subject classifications