×

Interesting systems. (English) Zbl 0955.05110

Summary: An intersecting system of type \((\exists,\forall,k,n)\) is a collection \(\mathbb{F}= \{{\mathcal F}_1,\dots,{\mathcal F}_m\}\) of pairwise disjoint families of \(k\)-subsets of an \(n\)-element set satisfying the following condition. For every ordered pair \({\mathcal F}_i\) and \({\mathcal F}_j\) of distinct members of \(\mathbb{F}\) there exists \(A\in{\mathcal F}_i\) that intersects every \(B\in{\mathcal F}_j\). Let \(I_n(\exists,\forall,k)\) denote the maximum possible cardinality of an intersecting system of type \((\exists,\forall,k,n)\). Ahlswede, Cai and Zhang conjectured that for every \(k\geq 1\), there exists \(n_0(k)\) so that \(I_n(\exists,\forall,k)= \left(\begin{smallmatrix} n-1\\ k-1\end{smallmatrix}\right)\) for all \(n> n_0(k)\). Here we show that this is true for \(k\leq 3\), but false for all \(k\geq 8\). We also prove some related results.

MSC:

05D05 Extremal set theory
PDFBibTeX XMLCite
Full Text: DOI