Cancellative pairs of families of sets (Q1893950)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cancellative pairs of families of sets |
scientific article |
Statements
Cancellative pairs of families of sets (English)
0 references
23 October 1995
0 references
A pair \(({\mathcal A}, {\mathcal B})\) of families of \(n\)-element sets is cancellative if, for all \(A, A'\in {\mathcal A}\) and \(B, B'\in {\mathcal B}\), the conditions \(A\backslash B= A'\backslash B\Rightarrow A= A'\) and \(B\backslash A= B'\backslash A\Rightarrow B= B'\) hold. The paper proves that every such pair satisfies \(| {\mathcal A}| |{\mathcal B}|< c^ n\), where \(c\approx 2.3264\). This is related to the well-known conjecture of Erdős and Katona on cancellative families. The proof uses information theoretical tools.
0 references
cancellative pairs
0 references
families of sets
0 references
entropy function
0 references
conjecture of Erdős and Katona
0 references
cancellative families
0 references