A set of permutations L on a finite linearly ordered set Ω is said to be k-min-wise independent, k-MWI for short, if Pr (min (π(X)) = π(x)) = 1/|X| for every X ⊆ Ω such that |X| ≤ k and for every x ∈ X. (Here π(x) and π(X) denote the image of the element x or subset X of Ω under the permutation π, and Pr refers to a probability distribution on L, which we take to be the uniform distribution.) We are concerned with sets of permutations which are k-MWI families for any linear order. Indeed, we characterize such families in a way that does not involve the underlying order. As an application of this result, and using the Classification of Finite Simple Groups, we deduce a complete classification of the k-MWI families that are groups, for k ≥3. Copyright © Taylor & Francis Group, LLC

Cameron, P., Spiga, P. (2007). Min-wise independent families with respect to any linear order. COMMUNICATIONS IN ALGEBRA, 35(10), 3026-3033 [10.1080/00927870701404812].

Min-wise independent families with respect to any linear order

SPIGA, PABLO
Ultimo
2007

Abstract

A set of permutations L on a finite linearly ordered set Ω is said to be k-min-wise independent, k-MWI for short, if Pr (min (π(X)) = π(x)) = 1/|X| for every X ⊆ Ω such that |X| ≤ k and for every x ∈ X. (Here π(x) and π(X) denote the image of the element x or subset X of Ω under the permutation π, and Pr refers to a probability distribution on L, which we take to be the uniform distribution.) We are concerned with sets of permutations which are k-MWI families for any linear order. Indeed, we characterize such families in a way that does not involve the underlying order. As an application of this result, and using the Classification of Finite Simple Groups, we deduce a complete classification of the k-MWI families that are groups, for k ≥3. Copyright © Taylor & Francis Group, LLC
Articolo in rivista - Articolo scientifico
Linear order; Min-wise independent family; Permutation group; Algebra and Number Theory
English
2007
35
10
3026
3033
none
Cameron, P., Spiga, P. (2007). Min-wise independent families with respect to any linear order. COMMUNICATIONS IN ALGEBRA, 35(10), 3026-3033 [10.1080/00927870701404812].
File in 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/10281/101058
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
Social impact