Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-17T03:25:16.666Z Has data issue: false hasContentIssue false

Self-Similarity Bounds for Locally Thin Set Families

Published online by Cambridge University Press:  08 October 2001

EMANUELA FACHINI
Affiliation:
Department of Computer Science, University of Rome I ‘La Sapienza’, Via Salaria 113, 00198 Roma, Italy (e-mail: fachini, korner, monti@dsi.uniroma1.it)
JÁNOS KÖRNER
Affiliation:
Department of Computer Science, University of Rome I ‘La Sapienza’, Via Salaria 113, 00198 Roma, Italy (e-mail: fachini, korner, monti@dsi.uniroma1.it)
ANGELO MONTI
Affiliation:
Department of Computer Science, University of Rome I ‘La Sapienza’, Via Salaria 113, 00198 Roma, Italy (e-mail: fachini, korner, monti@dsi.uniroma1.it)

Abstract

A family of subsets of an n-set is k-locally thin if, for every k-tuple of its members, the ground set has at least one element contained in exactly one of them. For k = 5 we derive a new exponential upper bound for the maximum size of these families. This implies the same bound for all odd values of k > 3. Our proof uses the graph entropy bounding technique to exploit a self-similarity in the structure of the hypergraph associated with such set families.

Type
Research Article
Copyright
2001 Cambridge University Press

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.)