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.
Self-similarity bounds for locally thin set families / Fachini, Emanuela; Korner, Janos; Monti, Angelo. - In: COMBINATORICS PROBABILITY & COMPUTING. - ISSN 0963-5483. - STAMPA. - 10:(2001), pp. 309-315. [10.1017/S0963548301004667]
Self-similarity bounds for locally thin set families
FACHINI, Emanuela;KORNER, JANOS;MONTI, Angelo
2001
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.