CaltechAUTHORS
  A Caltech Library Service

Bounding the Number of Edges in Permutation Graphs

Keevash, Peter and Loh, Po-Shen and Sudakov, Benny (2006) Bounding the Number of Edges in Permutation Graphs. Electronic Journal of Combinatorics, 13 (1). R44. ISSN 1077-8926. http://resolver.caltech.edu/CaltechAUTHORS:KEEejc06

[img]
Preview
PDF
See Usage Policy.

149Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:KEEejc06

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.


Item Type:Article
Additional Information:[P.K.] [r]esearch supported in part by NSF grant. [P.-S.L.] [r]esearch supported in part by a Fannie and John Hertz Foundation Fellowship, an NSF Graduate Research Fellowship, and a Princeton Centennial Fellowship. [B.S.] [r]esearch supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, Alfred P. Sloan fellowship, and the State of New Jersey.
Issue or Number:1
Record Number:CaltechAUTHORS:KEEejc06
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:KEEejc06
Alternative URL:http://www.combinatorics.org/Volume_13/Abstracts/v13i1r44.html
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3199
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:19 May 2006
Last Modified:26 Dec 2012 08:53

Repository Staff Only: item control page