Erdős Problem #1183
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: combinatorics, ramsey theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Erdős Problem #1183 asks the following. The maintained status is OPEN.
Two-color every subset of \([n]=\{1,\dots,n\}\). Define \(f(n)\) as the guaranteed maximum size of a monochromatic family closed under both union AND intersection. Define \(F(n)\) analogously with closure under union only. The family need not be a full sublattice of \(2^{[n]}\); it must simply be internally closed under the specified operations. Ask for sharp sizes, whether \(F(n)\ge n^{\omega(n)}\) for some diverging \(\omega(n)\), and an upper bound \(F(n)<(1+o(1))^n\). One-color classes alone are not necessarily closed families.
A small example
For \(n=3\), the Boolean lattice has eight subsets and 256 red/blue colorings. Exhaustively enumerate all nonempty families of the eight subsets and test closure under union and under both union/intersection. There are respectively 121 union-closed and 73 meet-and-join-closed nonempty families. Minimizing the largest available monochromatic closed family across all colorings yields \(f(3)=F(3)=2\), exactly. This finite coincidence does not predict superpolynomial \(F(n)\) as \(n\to\infty\).
What is known
The maintained catalogue https://www.erdosproblems.com/1183 lists this Erdős–Ulam question OPEN [Er78,p.39]. A maximal chain of \(n+1\) nested subsets is automatically closed under both operations, so by the pigeonhole principle it contains a monochromatic subchain of at least \(\lceil(n+1)/2\rceil\) members. This is the elementary lower bound noted by Erdős; it does not imply strong growth. A Howorka result on cardinality-class colorings, cited without a located reference, gives superpolynomial \(F(n)\) for a restricted class of colorings and does not settle arbitrary 2-colorings. Live comments/proof claims must be independently reviewed.
GCL's current state
Authenticated original-issue RESULT/1 research return. GCL independently replayed only the exact bounded fixture in ci/erdos_compendium_007_phase21_checks.py. The general theorem statements above are attributed to their external sources rather than independently certified. This is a locally authored and unaccepted draft.
What remains
Source-lock Erdős 1978 and Howorka's missing restricted-coloring theorem. Independently verify exhaustive n=3 family enumeration using a second method and compare closure under nonempty pair operations vs including empty union/intersection. Then develop nontrivial general lower constructions that apply to arbitrary colorings rather than cardinality-class-only cases.
Protected V2 admission requires source fidelity, manuscript QA and any mandatory independent critic reviews; none is inferred from this finite example.
Sources and claim boundaries
https://www.erdosproblems.com/1183 ; [Er78,p.39], Erdős–Ulam, reported Howorka theorem (primary citation missing).
Finite evidence receipt: governance/erdos_compendium/batches/EC-BULK-007_FINITE_CHECKS_PHASE21.json. Original GitHub source issue identities unchanged; source-fidelity adjudication, public deployment and V2 editorial acceptance PENDING.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2454 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.