On the maximum number of qualitative independent partitions (Q1121889)

Let X be an n-element set and for \(i=1,...,N\), let \(P_ i=(P^ 1_ i,...,P^ t_ i)\) be a partition of X into t disjoint sets. The collection \({\mathcal P}=\{P_ i:\quad 1\leq i\leq N\}\) is called qualitatively r-independent if for every possible choice of distinct \(i_ 1,...,i_ r\) \((1\leq i_ k\leq N)\) and arbitrary \(j_ 1,...,j_ r\) \((1\leq j_ k\leq t)\) \[ P^{j_ 1}_{i_ 1}\cap...\cap P^{j_ r}_{i_ r}\neq \emptyset. \] Renyi posed the problem of finding the maximum number \(N=N(n,t,r)\) for which there exists qualitatively r- independent collection \({\mathcal P}\) of N t-partitions of an n element set. It has been shown that \(N(n,t,2)\leq (1/t)(et)^{n/t}.\) The following results are proved in this article: (1) For every n and t, \(N(n,t,2)\leq \frac{1}{2}(\frac{[2n/t]}{[n/t]})=O(4^{n/t}/\sqrt{n}).\) (2) For every \(t\geq 2\), there exists a constant \(c=c_ t\) such that for all n and r, \(N(n,t,r)\leq c=c_ t\) such that for all n and r, \(N(n,t,r)\leq c4^{n/t}/\sqrt{n}.\) (3) If t is a prime power and \(t^ 2-t\) is a divisor of n-t, then \(N(n,t,2)\geq t^{(n-t)/t^ 2-t}.\) (4) \(N(n,3,2)\geq \frac{1}{2}(\frac{[n/3]}{[n/6]}),\) (5) \(N(n,t,r)\geq (er/t)e^{n/(rt^ r)}.\)