Hostname: page-component-7bb8b95d7b-5mhkq Total loading time: 0 Render date: 2024-09-29T23:17:24.746Z Has data issue: false hasContentIssue false
  • English
  • Français

On Cancellative Set Families

Published online by Cambridge University Press:  01 September 2007

JÁNOS KÖRNER  and
BLERINA SINAIMERI
JÁNOS KÖRNER
Affiliation:
Department of Computer Science, Università ‘La Sapienza’, via Salaria 113, 00198 Roma, Italy (e-mail: [email protected], [email protected])
BLERINA SINAIMERI
Affiliation:
Department of Computer Science, Università ‘La Sapienza’, via Salaria 113, 00198 Roma, Italy (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 5 , September 2007 , pp. 767 - 773
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N., Fachini, E. and Körner, J. (2000) Locally thin set families. Combin. Probab. Comput. 6 481–488.CrossRefGoogle Scholar
[2]Csiszár, I. and Körner, J. (1982) Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Orlando, FL, USA.Google Scholar
[3]Fachini, E., Körner, J. and Monti, A. (2001) A better bound for locally thin set families. J. Combin. Theory Ser. A 95 209–218.CrossRefGoogle Scholar
[4]Frankl, P. and Füredi, Z. (1984) Union-free hypergraphs and probability theory. Europ. J. Combin. 5 127–131.CrossRefGoogle Scholar
[5]Füredi, Z. (1996) On r-cover-free families. J. Combin. Theory Ser. A 73 172–173.CrossRefGoogle Scholar
[6]Jukna, S. (2000) Extremal Combinatorics With Applications in Computer Science, Springer, Berlin.Google Scholar
[7]Tolhuizen, L. (2000) New rate pairs in the zero-error capacity region of the binary multiplying channel without feedback. IEEE Trans. Inform. Theory 46 1043–1046.CrossRefGoogle Scholar