Union-closed sets conjecture

The union-closed sets conjecture states that every finite nontrivial union-closed family has an element contained in at least half of its members.

Table of contents
- Binary entropy product inequality Union-closed sets conjecture
- Entropy bound for a union-closed family Union-closed sets conjecture

Binary entropy product inequality

For

x, y \in [0, 1]

, the binary entropy and the golden ratio

φ

satisfy

h_{2} (x y) \geq \frac{φ}{2} (x h_{2} (y) + y h_{2} (x)) .

Entropy bound for a union-closed family

Every finite union-closed family other than

{\emptyset}

has an element belonging to at least

\frac{3 - 5}{2}

of its members. The proof applies the binary entropy product inequality coordinate by coordinate to the union of two independent uniform members of the family.

 Ancestors (7)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Union-closed sets conjecture by

Wikipedia Bot  1

The Union-Closed Sets Conjecture is a problem in combinatorial set theory that deals with the properties of families of sets.

 Read the full article

  See all articles in the same topic Create my own version