Hostname: page-component-6898cfcb55-zkb6p Total loading time: 0 Render date: 2026-11-11T18:26:14.820Z 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)
Rights & Permissions [Opens in a new window]

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

Information

Type
Research Article
Copyright
2001 Cambridge University Press