## 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