Bounding the Number of Edges in Permutation Graphs

Abstract

Given an integer $s\geq 0$ and a permutation $\pi \in S_n$, let $\Gamma_{\pi,s}$ be the graph on $n$ vertices $\{1, \ldots, n\}$ where two vertices $i < j$ are adjacent if the permutation flips their order and there are at most $s$ integers $k$, $i < k < j$, such that $\pi=[\ldots j \ldots k \ldots i\ldots]$. In this short paper we determine the maximum number of edges in $\Gamma_{\pi,s}$ for all $s\geq 1$ and characterize all permutations $\pi$ which achieve this maximum. This answers an open question of Adin and Roichman, who studied the case $s=0$. We also consider another (closely related) permutation graph, defined by Adin and Roichman, and obtain asymptotically tight bounds on the maximum number of edges in it.