Combinatorics – Existence of Universal (n,k) Sets

combinatoricsdiscrete mathematicsextremal-combinatoricsprobability theorysequences-and-series

A set of $0-1$ strings of length $n$ is $(n,k)$–universal if, for
any subset of $k$ coordinates $S=\{i_1,\dots,i_k\}$, the projection
$$A\upharpoonright_S:=\{(a_{i_1},\dots,a_{i_k}):(a_1,\dots,a_n)\in
A\}$$ of $A$ onto the coordinates in $S$ contains all possible $2^k$
configurations.

Theorem 3.2 (Kleitman-Spencer 1973). If $\binom{n}{k}2^{k}(1-2^{-k})^r<1$ , then there is an $(n,k)$-universal
set of size $r$.

Proof. Let $A$ be a set of $r$ random $0-1$ strings of length $n$, each entry of which takes values $0$ or $1$ independently and with
equal probability $1/2$. For every fixed set $S$ of $k$ coordinates
and for every fixed vector $v\in \{0,1\}^k$,

$$\text{Pr}[v\notin A\upharpoonright_S]=\prod \limits_{a\in
A}\text{Pr}[v\neq a\upharpoonright_S]=\prod \limits_{a\in
A}(1-2^{-|S|})=(1-2^{-k})^r.$$ Since there are only $\binom{n}{k}2^k$
possibilities to choose a pair $(S,v)$, the set $A$ is not
$(n,k)$-universal with probability at most
$\binom{n}{k}2^k(1-2^{-k})^r$, which is strictly smaller than $1$.
Thus, at least one set $A$ of $r$ vectors must be $(n,k)$-universal,
as claimed.

This is an excerpt from Jukna's book "Extremal combinatorics" which I am reading to understand the essence of probabilistic method in combinatorial problems. I am not so familiar with probability theory but I know some basics so I'd like to clarify some moments from the proof of this theorem.

Questions.

  1. Usually authors do not write explicitly what the probability space is in certain examples but I am a beginner so I'd like to understand the details. We have $\{0,1\}^n$ – binary string of length $n$ and there $2^n$ such strings. From the context I see that the probability space is the following: $(\Omega,\text{Pr}),$ where $\Omega:=\{A\subset \{0,1\}^n: |A|=r\}$, i.e. $|\Omega|=\binom{2^n}{r}$ and probability distribution is uniform, i.e. $\text{Pr}[A]=\frac{1}{|\Omega|}$. Is my guess correct?

  2. What is $[v\notin A\upharpoonright_S]$? I guess it is some event, i.e. subset of $\Omega$, but I cannot write it explicitly. Can explain what is this please? Initially I thought that $[v\notin A\upharpoonright_S]$ is the same as $\{A\in \Omega: v\notin A\upharpoonright_S\}$ but it does make sense since in the next equality he is taking product over all element of $A$.

I have two questions so far because I need to understand those moments in order to move forward.
I'd be very thankful for help!

EDIT: 3) I am slightly confused with the definition of $(n,k)$ universal set. Let's take $n=3, k=2$ and consider the following set of binary strings of length $3$, say $\mathcal{A}=\{(1,0,0),(0,1,0),(1,1,0),(0,0,1)\}$. Then we have the following set of coordinates $S_{12}=\{1,2\},\ S_{13}=\{1,3\},\ S_{23}=\{2,3\}.$ One can check that $$A\upharpoonright_{S_{12}}=\{(1,0),(0,1),(1,1),(0,0)\},$$ $$A\upharpoonright_{S_{13}}=\{(1,0),(0,0),(0,1)\},$$ $$A\upharpoonright_{S_{23}}=\{(0,0),(1,0),(0,1)\}.$$
Can we say $\mathcal{A}$ is $(3,2)$-universal set?

Best Answer

Edit: After discussion with @PlayGame, it seems that confusion arises as in the proof, $A$ is defined to be a set, which would imply that the elements are distinct (and thus we lose the independence of strings). To make the proof sensical, we need to define $A$ as a vector of strings. Note that the proof remains correct, because a universal $(n,k)$-vector of size $r$ implies a universal $(n,k)$-set even smaller.

  1. This is correct Edit : In fact no, in your probability space, nothing tells you that $a_i\neq a_j~ \forall a_i, a_j \in A, i\neq j$, so $|\Omega| \neq \binom{2^n}{r}$. You have $rn$ binary values to choose, so you have $2^{rn}$ possible choices, so $|\Omega| = 2^{rn}$.
  2. Your guess was correct, you are probably confused by the fact that the product is on $A$, since $A$ is a random variable, but in fact, it does not really rely on $A$. If we write $A = \{a_1, a_2,\dots, a_r\}$, we could rewrite the product as $\prod \limits_{i\in 1,\dots,r}\text{Pr}[v\neq a_i\upharpoonright_S]$, and it no longer depends on $A$.
  3. No, because $A\upharpoonright_{S_{13}}$ does not contain every possible string of length $2$. Add $(1, 1, 1)$ and you get a universal set.
Related Question