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.
2001
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/254355
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact