Cancellative pairs of families of sets
type: Item
instance of: scholarly article
title: Cancellative pairs of families of sets
zbMATH Open document ID: 0823.05057
DOI: 10.1016/0195-6698(95)90031-4
author: Ron Holzman
author: János Körner
published in: European Journal of Combinatorics
publication date: 1995-10-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 773830
zbMATH Keywords: cancellative pairs
zbMATH Keywords: families of sets
zbMATH Keywords: entropy function
zbMATH Keywords: conjecture of Erdős and Katona
zbMATH Keywords: cancellative families
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: 0195-6698(95)90031-4
OpenAlex ID: W1987305997
cites work: On the optimal structure of recovering set pairs in lattices: The sandglass conjecture
cites work: Union-free hypergraphs and probability theory
cites work: Q4052170
cites work: On write-unidirectional memory codes
description: scientific article; zbMATH DE number 773830