{"id":"arxiv/2602.16625","url":"https://arxiv.org/abs/2602.16625","tags":["math.CO"],"score":0,"title":"Comparability of random permutations in the strong Bruhat order","domain":"math.CO","source":"arxiv","authors":["Nicholas Christo","Marcus Michelen"],"reviews":0,"subject":"math.CO","summary":"The (strong) Bruhat order for permutations provides a partial ordering defined as follows: two permutations are comparable if one can be obtained from the other by a sequence of adjacent transpositions that each increase the number of inversions by $1$. Given two random permutations, what is the probability that they are comparable in the Bruhat order? This problem was first considered in a 2006 work of Hammett and Pittel, which showed an exponential lower bound and a polynomial upper bound. The lower bound was very recently improved to the subexponential bound of $\\exp(-n^{1/2 + o(1)})$ by…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-18","reactions":{}}