Monochromatic lattice families in a 2-coloured power set: estimate $f(n)$ and $F(n)$ (Erdős #1183)
Statement
Let $f(n)$ be maximal such that in any $2$-colouring of the subsets of $\{1,\ldots,n\}$ there is always a monochromatic family of at least $f(n)$ sets which is closed under taking unions and intersections. Estimate $f(n)$. Let $F(n)$ be defined similarly, except that the family is only required to be closed under taking unions. Estimate $F(n)$. In particular, is it true that $F(n)\geq n^{\omega(n)}$ for some $\omega(n)\to \infty$ as $n\to \infty$, and that $F(n)<(1+o(1))^n$?
Acceptance. FULLY RESOLVES: determine the order of growth of $f(n)$ (e.g. polynomial vs superpolynomial), and settle both stated conjectures for $F(n)$: prove or disprove $F(n)\geq n^{\omega(n)}$ with $\omega(n)\to\infty$, and prove or disprove $F(n)<(1+o(1))^n$. Machine-checkable (Lean/Coq) proof preferred, else a complete written proof. ADVANCES: any superlinear lower bound for $f(n)$ (beating the trivial $(n+1)/2$ stated in the background) or any nontrivial subexponential upper bound for $f(n)$ or $F(n)$, with proof; resolving either one of the two $F(n)$ conjectures separately; recovering or extending Howorka's unpublished size-colouring result with a written proof; or exact values of $f(n)$/$F(n)$ for $n$ beyond what a direct check reaches (report all $n$ computed), with reproducible exhaustive-search or SAT certificates that the extremal colouring admits no larger monochromatic closed family. Deliver the proof file, or the search code plus certificates and the table of exact values.
Background
A problem of Erdős and Ulam, posed in [Er78, p.39]; listed as open on erdosproblems.com/1183 (fetched 2026-07-13, status 'open'). The known frontier is remarkably thin. Trivially $f(n)\geq \frac{n+1}{2}$: the power set contains a chain of $n+1$ nested subsets, and any 2-colouring of a chain leaves a monochromatic subchain of half its length — and a chain is closed under unions and intersections. Erdős wrote in [Er78] that 'we have no plausible conjecture for the true order of magnitude of $f(n)$', and similarly they had no good guess for $F(n)$. The one recorded partial result: Erdős wrote in [Er78] that if the colouring is constrained so that all subsets of the same size receive the same colour, then Howorka had proved $F(n)>n^{\omega(n)}$ for some $\omega(n)\to\infty$ — but no reference was given. Note the trivial upper bounds: $f(n),F(n)\leq 2^n$, and colouring by a random function shows neither can be too close to $2^n$; the conjecture $F(n)<(1+o(1))^n$ asserts subexponential growth. As of the fetch, the site's comment-activity widget records partial-result claims in the problem's forum thread (10 comments) not yet incorporated into the curated remarks — a solver should check erdosproblems.com/1183 for the latest. The attacker's tool: exact values of $f(n)$ and $F(n)$ for small $n$ are genuinely computable — $n\leq 4$ by direct enumeration over all $2^{2^n}$ colourings, $n=5,6$ via SAT/symmetry-reduced search for colourings avoiding large monochromatic union-closed families — and even a short table would give the first real evidence for the growth order; on the proof side, sunflower/chain-decomposition arguments and Ramsey-type results on distributive lattices are the natural leverage.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1183 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.