A family of subsets of an n-set is 2-cancellative if, for every four-tuple {A,B, C,D} of its members, A∪B∪C=A∪B∪D implies C=D. This generalizes the concept of cancellative set families, defined by the property that A∪B ≠ A∪C for A, B, C all different. The asymptotics of the maximum size of cancellative families of subsets of an n-set is known (Tolhuizen [7]). We provide a new upper bound on the size of 2-cancellative families, improving the previous bound of 20.458n to 20.42n.
On cancellative set families / Korner, Janos; Sinaimeri, Blerina. - In: COMBINATORICS PROBABILITY & COMPUTING. - ISSN 0963-5483. - 16:5(2007), pp. 767-773. [10.1017/s0963548307008413]
On cancellative set families
Blerina Sinaimeri
2007
Abstract
A family of subsets of an n-set is 2-cancellative if, for every four-tuple {A,B, C,D} of its members, A∪B∪C=A∪B∪D implies C=D. This generalizes the concept of cancellative set families, defined by the property that A∪B ≠ A∪C for A, B, C all different. The asymptotics of the maximum size of cancellative families of subsets of an n-set is known (Tolhuizen [7]). We provide a new upper bound on the size of 2-cancellative families, improving the previous bound of 20.458n to 20.42n.File | Dimensione | Formato | |
---|---|---|---|
article.pdf
Solo gestori archivio
Tipologia:
Versione dell'editore
Licenza:
DRM (Digital rights management) non definiti
Dimensione
171.85 kB
Formato
Adobe PDF
|
171.85 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.