Return to Question

The problem is:

Given a finite set $X$ with size $x$ and let $B$ denote 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.)

The problem is:

Given a finite set $X$ with size $x$ and let $B$ denote 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.)

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.)

The problem is:

Given a finite set $X$ with size $x$ and let $B$ denote 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.)

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 of blocks such that every element of $X$ is determined by the indicators of $B$ on $X$?

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.)

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.)