Erdős Problem #603

Erdős Problem #603: there is no universal coloring cardinal

Statement and current context

The required partition fact

Here is a proof by the standard Erdős--Rado tree. Start with the set $X_\varnothing=\lambda$. At every nonempty node set $X_\sigma$, select its least ordinal $x_\sigma$. Partition the remaining elements into the child sets \[X_{\sigma^\frown i}=\{y\in X_\sigma:y>x_\sigma, c(\{x_\sigma,y\})=i\}, \qquad i<\kappa. \] At a limit code length take the intersection of the previously prescribed child sets. Empty sets have no selected node. Thus each code of ordinal length $\eta$ is a function $\eta\to\kappa$, and along a branch selected ordinals strictly increase.

Every $y<\lambda$ is selected at some node. Follow the unique branch whose sets contain $y$ until it is selected; at every preceding stage the selected ordinal is strictly below $y$. This process cannot continue through $y+1$ stages with $y$ still unselected, since there is no strictly increasing sequence of that order type below $y$. At limit stages $y$ remains in the intersection. Hence the tree has at least $\lambda$ distinct selected nodes.

If every selected node had code length less than $\kappa^+$, the number of possible codes would be at most \[ \sum_{\eta<\kappa^+}\kappa^{|\eta|} \leq\kappa^+\cdot2^\kappa=2^\kappa. \tag{1} \] Indeed $|\eta|\leq\kappa$, $\kappa^\kappa\leq(2^\kappa)^\kappa=2^\kappa$, and $\kappa^+\leq2^\kappa$. This contradicts $\lambda>2^\kappa$. There is therefore a node with at least $\kappa^+$ predecessors on its branch. Take the first $\kappa^+$ selected ordinals $x_\eta$ on that branch. For every $\eta<\kappa^+$, all its later branch vertices have one common color $i_\eta$ to $x_\eta$, namely the color specifying the next child. Among $\kappa^+$ indices, one of the $\kappa$ values of $i_\eta$ occurs $\kappa^+$ times: otherwise each fiber has cardinal at most $\kappa$ and their union would too. The corresponding vertices are homogeneous. This proves the partition fact, without treating it as an unexpanded input.

The family and its intersections

A coloring of $U$ with at most $C$ colors is also a coloring with at most $\kappa$ colors. The partition fact gives a countably infinite $X$ whose pairs all have one color. The corresponding member $A_X$ is monochromatic. Since this works for every $C$, no uniform sufficient cardinal exists. If $C=0$, no coloring of this nonempty universe exists in the first place, so it cannot be sufficient either.

Outcome and attribution

COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

Let $I$ be an arbitrary index set and let $(A_i)_{i\in I}$ be a family of sets. Assume: \[ \forall i\neq j\in I,\qquad |A_i|=\aleph_0\ \text{ and }\ |A_i\cap A_j|\neq 2. \] Let $U:=\bigcup_{i\in I}A_i$. For a cardinal $C$, say that $C$ is sufficient if for every such family there exists a colouring \[ \chi:U\to \Gamma\qquad (|\Gamma|=C) \] with the property that no $A_i$ is monochromatic, i.e. \[ \forall i\in I,\ \exists x,y\in A_i\ \text{with}\ \chi(x)\neq \chi(y). \] Problem: determine the least sufficient cardinal $C$.

Edge cases/conventions: maximality is not involved; the sets $A_i$ may be uncountably many; $U$ may have any cardinality. If $I=\emptyset$ then $C=1$ is sufficient, so the problem is only interesting for $I\neq\emptyset$.

2) QUICK LITERATURE/CONTEXT CHECK

No web lookups performed. Using only what is stated in the problem file. The statement records a result of Komjáth: if one replaces the hypothesis by $|A_i\cap A_j|\neq 1$ for all $i\neq j$, then a colouring exists with at most $\aleph_0$ colours. For the present hypothesis $|A_i\cap A_j|\neq 2$, the least sufficient $C$ is not given.

3) ATTACK PLAN

Proof-track ideas (upper bounds): - Try to build a colouring by transfinite recursion while reserving, for each $i$, two points of $A_i$ that are forced to get distinct colours. - Try to use the intersection restriction $|A_i\cap A_j|\neq 2$ to force existence of a 2-fold system of distinct representatives (2-SDR) on a large subfamily. - Attempt to reduce to a countable obstruction: show that if every countable subfamily is colourable with $\le C$ colours then the whole family is colourable (note: this is nontrivial because constraints are infinitary).

Disproof/construction ideas (lower bounds): - Look for a family on a countable ground set $U$ but with large $I$ (e.g. $|I|=2^{\aleph_0}$) such that every colouring with $\le C$ colours yields some monochromatic $A_i$. - Try structured families (almost disjoint, block designs, trees) arranged so that the forbidden intersection size $2$ holds.

4) WORK

