Let $mathcal{F}$ and $mathcal{G}$ be two $t$-uniform families of subsets over $[k] = {1,2,...,k}$, where $|mathcal{F}| = |mathcal{G}|$, and let $C$ be the adjacency matrix of the bipartite graph whose vertices are the subsets in $mathcal{F}$ and $mathcal{G}$, and there is an edge between $Ain mathcal{F}$ and $B in mathcal{G}$ if and only if $A cap B eq emptyset$. The pair $(mathcal{F},mathcal{G})$ is $q$-almost cross intersecting if every row and column of $C$ has exactly $q$ zeros. We consider $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 $(mathcal{F},mathcal{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 leq p leq 2t-1$ and $1 leq q leq k-2t+1$. (2) $2t leq p leq t^2$ and any $q> 0$, where $k geq p+q$. (3) $p$ that is exponential in $t$, for large enough $k$. Using the first result we show that if $k geq 4t-3$ then $C_{2t-1,k-2t+1}$ is a maximal isolation submatrix of size $ktimes 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.
Download