Permutation patterns and higher connectivity in inversion graphs
Source: arxiv.org/abs/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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.17237
curl -X POST /api/v1/records/arxiv/2611.17237/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.17237/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'