Upper bounds for the monotone rank of the unique disjointness matrix

Abstract

It is shown that the $\mathsf{OR}$-rank (covering rank) of the $2^n\times 2^n$ unique disjointness matrix is $n^{O(1)}(3/2{)}^n$, hence the known lower bound $1.5^n$ turns out to be essentially tight. By the way, an upper bound $1.89^n$ is obtained for the $\mathsf{SUM}$-rank (partition rank) of this matrix.

7 pages (in English); 7 pages (in Russian)