论文标题
循环系统几乎交叉相交的家庭
Circulant almost cross intersecting families
论文作者
论文摘要
令$ \ MATHCAL {F} $和$ \ MATHCAL {G} $为两个$ T $ - 均匀的子集的子集$ [K] = \ {1,2，...，K \} $，其中$ | \ Mathcal {f} | = | \ Mathcal {g} | $，让$ c $为两部分图的邻接矩阵，其顶点是$ \ Mathcal {f} $和$ \ Mathcal {g} $中的子集，并且在\ Mathcal {f} $和$ b \ nif $ a \ in c. b \ neq \ emptyset $。对$（\ MATHCAL {F}，\ MATHCAL {g}）$是$ q $ - 几乎交叉相交，如果$ c $的每个行和列都有$ q $ zeros。 我们考虑$ q $ - 几乎具有循环交叉点矩阵$ c_ {p，q} $的交叉相交对，由带有$ p> 0 $的列向量确定，然后是$ q> 0 $ zeros。这个矩阵家族包括一个极端的身份矩阵，另一个极端中的两分冠图的邻接矩阵。 我们给出$（\ Mathcal {f}，\ Mathcal {g}）$的构造，其相交矩阵为$ C_ {p，q} $，对于参数$ p $和$ q $的广泛值，在某些情况下，也可以证明上限匹配的上限。具体来说，我们证明了参数的以下值的结果：（1）$ 1 \ leq p \ leq 2t-1 $和$ 1 \ leq q \ leq Q \ leq k-2t+1 $。 （2）$ 2T \ leq p \ leq t^2 $和任何$ q> 0 $，其中$ k \ geq p+q $。 （3）$ p $在$ t $中为指数，对于足够大的$ k $。 使用第一个结果，我们表明，如果$ k \ geq 4t-3 $，则$ c_ {2t-1，k-2t+1} $是$ 0,1 $ -MATRIX $ -MATRIX $ a_ {k，t} $的最大隔离，$ k \ times k \ times k $ k \ times k $，其行和列的$ ys $ the $ ys $ ys $ the $ t $ t $ t $ t $ t $ t [ $ x $和列$ y $，仅当subset $ x，y $相交时。
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 $A\in \mathcal{F}$ and $B \in \mathcal{G}$ if and only if $A \cap B \neq \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 $k\times 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.
