On disjointly representable sets (Q790112): Difference between revisions

A set-system \(E_ 1,...,E_ k\subset X\) is disjointly representable if there exist \(x_ 1,...,x_ k\in X\) such that \(x_ i\in E_ j\) if and only if \(i\neq j\). f(r,k) is the maximal size of an r-uniform system containing no k disjointly representable members. It is proved that \(f(r,3)=\lfloor(r+2)/2\rfloor \cdot \lceil(r+2)/2\rceil\), and the (unique) extremal system is described. For \(k>3\) asymptotically sharp bounds are given. The sets \(E_ 1,...,E_ k\subset X\) are disjointly t- representable if there are t-element \(X_ i\subset E_ i\) such that \(X_ i\cap E_ j=\emptyset\) whenever \(i\neq j\). \(f_ t^{\ell}(r,k)\) is the maximum size of an r-uniform system without k disjointly t- representable members and without a \(\Delta\)-system of size \(\ell\) and with kernel of cardinality \(>r-t\). Then \(cr^{(k-1)t}<f_ t^{\ell}(r,k)<c'r^{kt-1}\) where \(0<c,c'\) depend on k,\(\ell,t\). An analogue of Sauer's theorem on traces of systems is also proved.