Self-similarity bounds for locally thin set families (Q2757074)

A family \(\mathcal F\) of subsets of \([n]=\{1,2,\dots,n\}\) (the ground set) is \(k\)-locally thin if, for any \(k\) of its distinct members, at least one point of the ground set is contained in exactly one of them; \(M(n,k)\) denotes the maximum cardinality of such a \(k\)-locally thin family; \(t(k)\) is defined to be \(\limsup_{n\to\infty}\frac{\log{ M(n,k)}}n\). Let \(h(t)=-t\log{t}-(1-t)\log(1-t)\) denote the binary entropy function, and \(\ell:[0,1]\rightarrow[0,1]\) be the upper convex envelope of \(h((1-p)^2)\) as a function of \(p\in[0,1]\). Theorem 2.2: NEWLINE\[NEWLINE0.19\leq t(5)\leq\max_{p\in[0,1]} \frac{\ell(p)}{2-p}<0.569.NEWLINE\]NEWLINE From the authors' abstract: ``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.'' NEWLINENEWLINENEWLINEA family \(\mathcal F\) of subsets of \([n]\) is \(k\)-locally 2-thin if, for any \(k\) of its distinct members, at least one point of the ground set is contained in either 1 or 2 of the sets; \(M(n,k,2)\) denotes the maximum of such a \(k\)-locally 2-thin family, and \(t(k,2)\) is defined to be \(\limsup_{n\to\infty} \frac{\log{ M(n,k,2)}}n\). NEWLINENEWLINENEWLINETheorem 2.3: NEWLINE\[NEWLINEt(6,2)\leq\max_{p\in[0,1]} \frac{\ell(p)}{2-p}<0.596.NEWLINE\]NEWLINE All logarithms are to base 2.