On maximal isolation sets in the uniform intersection matrix

Abstract: 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 - 2 t + 2

. Then we provide constructions of isolations sets in

A_{k, t}

for any

t g e q 2

, as follows: �egin{itemize} item If

k = 2 t + r

and

0 l e q r l e q 2 t - 3

, there exists an isolation set of size

2 r + 3 = 2 k - 4 t + 3

. item If

k g e q 4 t - 3

, there exists an isolation set of size

k

. end{itemize} The construction is maximal for

k g e q 4 t - 3

, since the Boolean rank of

A_{k, t}

is

k

in this case. As we prove, the construction is maximal also for

k = 2 t, 2 t + 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

(2 t c h o o s e t - 1) i m e s (2 t c h o o s e t - 1)

, for any

t g e q 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.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: On maximal isolation sets in the uniform intersection matrix