On the minimum number of completely 3-scrambling permutations
From MaRDI portal
Publication:2476274
A family \({\mathcal P}\) of permutations on \([n]\) is completely \(3\)-scrambling if for any triple \((x_1,x_2,x_3)\) of distinct elements of \([n]\), there is a permutation \(\pi\in{\mathcal P}\) with \(\pi(x_1)<\pi(x_2)<\pi(x_3)\). It is proved that the minimum size of a completely \(3\)-scrambling family of pemutations on \([n]\) is at most \[ 2\log_2 n+(1+o(1))\log_2\log_2 n. \]
Recommendations
Cites work
- A note on scrambling permutations
- An extremal problem of \(d\) permutations containing every permutation of every \(t\) elements
- Chromatic number of Hasse diagrams, eyebrows and dimension
- Containment problems in high-dimensional spaces
- Families of \(k\)-independent sets
- scientific article; zbMATH DE number 426339 (Why is no real title available?)
- scientific article; zbMATH DE number 1445297 (Why is no real title available?)
- Min-wise independent permutations
- Minimal scrambling sets of simple orders
- On the order dimension of 1-sets versus k-sets
- On the sample size of k -restricted min-wise independent permutations and other k -wise distributions
- Scrambling permutations and entropy of hypergraphs
- The order dimension of the complete graph
Cited in
(8)- The covering threshold of a directed acyclic graph by directed acyclic subgraphs
- Perfect sequence covering arrays
- Sequence Covering Arrays and Linear Extensions
- On the minimum number of completely 3-scrambling permutations
- A note on scrambling permutations
- Scrambling permutations and entropy of hypergraphs
- Perfect and nearly perfect separation dimension of complete and random graphs
- Shattering k-sets with permutations
This page was built for publication: On the minimum number of completely 3-scrambling permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476274)
