Geodesic
On some properties of min-wise independent families and groups of permutations
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 30-41 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Informally, a family $\mathcal{F}\subseteq S_n$ of permutations is $k$-restricted min-wise independent if for any $X\subseteq[n]$ with $|X|\leqslant k$, each $x\in X$ has an equal chance of being mapped to the minimum among $\pi(X)$. In the second section of this paper, the connection of min-wise independent families of permutations and independence on $l$-th minimum is studied. In the third section we present a way to construct $(k+1)$-restricted min-wise independent family from $k$-restricted min-wise independent family when $k$ is odd. As a corollary, we improve the existing upper bound on the minimal size of $4$-restricted min-wise independent family. In the last section we consider min-wise indepenent groups of permutations. 
@article{ZNSL_2004_316_a1,
     author = {V. Bargachev},
     title = {On some properties of min-wise independent families and groups of permutations},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {30--41},
     year = {2004},
     volume = {316},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a1/}
}
TY  - JOUR
AU  - V. Bargachev
TI  - On some properties of min-wise independent families and groups of permutations
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2004
SP  - 30
EP  - 41
VL  - 316
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a1/
LA  - ru
ID  - ZNSL_2004_316_a1
ER  - 
%0 Journal Article
%A V. Bargachev
%T On some properties of min-wise independent families and groups of permutations
%J Zapiski Nauchnykh Seminarov POMI
%D 2004
%P 30-41
%V 316
%U http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a1/
%G ru
%F ZNSL_2004_316_a1
V. Bargachev. On some properties of min-wise independent families and groups of permutations. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 30-41. http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a1/

[1] A. Z. Broder, “On the resemblance and containment of documents”, Proc. of Compression and Complexity of Sequences, 1998, 21–29

[2] A. Z. Broder, M. Charikar, A. M. Frieze, M. Mitzenmacher, “Min-wise independent permutations”, J. Comput. Syst., 60:3 (2000), 630–659 | DOI | MR | Zbl

[3] A. Z. Broder, M. Charikar, M. Mitzenmacher, “A Derandomization using min-wise independent permutations”, Proc. of RANDOM'98, Lecture Notes in Computer Science, 1518, Springer, 1998, 15–24 | MR

[4] A. Z. Broder, M. Mitzenmacher, “Completeness and robustness properties of min-wise independent permutations”, Random Structures and Algorithms, 18:1 (2001), 18–30 | 3.0.CO;2-M class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[5] P. J. Cameron, P. Spiga, “Min-wise independent families with respect to any linear order”, Communications in Algebra, 35 (2007), 3026–3033 | DOI | MR | Zbl

[6] C. Franchi, “Multiple transitivity and min-wise indendence in permutation groups”, Quaderni del Seminario Matematico di Brescia, 7 (2003), 1–9 | MR

[7] C. Franchi, M. Vsemirnov, “Min-wise independent groups”, European J. Combinatorics, 24:7 (2003), 855–875 | DOI | MR | Zbl

[8] J. Matoušek, M. Stojaković, “On restricted min-wise independence of permutations”, Random Struct. Algorithms, 23 (2003), 397–408 | DOI | MR | Zbl

[9] J. Tarui, T. Itoh, Y. Takei, “A nearly linear size 4-min-wise independent permutation family by finite geometries”, IEIC Technical Report, 103:119 (2003), 35–42 | MR

[10] M. Vsemirnov, Automorphisms of projective spaces and min-wise independent sets of permutations, Quaderni del Seminario Matematico di Brescia No 53, 2002, 1–16; (в печати)

[11] M. A. Vsemirnov, E. A. Girsh, E. Ya. Dantsin, S. V. Ivanov, “Algoritmy dlya propozitsionalnoi vypolnimosti i verkhnie otsenki ikh slozhnosti”, Zap. nauchn. semin. POMI, 277, 2001, 14–46 | MR | Zbl

[12] S. A. Norin, “Polinomialnaya nizhnyaya otsenka dlya razmera nezavisimogo po $k$ otnositelno minimuma mnozhestva perestanovok”, Zap. nauchn. semin. POMI, 277, 2001, 103–116 | MR | Zbl