We consider graphs whose vertex set is the set of permutations of the first n natural numbers. Two such sequences are adjacent if for two different natural numbers they and their images in the two permutations occupy four different positions in some specific order, implying that the permutations are different. Several such relations are investigated, and for two of them the precise asymptotic magnitude of the largest clique in the graph is determined.
Interlocked permutations / Cohen, Gérard; Fachini, Emanuela; Körner, János. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 33:3(2019), pp. 1662-1668. [10.1137/18M1200683]
Interlocked permutations
Fachini, Emanuela;Körner, János
2019
Abstract
We consider graphs whose vertex set is the set of permutations of the first n natural numbers. Two such sequences are adjacent if for two different natural numbers they and their images in the two permutations occupy four different positions in some specific order, implying that the permutations are different. Several such relations are investigated, and for two of them the precise asymptotic magnitude of the largest clique in the graph is determined.| File | Dimensione | Formato | |
|---|---|---|---|
|
Cohen_Interlocked_2019.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
276.02 kB
Formato
Adobe PDF
|
276.02 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
