2006/09/11 by Tamar Seeman, Seeman, Tamar
Engineering · Mathematics · #05C35 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C35
paper · pdf · doi:10.48550/arxiv.math/0609281
arxiv created 2006/09/11 · openalex publication_date 2006/09/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a permutation P in Sn, let G(P) be the graph on n vertices 1,...,n, where two vertices i<j are adjacent if i appears right of j in P and there are no integers k with i<k<j and k appearing between i and j in P. Let G'(P) be the graph obtained by dropping the condition that i appears right of j, i.e. two vertices are adjacent if the rectangle [i,P(i)] x [j,P(j)] is empty. In the study of the strong order on permutation, Adin and Roichman introduced these graphs and computed their maximum number of edges. We generalize these results to the Weyl group of signed permutations Bn, working with graphs on vertices -n,...,n\0, using new variants of a classical theorem of Turan.