Bounding the Number of Edges in Permutation Graphs

Abstract

Given an integer s >= 0 and a permutation pi is an element of S-n, let Gamma(pi,s) be the graph on n vertices {1,..., 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 = [... j... k... i...]. In this short paper we determine the maximum number of edges in Gamma(pi,s) for all s >= 1 and characterize all permutations 7 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.

Files

Additional details