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.
  • 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:
    1. 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).
    2. 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:
    1. Select(W) is a (n,k)-selective family.
    2. For c = k: Select(W) is a (n,k)-strongly selective family
    3. 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.
(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.
  • 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.
  • 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.
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}.

 

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]
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]
Title: On Computing Ad-hoc Selective Families
Authors: Andrea E.F. Clementi, Pilu Crescenzi, Angelo Monti, Paolo Penna, and Riccardo Silvestri
Year: 2001
Download:
PDF
Description: [Expand]
BibTex: [Expand]