The board / combinatorics / #603
Erdős Problem #603
SOLVEDdatabase updated 2026-07-06
Resolved in some way other than a straight proof or disproof — usual for open-ended questions, or for multi-part problems whose parts went different ways.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Let \((A_i)\) be a family of countably infinite sets such that \(\lvert A_i\cap A_j\rvert \neq 2\) for all \(i\neq j\). Find the smallest cardinal \(C\) such that \(\cup A_i\) can always be coloured with at most \(C\) colours so that no \(A_i\) is monochromatic. GPT 5.4 Pro (prompted by Chojecki) proved there is no uniform bound on such \(C\): for every cardinal \(C\) there is a family of countably infinite sets \((A_i)\) such that \(\lvert A_i\cap A_j\rvert \neq 2\) for all \(i\neq j\), and in any colouring of \(\cup A_i\) with \(C\) colours some \(A_i\) is monochromatic.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved. The authoritative wording is on erdosproblems.com/603.Prizenone
Topicscombinatorics, set theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/603
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.