Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 If-.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 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 1.1 Given an integer s 0 and a permutation w 2 Sn Department of Mathematics Caltech Pasadena CA 91125. E-mail keevash@caltech.edu. Research supported in part by NSF grant. Department of Mathematics Princeton University Princeton NJ 08544. E-mail ploh@math.princeton.edu. 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@math.princeton.edu. Research supported in .
