Bellaard.com

Union-Closed Family Visualizer

A family \(\cF\) is a set of subsets of some set \(X\), called the ground set. The elements of the family, i.e. a subset of \(X\), is called a member. A union closed family is a family for which the union of any collection of members is also in the family. This includes the empty collection of members; so we assume the empty set is always a member of a union-closed family. From here on out we will denote families with scripture letters, members with upper case letters, and elements of members with lower case letters.

The union closed conjecture states that every union closed family has at least one element that is common. A common element is defined as an element \(x \in X\) that appears at least as much times in the members of the family as the amount of times that it doesn't. Equivalently, it is an element that belongs to at least half of the members in the family. The conjecture was proposed by P├ęter Frankl in 1979 and is still open to this day. To be precise/pedantic, there does actually exist a union-closed family that has no common elements: \(\{\emptyset\}\). This family is not considered to be "valid" as it has no actual elements and is therefor omitted from the conjecture. If you're interested in the union closed conjecture I suggest reading the bachelor final project of my friend Sander Spoelstra.

There are many ways to (partially) order the members of a union-closed family. We can order by subset \(\subset\), We can order with the following relation: \[ M \prec N \iff \exists N \neq M' \in \cF : M \cup M' = N \] i.e. \(M\) precedes \(N\) if there exists a member \(M'\) not equal to \(N\), such that the union of \(M\) and \(M'\) is \(N\). Or in other words, \(M \prec N\) if one can make \(N\) using \(M\) but without using \(N\). We can also order by size of the member, i.e.: \[ M \prec N \iff |M| < |N|\] These orderings of a union-closed family can be visualized by plotting layers of minimal elements. A minimal element of a partially ordered set is an element for which there exists no other element which precedes it.

Generate




Visualize






Information



Edit