Let $A_{k,t}$ be the matrix that represents the adjacency matrix of the intersection bipartite graph of all subsets of size $t$ of ${1,2,...,k}$. We give constructions of large isolation sets in $A_{k,t}$, where, for a large enough $k$, our constructions are the best possible. We first prove that the largest identity submatrix in $A_{k,t}$ is of size $k-2t+2$. Then we provide constructions of isolations sets in $A_{k,t}$ for any $tgeq 2$, as follows: begin{itemize} item If $k = 2t+r$ and $0 leq r leq 2t-3$, there exists an isolation set of size $2r+3 = 2k-4t+3$. item If $k geq 4t-3$, there exists an isolation set of size $k$. end{itemize} The construction is maximal for $kgeq 4t-3$, since the Boolean rank of $A_{k,t}$ is $k$ in this case. As we prove, the construction is maximal also for $k = 2t, 2t+1$. Finally, we consider the problem of the maximal triangular isolation submatrix of $A_{k,t}$ that has ones in every entry on the main diagonal and below it, and zeros elsewhere. We give an optimal construction of such a submatrix of size $({2t choose t}-1) times ({2t choose t}-1)$, for any $t geq 1$ and a large enough $k$. This construction is tight, as there is a matching upper bound, which can be derived from a theorem of Frankl about skew matrices.
Download