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.
Korner, Janos; Sinaimeri, Blerina. (2007). On cancellative set families. COMBINATORICS PROBABILITY & COMPUTING, (ISSN: 0963-5483), 16:5, 767-773. Doi: 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.
