A better bound for locally thin set families (Q5947361): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Locally Thin Set Families / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: String Quartets in Binary / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New bounds for union-free families of sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Union-free hypergraphs and probability theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4053473 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fredman–Komlós bounds and information theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New bounds for perfect hashing via information theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Determination of two vectors from the sum / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4840778 / rank | |||
Normal rank |
Latest revision as of 20:58, 3 June 2024
scientific article; zbMATH DE number 1660984
Language | Label | Description | Also known as |
---|---|---|---|
English | A better bound for locally thin set families |
scientific article; zbMATH DE number 1660984 |
Statements
A better bound for locally thin set families (English)
0 references
29 March 2002
0 references
A family \({\mathcal F}\) of subsets of a ``ground set'' \(A\) of \(n\) elements is 4-locally thin if, for any 4 distinct members of \({\mathcal F}\), at least one member of \(A\) is contained in exactly one of the 4; \(M(n)\) denotes the maximum cardinality of such a family \({\mathcal F}\). All logarithms are to base 2; \(h\) denotes the ``binary entropy function'', defined by \(h(t)=-t\log t-(1-t)\log t\). It is shown in Theorem 2.1 that \[ \limsup_{n\to\infty}\frac{\log M(n)}n\leq\frac 12\max\limits_{p\in[0,1]}\left[(1-p^2)h\left(\frac{1-p}{1+p}\right)\right]. \] Through computer calculations the authors deduce that the cardinality of a 4-locally thin family cannot exceed \(2^{0.4561n}\). This improves on results contained in [\textit{N. Alon, E. Fachini}, and \textit{J. Körner}, Comb. Probab. Comput. 9, No. 6, 481-488 (2000; Zbl 0972.05050)] and [\textit{N. Alon, J. Körner}, and \textit{A. Monti}, Comb. Probab. Comput. 9, No. 5, 381-390 (2000; Zbl 0978.05070)].
0 references
thin family
0 references