Property B for countable sets whose pairwise intersections are finite and never exactly 1 (Erdős #602)
Statement
Let $(A_i)$ be a family of sets with $\lvert A_i\rvert=\aleph_0$ for all $i$, such that for any $i\neq j$ the intersection $A_i\cap A_j$ is finite and $\lvert A_i\cap A_j\rvert \neq 1$. Is there a $2$-colouring of $\cup A_i$ such that no $A_i$ is monochromatic? (A family admitting such a colouring is said to have Property B.)
Acceptance. FULLY RESOLVES: a ZFC proof that every family satisfying the hypotheses (all members countably infinite, pairwise intersections finite and of size $\neq 1$) has Property B; OR a ZFC construction of such a family in which every $2$-colouring of the union leaves some member monochromatic; OR a proof that the answer is independent of ZFC, exhibiting models (or known consistent axioms) deciding it each way. Machine-checkable (Lean/Coq) proof preferred — a Lean statement already exists in the formal-conjectures repository — else a complete written proof. ADVANCES: settle the question under an additional axiom (CH, MA$+\neg$CH, or in a named forcing model); prove Property B for restricted subclasses beyond Miller's bounded-intersection theorem stated in the background (e.g. families of cardinality at most $\aleph_1$, or intersection sizes avoiding $\{1\}$ and growing slowly along a well-ordering); or a reduction of the question to a known open combinatorial principle, with proof of the equivalence. Deliver the proof file or Lean sources, with any set-theoretic assumptions explicit.
Background
A problem of Komjáth, recorded by Erdős in [Er87]; listed as open on erdosproblems.com/602 (fetched 2026-07-13, status 'open'). It sits in the classical line of Property B questions for infinite set systems started by Bernstein, Miller, and Erdős–Hajnal. Two pieces of context explain the hypotheses. First, a classical theorem of E. W. Miller (1937) gives Property B when the family consists of countably infinite sets whose pairwise intersections have size at most a fixed finite bound $t$; Komjáth's question drops the uniform bound, requiring only that each intersection be finite. Second, the exclusion of intersection size exactly $1$ rules out projective-plane-style configurations — in the finite setting, set systems whose members pairwise meet in exactly one point (e.g. the Fano plane) are the standard examples of non-$2$-colourable systems, so some such exclusion is necessary for the question to be plausible. The finite-hypergraph face of Property B — the minimum number of edges $m(n)$ in a non-$2$-colourable $n$-uniform hypergraph — is a separate venue problem (Erdős #901); this problem is its infinitary sibling and is untouched: the site records no partial progress. The statement has been formalised in Lean in Google DeepMind's formal-conjectures repository. The attacker's tool: infinitary combinatorics — transfinite induction along a well-ordering of the family, elementary-submodel or chain-decomposition arguments for the positive direction, and CH/forcing constructions for a consistent counterexample; there is no computational purchase beyond toy finite analogues.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #602 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #602 (formal-conjectures, Google DeepMind) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.