# Circulant almost cross intersecting families

### Abstract

Let ℱ and *G* be two *t*-uniform families of subsets over [*k*] = {1, 2, ..., *k*}, where |ℱ| = |*G*|, and let *C* be the adjacency matrix of the bipartite graph whose vertices are the subsets in ℱ and *G*, where there is an edge between *A* ∈ ℱ and *B* ∈ *G* if and only if *A* ∩ *B* ≠ ∅. The pair (ℱ,*G*) is *q*-almost cross intersecting if every row and column of *C* has exactly *q* zeros.

We further restrict our attention to *q*-almost cross intersecting pairs that have a circulant intersection matrix *C*_{p, q}, determined by a column vector with *p* > 0 ones followed by *q* > 0 zeros. This family of matrices includes the identity matrix in one extreme, and the adjacency matrix of the bipartite crown graph in the other extreme.

We give constructions of pairs (ℱ,*G*) whose intersection matrix is *C*_{p, q}, for a wide range of values of the parameters *p* and *q*, and in some cases also prove matching upper bounds. Specifically, we prove results for the following values of the parameters: (1) 1 ≤ *p* ≤ 2*t* − 1 and 1 ≤ *q* ≤ *k* − 2*t* + 1. (2) 2*t* ≤ *p* ≤ *t*^{2} and any *q* > 0, where *k* ≥ *p* + *q*. (3) *p* that is exponential in *t*, for large enough *k*.

Using the first result we show that if *k* ≥ 4*t* − 3 then *C*_{2t − 1, k − 2t + 1} is a maximal isolation submatrix of size *k* × *k* in the 0, 1-matrix *A*_{k, t}, whose rows and columns are labeled by all subsets of size *t* of [*k*], and there is a one in the entry on row *x* and column *y* if and only if subsets *x*, *y* intersect.