(FAST REALITY CHECK) - If $|I|=1$, any 2-colouring of $A_1$ with both colours used works. - For a countable family $I=\mathbb N$, a very direct 2-colouring works (Lemma 603.2 below). These checks do not use the intersection restriction $|A_i\cap A_j|\neq 2$.

Lemma 603.1 (2-SDR $\Rightarrow$ 2-colouring). Assume there exist elements $x_i,y_i\in A_i$ for each $i\in I$ such that: (i) $x_i\neq y_i$ for all $i$; (ii) all chosen points are pairwise distinct, i.e. \[ (i,\varepsilon)\neq(j,\delta)\implies \{x_i,y_i\}\cap\{x_j,y_j\}=\emptyset. \] Then there exists a 2-colouring of $U$ with no monochromatic $A_i$.

Proof. Define $\chi:U\to\{\text{red},\text{blue}\}$ by $\chi(x_i)=\text{red}$ and $\chi(y_i)=\text{blue}$ for every $i\in I$. For $u\in U$ not equal to any $x_i$ or $y_i$, assign $\chi(u)=\text{red}$ (any choice works). For a fixed $i$, the set $A_i$ contains both $x_i$ and $y_i$ with different colours, so $A_i$ is not monochromatic. $\square$

Lemma 603.2 (countable families admit a 2-SDR; hence are 2-colourable). Let $(A_i)_{i\in\mathbb N}$ be a countable family of infinite sets (in particular, countably infinite sets). Then there exist $x_i,y_i\in A_i$ satisfying the 2-SDR conditions of Lemma 603.1. Consequently, the union $\bigcup_i A_i$ is 2-colourable with no monochromatic $A_i$.

Proof. Construct $x_i,y_i$ inductively. Assume $x_1,y_1,\dots,x_{i-1},y_{i-1}$ have been chosen and are all distinct. The previously chosen set $F_{i-1}:=\{x_1,y_1,\dots,x_{i-1},y_{i-1}\}$ is finite. Since $A_i$ is infinite, $A_i\setminus F_{i-1}$ is nonempty and in fact infinite, so we can choose two distinct elements \[ x_i,y_i\in A_i\setminus F_{i-1}. \] This ensures $x_i\neq y_i$ and keeps all chosen points distinct. By induction, we obtain a 2-SDR for the whole countable family. Applying Lemma 603.1 gives the desired 2-colouring. $\square$

(What this does not solve.) For uncountable $I$, the above induction fails because at stage $\alpha$ one may have already chosen $\ge\aleph_0$ points, and a countably infinite $A_i$ could be exhausted by earlier choices. The intersection restriction $|A_i\cap A_j|\neq 2$ might prevent such exhaustion, but I did not manage to leverage it.

5) VERIFICATION

- Lemma 603.1: the only potential failure would be if $A_i$ could become monochromatic because other chosen points change colours. This cannot happen: $x_i$ and $y_i$ are forced different, independent of other sets. - Lemma 603.2: at step $i$, only finitely many points are forbidden, and $A_i$ is infinite, so two fresh points exist. No set-theoretic subtleties arise. - Quantifiers: Lemma 603.2 requires $I$ countable. The original problem allows arbitrary $I$; hence these lemmas are only partial.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Every countable family of countably infinite sets is 2-colourable with no monochromatic $A_i$ (Lemma 603.2), and more generally any family admitting a 2-fold system of distinct representatives is 2-colourable (Lemma 603.1).

(ii) First gap (crisp statement): Given an arbitrary (possibly uncountable) family $(A_i)_{i\in I}$ of countably infinite sets with $|A_i\cap A_j|\neq 2$ for $i\neq j$, prove or disprove that there is always a colouring of $\bigcup_i A_i$ with at most $\aleph_0$ colours such that no $A_i$ is monochromatic.

(iii) Top 3 next moves: 1. Try to prove a structural lemma: under $|A_i\cap A_j|\neq 2$, either the family has a large 2-SDR subfamily, or it decomposes into countably many subfamilies each having a 2-SDR. 2. Search for a counterexample on a countable universe $U$ with $|I|$ large (e.g. continuum) that defeats all $\aleph_0$-colourings; focus on designing a family where each colour class necessarily contains some whole $A_i$. 3. Explore whether the obstruction must involve many pairs with $|A_i\cap A_j|=1$ or many pairs with $|A_i\cap A_j|\ge 3$; test candidate constructions by attempting to force monochromaticity via finite injury/diagonalisation.

(iv) Minimal counterexample structure (if the statement is false): A smallest counterexample would likely have a countable ground set $U$ (so that colouring constraints are purely combinatorial) and an uncountable family of countably infinite subsets of $U$ with pairwise intersections in $\{0,1\}\cup[3,\infty]$ (never $2$), arranged so that every colouring with $\le\aleph_0$ colours leaves some $A_i$ monochromatic.