2024/12/13 by Herman Chau, Chau, Herman
Computer Science · Mathematics · #05A16 #Advanced Algebra and Logic #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2412.10532
openalex publication_date 2024/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The higher Bruhat orders B(n,k) were introduced by Manin-Schechtman to study discriminantal hyperplane arrangements and subsequently studied by Ziegler, who connected B(n,k) to oriented matroids. In this paper, we consider the enumeration of B(n,k) and improve upon Balko's asymptotic lower and upper bounds on |B(n,k)| by a factor exponential in k. A proof of Ziegler's formula for |B(n,n-3)| is given and a bijection between a certain subset of B(n,n-4) and totally symmetric plane partitions is proved. Central to our proofs are deletion and contraction operations for the higher Bruhat orders, defined in analogy with matroids. Dual higher Bruhat orders are also introduced, and we construct isomorphisms relating the higher Bruhat orders and their duals. Additionally, weaving functions are introduced to generalize Felsner's encoding of elements in B(n,2) to all higher Bruhat orders B(n,k).