Bounding the number of edges in permutation graphs (Q2500963)

Summary: Given an integer \(s\geq 0\) and a permutation \(\pi \in S_n\), let \(\Gamma_{\pi,s}\) be the graph on \(n\) vertices \(1, \dots, 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=[\dots j \dots k \dots 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.