No CrossRef data available.
Article contents
On Cancellative Set Families
Published online by Cambridge University Press: 01 September 2007
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2007
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
You have
Access
- 4
- Cited by