{"id":"arxiv/2611.17237","url":"https://arxiv.org/abs/2611.17237","tags":["math.CO"],"score":0,"title":"Permutation patterns and higher connectivity in inversion graphs","domain":"math.CO","source":"arxiv","authors":["Emil Verkama"],"reviews":0,"subject":"math.CO","summary":"We prove that any permutation $π\\in S_n$ whose inversion graph is $k$-connected has at least $\\frac{k+1}{2}n - C$ inversions, where $C$ depends only on $k$. In particular, inversion graphs beat the general lower bound $\\frac{kn}{2}$ for the number of edges in a $k$-connected graph. Furthermore, we characterize the permutation patterns $σ$ having the property that if $π$ avoids $σ$, then the bound improves to $kn - C$. The collection of patterns is $\\mathrm{Av}(321, 2341, 4123)$, and it is independent of $k \\geq 2$. This work is motivated by a result of Linusson and Verkama (2025) that can be…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{}}