Theorem. Assume that N is even and greater than zero. Let a be an an arbitrary element of S and Σ a minimal permutation cover of S − {a}. The set Σ' defined as

Σ' = {aσ, σa : σ in Σ}

is a minimal permutation cover of S.

Proof. Σ' is a permutation cover: let X be a subset of S; if a is not in X, X is covered by some permutation σ of Σ and a fortiori by σa in Σ'; if a belongs to X, some σ in Σ covers X − {a} and then aσ in Σ' covers X. Σ' is minimal as |Σ'| = 2|Σ| = 2 C(N − 1, floor((N − 1)/2)) = 2 C(N − 1, N/2 − 1) = C(N,N/2) = C(N,floor(N/2)), where the equalities depend on basic properties of binomial coefficients and the fact that N is even.

This result reduces the problem to N odd. The Hasse diagram of the powerset of S when N is odd looks like this (the particular case depicted is N = 5):

We name the layers of the diagram S_{0},...,S_{N}. S_{i} consists of the subsets of S with cardinality i. We have |S_{i}| = C(N,i). A permutation covers exactly one element of each S_{i}. Similarly, a tuple τ of n non-repeating elements covers exactly one element of each of S_{0},...,S_{n}. So, a minimal tuple cover of S_{0},...,S_{n} can be proved to have as many elements as the largest layer covered. The next result shows how to extend a minimal tuple cover of S_{0},...,S_{(N − 1)/2 }, which has cardinality C(N,(N − 1)/2) = C(N,floor(N/2)) and spreads over the bottom half of the powerset of S, to a minimal permutation cover of S.

Theorem. Assume that N is odd and set M = (N − 1)/2. Let Τ be a minimal set of M-tuples of non-repeating elements covering S_{0} U ... U S_{M}, and d : S_{M} → S_{M} a bijection with X ∩ d(X) = Ø for all X in S_{M}. The set Σ defined as

Σ = { τ·a·reverse(τ') : τ,τ' belong to Τ, range(τ') = d(range(τ)), a = S − range(τ) − range(τ')}

is a minimal permutation cover of S.

Proof. We see first that to each τ in Τ there corresponds exactly one permutation σ_{τ} of the form τ·a·reverse(τ') described above: since Τ is minimal each element of S_{M} is covered by one and only one element of Τ; so, for each τ there is exactly one τ' covering d(range(τ)). We prove now that Σ covers S: let X be a subset of S; if |X| ≤ M, X is covered by some τ in Τ and hence also by the associated σ_{τ}; if |X| > M, the set Y = S − X has |Y| ≤ M and is thus covered by some τ' in Τ; as we have seen, τ' univocally determines a permutation σ = τ·a·reverse(τ'), and σ obviously covers X, as all the elements of Y are packed at the tail of the permutation. Finally, Σ is minimal, since |Σ|= |Τ| and we saw before that |Τ| = C(N,floor(N/2)).

The mapping τ → σ_{τ} just defined can be described in a more algorithmic fashion as follows:

- Find the τ' in Τ covering d(range(τ)).
- Let a be the only element of S not present in τ nor τ'.
- σ
_{τ}:= τ·a·reverse(τ').

Note that the last theorem extends easily to N even: in this case, the permutations have the form τ·reverse(τ'), i.e. there is no middle element a. However, it is more efficient to reduce the case N even to N − 1 using the first theorem of this entry.

_{0}U ... U S

_{M}and finding a suitable bijection d : S

_{M}→ S

_{M}.

Can you develop something on Range Voting using for instance Spain's elections as an example?

ReplyDeletehttp://www.technologyreview.com/article/21172/