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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-12 Page: https://delphi.science/r/arxiv/2611.17237 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…