On the maximum number of qualitative independent partitions
type: Item
instance of: scholarly article
title: On the maximum number of qualitative independent partitions
zbMATH Open document ID: 0675.05005
DOI: 10.1016/0097-3165(89)90081-2
author: Svatopluk Poljak
author: Zsolt Tuza
published in: Journal of Combinatorial Theory. Series A
publication date: 1989-01-01T00:00:00Z
review text: 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)}.\)
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 4104960
zbMATH Keywords: independent partitions
MaRDI profile type: Publication
full work available at URL: 0097-3165(89)90081-2
OpenAlex ID: W1970233409
cites work: Explicit construction of exponential sized families of k-independent sets
cites work: On generalized graphs
cites work: Two applications (for search theory and truth functions) of Sperner type theorems
cites work: Q5606602
cites work: An explicit construction of short monotone formulae for the monotone symmetric functions
cites work: Families of \(k\)-independent sets
cites work: On qualitatively independent partitions and related problems
cites work: Orthogonal partitions and covering of graphs
cites work: Q5750908
description: scientific article; zbMATH DE number 4104960