Skip to main content
2 of 4
added 243 characters in body; edited body
LeechLattice
  • 9.5k
  • 2
  • 23
  • 57

Distinguishing points by sets of given size

The problem is:

Given a finite set $X$ with size $x$ and let $B$ be a family of $k$-element subsets of $X$, called blocks. What is the smallest possible number $n$ of blocks such that every element of $X$ is determined by the indicators of $B$ on $X$?

In other words, what is the smallest number $n$ such that the mapping $f:X→\text{\{}0,1\text{\}}^n$ defined by $f_ i(X)=b_i(X)$ is injective, where $f_i(X)$ is the ith component of $f(X)$, and $b_i$ is the indicator function of $B_i$?

Does this problem has a name? What are the known upper/lower bounds? Links to papers or webpages are also welcome.

(This question was asked to me by a Chinese friend.)

LeechLattice
  • 9.5k
  • 2
  • 23
  • 57