Skip to content

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.

Back to catalogue · Compendium introduction