Delphi.science

Permutation patterns and higher connectivity in inversion graphs

Source: arxiv.org/abs/2611.17237

Emil Verkama

arXivarxiv/2611.17237Nov 12, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'