# Multiselector Definitions

(n,c,k)-multiselector

Let W = W_1, W_2, ..., W_m be a set of functions that map from [n] to [c] U {\bot}. W is a (n,c,k)-multiselector if every subset S of [n], such that |S| = k, there exists a subset S' of S, such that |S'| = min{c,k}, and there exists W_i in W that maps each element in S' to a unique element in [c] and each element in S \ S' to \bottom.

Let W = W_1, W_2, ..., W_m be a set of functions that map from [n] to [c] U {\bot}. W is a (n,c,k)-multiselector if every subset S of [n], such that |S| = k, there exists a subset S' of S, such that |S'| = min{c,k}, and there exists W_i in W that maps each element in S' to a unique element in [c] and each element in S \ S' to \bottom.

- Best Lower: For k = c: Omega(e^c)
- Best Existential Upper: For k = c: O[e^c c log(n/c)]
- Best Explicit Upper: For k = c: O(c! log^(c)n)
- Our previous definition of an (n,c)-multiselector is generalized as an (n,c,c)-multiselector.
- There is an interesting conceptual split with the
(n,r,k)-selectors
In a multiselector, c of k must be selected, and the
*remaining*k - c must all be*non-selected*(e.g., mapped to the same set \bottom). In a selector, c of k must be selected, but we don't care what happens to the other k - c. - Converting multiselector to selectors.
In order to formally compare multiselectors to selectors we
need a way of transforming them into the same form.
The three selector types defined below are all in the form
of binary arrays, with the column representing the elements
and the rows representing the sets. The value 1 in position (x,y)
indicates element y is in set x.
Given multiselector W, let
*Select(W)*equal the selector object constructed as follows:- Covert each W_i in W into a binary matrix with n columns and c+1 rows. Set (x,y) = 1 if and only if W_i maps y to x (let c+1 represent \bottom).
- Append all m matrices to get one large binary matrix with n columns and (c+1)m rows.

- Relationship with Selectors.
Let W equal a (n,c,k)-multiselector (with c,k >0). We know:
- Select(W) is a (n,k)-selective family.
- For c = k: Select(W) is a (n,k)-strongly selective family
- Select(W) is a (n,c,k)-selector.

# Selector Definitions

(n,k)-selective family

A family F of subsets of [n] is (n,k)-selective if for every non-empty subset Z of [n], such that |Z| <= k, there is a set f in F that intersects Z at exactly one element.

A family F of subsets of [n] is (n,k)-selective if for every non-empty subset Z of [n], such that |Z| <= k, there is a set f in F that intersects Z at exactly one element.

- Best Lower: k/24 log(n/k)
- Best Existential Upper: O(k log(n/k))
- Best Explicit Upper: O(k log(k) log(n/k))

(n,k)-strongly-selective family

A family F of subsets of [n] is (n,k)-strongly-selective if for every non-empty subset Z of [n], such that |Z| <= k, and for every z in Z, there is a set f in F that intersects Z at only element z.

A family F of subsets of [n] is (n,k)-strongly-selective if for every non-empty subset Z of [n], such that |Z| <= k, and for every z in Z, there is a set f in F that intersects Z at only element z.

- Best Lower: Omega((k^2/log(k)) log(n)) (3 <= k <= sqrt{2n} - 1, else n)
- Best Existential Upper: O(k^2 log(n/k))
- Best Explicit Upper:
O(k^2 log^2(n))

*[from a 1964 paper on superimposed codes by Kautz and Singelton]* - Strongly-selective families are another from
of
*superimposed codes*, which are also sometimes called*cover free families*.

(n,r,k)-selectors

Given integers k, r, n, with 1 <= r <= k <= n, we say that a boolean matrix M with t rows and n columns is a (k,m,n)-selector if any submatrix of M obtained by choosing k out of n arbitrary columns of M contains at least r distinct rows of the identity matrix I_k.

Given integers k, r, n, with 1 <= r <= k <= n, we say that a boolean matrix M with t rows and n columns is a (k,m,n)-selector if any submatrix of M obtained by choosing k out of n arbitrary columns of M contains at least r distinct rows of the identity matrix I_k.

- Best Lower: Omega(min[n, (r-1)^2/(k-r+1) log(n/(k-r+1))/log((r-1)/(k-r+1))])
- Best Existential Upper: O( (k^2)/(k-r+1) log(n/k) )
- Best Explicit Upper:
O(min{n, (k^2)/(k-r+1) polylog(n)})

*[from not yet published Chelbus and Kowalski paper]* - A related definition is to say that a set F of t subsets of [n] is a (k,m,n)-selector if for any k-subset Z of [n], for every z in Z there is a set f in F that intersects Z at only element z.
- A (n,k)-strongly-selective family is cleary also a
(k,k,n)-selector. The opposite also holds.
Given a set smaller than k, we know that all elements
will be isolated, because this is true if we add any
arbitrary extra elements to fill out set to k.
These things are, therefore, equivalent.
In other words, the fact that it has to isolate
*as many as k elements*, means that isolating smaller subset comes for for free (no extra work is required to isolate those).

(n,k,l)-intersection free

Let l <= k <= n. A family F of k-subsets of [n] is (n,k,l)-intersection free if F1 does not intersect F2 at exactly l points for every pair F1 and F2 from F.

Let l <= k <= n. A family F of k-subsets of [n] is (n,k,l)-intersection free if F1 does not intersect F2 at exactly l points for every pair F1 and F2 from F.

r-different sequences

Two sequences x and y of equal length over the alphabet {0} U [r] are r-different if for any z in [r] there is a coordinate i for which {x[i], y[i]} = {z,0}.

Two sequences x and y of equal length over the alphabet {0} U [r] are r-different if for any z in [r] there is a coordinate i for which {x[i], y[i]} = {z,0}.

- Best Lower: Omega((r/log r)log(n))
- Best Existential Upper:
- Best Explicit Upper:

# Selector Papers

Title:
Distributed broadcast in radio networks of unknown topology

Authors: Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri

Year: 2003

Download: PDF

Description: [Expand]

BibTex: [Expand]

Authors: Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri

Year: 2003

Download: PDF

Description: [Expand]

BibTex: [Expand]

Title:
Generalized Framework for Selectors with Applications in Optimal Group Testing

Authors: Annalisa De Bonis, Leszek Gasieniec, and Ugo Vaccaro

Year: 2003

Download: PDF

Description: [Expand]

BibTex: [Expand]

Authors: Annalisa De Bonis, Leszek Gasieniec, and Ugo Vaccaro

Year: 2003

Download: PDF

Description: [Expand]

BibTex: [Expand]