Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Bounding the number of edges in permutation graphs. | Bounding the number of edges in permutation graphs Peter Keevash Po-Shen Loh t Benny Sudakov Ỉ Submitted Dec 10 2005 Accepted Apr 27 2006 Published May 5 2006 Mathematics Subject Classification 05C35 20B30 Abstract Given an integer s 0 and a permutation K 2 Sn let 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 K . j . k. i. . In this short paper we determine the maximum number of edges in r s for all s 1 and characterize all permutations K 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. 1 Introduction We begin with standard notation. Let w 2 Sn be a permutation and let w i denote the image of i where we consider w as a bijection from n 1 . n to itself. We express permutations as linear arrangements of n by listing images in order as w 1 . w n . For example 2 5 1 3 4 represents the permutation that maps 1 2 2 5 3 1 4 3 5 4. Note that in the context of list notation w-1 i denotes the position of i in the permutation when w is written in a list form and w-1 i w-1 j has the simple interpretation that in w the number i appears before the number j. Definition Given an integer s 0 and a permutation w 2 Sn Department of Mathematics Caltech Pasadena CA 91125. E-mail keevash@. Research supported in part by NSF grant. Department of Mathematics Princeton University Princeton NJ 08544. E-mail ploh@. Research supported in part by a Fannie and John Hertz Foundation Fellowship an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. Department of Mathematics Princeton University Princeton NJ 08544 and Institute for Advanced Study Princeton. E-mail bsudakov@. Research supported in .
