论文标题
以$ 1 $ - 交叉相交套装对系统的限制
A bound for $1$-cross intersecting set pair systems
论文作者
论文摘要
Bollobás的一个众所周知的结果说，如果$ \ {（a_i，b_i）\} _ {i = 1}^m $是一个设定的对系统，以至于$ | a_i | \ le a $和$ | b_i | \ le b $ for $ 1 \ le i \ le m $，$ a_i \ cap b_j \ ne \ emptyset $ i时，仅当$ i \ ne j $，然后$ m \ le {a+b \ select a} $。 Füredi，Gyárfás和Király最近通过$ | a_i \ cap b_j |对此类系统进行了研究。 =所有$ i \ ne j $的1 $。确认了他们的猜想，我们表明这种额外的条件允许通过恒定因素改善上限（至少）。
A well-known result of Bollobás says that if $\{(A_i, B_i)\}_{i=1}^m$ is a set pair system such that $|A_i| \le a$ and $|B_i| \le b$ for $1 \le i \le m$, and $A_i \cap B_j \ne \emptyset$ if and only if $i \ne j$, then $m \le {a+b \choose a}$. Füredi, Gyárfás and Király recently initiated the study of such systems with the additional property that $|A_i \cap B_j| = 1$ for all $i \ne j$. Confirming a conjecture of theirs, we show that this extra condition allows an improvement of the upper bound (at least) by a constant factor.
