Körner and Malvenuto asked whether one can find (n/2) linear orderings (i.e., permutations) of the first n natural numbers such that any pair of them places two consecutive integers somewhere in the same position. This led to the notion of graph-different permutations. We extend this concept to directed graphs, focusing on orientations of the semi-infinite path whose edges connect consecutive natural numbers. Our main result shows that the maximum number of permutations satisfying all the pairwise conditions associated with all of the various orientations of this path is exponentially smaller, for any single orientation, than the maximum number of those permutations which satisfy the corresponding pairwise relationship. This is in sharp contrast to a result of Gargano, Körner, and Vaccaro concerning the analogous notion of Sperner capacity of families of finite graphs. We improve the exponential lower bound for the original problem and list a number of open questions. © 2010 Society for Industrial and Applied Mathematics.

Permutation capacities of families of oriented infinite paths / Graham, Brightwell; Gérard, Cohen; Fachini, Emanuela; Marianne, Fairthorne; Korner, Janos; Gabor, Simonyi; Agnes, Toth. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - STAMPA. - 24:2(2010), pp. 441-456. [10.1137/090765407]

Permutation capacities of families of oriented infinite paths

FACHINI, Emanuela;KORNER, JANOS;
2010

Abstract

Körner and Malvenuto asked whether one can find (n/2) linear orderings (i.e., permutations) of the first n natural numbers such that any pair of them places two consecutive integers somewhere in the same position. This led to the notion of graph-different permutations. We extend this concept to directed graphs, focusing on orientations of the semi-infinite path whose edges connect consecutive natural numbers. Our main result shows that the maximum number of permutations satisfying all the pairwise conditions associated with all of the various orientations of this path is exponentially smaller, for any single orientation, than the maximum number of those permutations which satisfy the corresponding pairwise relationship. This is in sharp contrast to a result of Gargano, Körner, and Vaccaro concerning the analogous notion of Sperner capacity of families of finite graphs. We improve the exponential lower bound for the original problem and list a number of open questions. © 2010 Society for Industrial and Applied Mathematics.
2010
's problem; andré; digraphs; graph capacities; permutations
01 Pubblicazione su rivista::01a Articolo in rivista
Permutation capacities of families of oriented infinite paths / Graham, Brightwell; Gérard, Cohen; Fachini, Emanuela; Marianne, Fairthorne; Korner, Janos; Gabor, Simonyi; Agnes, Toth. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - STAMPA. - 24:2(2010), pp. 441-456. [10.1137/090765407]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/228807
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact