Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-26T18:16:43.581Z Has data issue: false hasContentIssue false
  • English
  • Français

Self-Similarity Bounds for Locally Thin Set Families

Published online by Cambridge University Press:  08 October 2001

EMANUELA FACHINI ,
JÁNOS KÖRNER  and
ANGELO MONTI
EMANUELA FACHINI
Affiliation:
Department of Computer Science, University of Rome I ‘La Sapienza’, Via Salaria 113, 00198 Roma, Italy (e-mail: fachini, korner, [email protected])
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, [email protected])
ANGELO MONTI
Affiliation:
Department of Computer Science, University of Rome I ‘La Sapienza’, Via Salaria 113, 00198 Roma, Italy (e-mail: fachini, korner, [email protected])
Get access Rights & Permissions [Opens in a new window]

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
Information
Combinatorics, Probability and Computing , Volume 10 , Issue 4 , July 2001 , pp. 309 - 315
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.)