On the unique-disjointness matrix

A unique-disjointness matrix is a $2^n\times 2^n$ matrix $D=D_n$ whose rows and columns are labeled by subsets $a$ of $[n]=\{1,\ldots,n\}$, and \[ D[a,b]=\begin{cases} 1 & \mbox{if $|a\cap b|=0$}\\ 0 & \mbox{if $|a\cap b|=1$}\\ \ast & \mbox{if $|a\cap b|>1$}\\ \end{cases} \] Let $ \disjpairs(n) := \{ (a,b) \in 2^{[n]} \times 2^{[n]} : a \cap b = \emptyset \} $ be the set of $1$-entries of $D_n$. Then \[ |\disjpairs(n)|=\sum_{i=0}^n\binom{n}{i}2^i=3^n\,. \] Call a subset $ R \subseteq \disjpairs(n) $ of $1$-entries valid if for every two distinct entries $(a,b)$ and $(a',b')$ in $R$, we have that $| a \cap b' | \neq 1$.

Lemma (Kaibel-Weltge [1]): If $R\subseteq \disjpairs(n)$ is valid, then $|R|\leq 2^n$.

Proof: Let $r(n)$ be the maximum cardinality of a valid subset of $\disjpairs(n)$. To show that $r(n)\leq 2^n$, it is enough to show that $r(n)\leq 2\cdot r(n-1)$. (Note that $r(0) = 1$ since the only valid subset of $ \disjpairs(0) $ is $ \{ ( \emptyset, \emptyset ) \} $.)

Towards this end, let $ R \subseteq \disjpairs(n) $ be valid (with $ n \geq 1 $) and let us define the following two sets: \begin{align*} R_1 & := \left( \{(a,b) \in R\colon n \in a\} \cup \{(a,b) \in R\colon (a \cup \{n\},b) \not\in R\} \right) \cap ([n] \times [n-1]) \\ R_2 & := \left( \{(a,b) \in R\colon n \in b\} \cup \{(a,b) \in R\colon (a,b \cup \{n\}) \not\in R\} \right) \cap ([n-1] \times [n]) \end{align*} Further, let us define the function $ f \colon R \to \disjpairs(n-1) $ with $ f(a,b) := (a \setminus \{n\}, b \setminus \{n\}) $. Since $ R_1 \subseteq R $ is valid and since $ R_1 \subseteq [n] \times [n-1] $, $ f(R_1) $ is valid. Similarly, $ f(R_2) $ is also valid. Further, by the definition of $ R_i $, $ f $ is injective on $ R_i $ for $ i = 1,2 $. By induction, we hence obtained that \[ |R_1| + |R_2| = |f(R_1)| + |f(R_2)| \leq 2\cdot r(n-1) = 2^n. \] Thus, it suffices to show that $ R \subseteq R_1 \cup R_2 $: Let $ (a,b) \in R $. Since $ a \cap b = \emptyset $, we have that $ (a,b) \subseteq ([n] \times [n-1]) \cup ([n-1] \times [n]) $. Thus, if $ n \in a \cup b $, we clearly have that $ (a,b) \in R_1 \cup R_2 $. It remains to show that for any $ (a,b) \in R $ with $ n \notin a \cup b $, we cannot have that $ (a \cup \{n\},b) \in R $ and $ (a,b \cup \{n\}) \in R $. Indeed, this is true since, otherwise, the validity of $ R $ would imply \[ 1 \neq |(a \cup \{n\}) \cap (b \cup \{n\})| = | \{n\} | = 1, \] a contradiction. $\Box$

A rectangle in the unique disjointness matrix $D_n$ if a submatrix with no $0$-entries, i.e. with only entries $1$ or $\ast$. Since the set of all entries of a rectangle must be valid, we obtain:

Corollary: The $1$-entries of $D_n$ cannot be covered by fewer than $1.5^n$ rectangles.

Reference:

[1] V. Kaibel and S. Weltge, A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially, arXiv preprint arXiv:1307.3543 (to appear in J. Comb. Ser. A)

S. Jukna, March 2014