Minimal completely separating systems of \(k\)-sets (Q5929844): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:40, 5 March 2024
scientific article; zbMATH DE number 1586935
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal completely separating systems of \(k\)-sets |
scientific article; zbMATH DE number 1586935 |
Statements
Minimal completely separating systems of \(k\)-sets (English)
0 references
17 February 2002
0 references
Let \(n\) and \(k\) be fixed positive integers. A collection \(C\) of \(k\)-subsets of \([n]=\{1,2, \ldots, n\}\) is a completely separating system if, for all distinct \(i,j \in [n]\), there is an \(S \in C\) for which \(i \in S\) and \(j \notin S\). Let \(R(n,k)\) denote the minimum size of such a \(C\). It is proved in this paper that, if \(n_k\) is a sequence with \(k \ll n_k \ll k^{1+\varepsilon}\) for every \(\varepsilon > 0\), then \(R(n_k,k) \sim \min \{t \mid n_k \leq {t \choose {\lceil kt/n_{_k} \rceil}}\}\).
0 references
extremal set theory
0 references
uniform hypergraph
0 references
separating family
0 references
Baranyai's theorem
0 references
antichain
0 references