Journal of Combinatorics

Volume 6 (2015)

Number 1–2

Bruhat graphs and pattern avoidance

Pages: 91 – 102

DOI: http://dx.doi.org/10.4310/JOC.2015.v6.n1.a6

Authors

Christopher Conklin (School of Physics & Astronomy, University of Minnesota, Minneapolis, Minn., U.S.A.)

Alexander Woo (Department of Mathematics, University of Idaho, Moscow, Id., U.S.A.)

Abstract

We characterize permutations whose Bruhat graphs can be drawn in the plane and those whose Bruhat graphs can be drawn on the torus. In particular, we show these properties are characterized by avoiding finitely many permutations.

Keywords

Bruhat graph, pattern avoidance, planar graph

2010 Mathematics Subject Classification

Primary 05C25. Secondary 05A05, 05E15.

Full Text (PDF format)

Published 20 March 2015