Erdős Problem #75

Erdős Problem 75: hereditary finite independence and uncountable chromatic number

1. Statement and scope

2. Hereditary independence implies subpolynomial finite colouring

3. The linear variant

4. Correct directions of the elementary inequalities

5. Assessment and attribution

Completion rate estimate: 15%.

FORMAL RESTATEMENT. Does there exist a (simple, undirected) graph $G$ with chromatic number $\chi(G)=\aleph_1$ such that the following holds?

For every real $\epsilon>0$ there exists an integer $N_\epsilon$ such that for all integers $n\ge N_\epsilon$ and every subgraph $H$ of $G$ with $\lvert V(H)\rvert=n$, the graph $H$ contains an independent set of size strictly larger than $n^{1-\epsilon}$.

(Recall: an independent set is a vertex set spanning no edges. Also, since removing edges can only increase the independence number, it suffices to check the property for induced subgraphs on $n$ vertices.)

QUICK LITERATURE/CONTEXT CHECK. The problem statement says this is conjectured by Erdős--Hajnal--Szemerédi. It also notes Erdős suggested the independent set might even be of linear size $\gg n$. No additional results are used here.

ATTACK PLAN. Proof track ideas. $1$ Try to build an $\aleph_1$-chromatic graph via a set-theoretic construction while enforcing strong local sparsity (few edges on every finite vertex set), since large independent sets force sparsity. $2$ Seek a transfinite inductive construction ensuring that every $n$-vertex induced subgraph has a large independent set, while globally preventing a countable coloring.

Disproof track ideas. $1$ Show that the local condition implies $G$ must be countably chromatic (i.e. admits an $\aleph_0$-coloring), contradicting $\chi(G)=\aleph_1$.

I did not reach a complete proof or counterexample. The work below records deterministic implications of the local independent-set condition.

WORK.

Lemma 75.1 (independence forces small finite chromatic number). Let $H$ be a finite graph with $n:=\lvert V(H)\rvert$ and independence number $\alpha(H)$. Then \[\chi(H)\ge \frac{n}{\alpha(H)}.\] In particular, if $\alpha(H)>n^{1-\epsilon}$ then $\chi(H)<n^{\epsilon}$.

Proof. A proper coloring of $H$ with $\chi(H)$ colors partitions $V(H)$ into $\chi(H)$ independent color classes. Therefore at least one color class has size at least $n/\chi(H)$. By definition of $\alpha(H)$, we have $\alpha(H)\ge n/\chi(H)$, which rearranges to $\chi(H)\ge n/\alpha(H)$. If $\alpha(H)>n^{1-\epsilon}$ then $\chi(H)\ge n/\alpha(H)< n/n^{1-\epsilon}=n^{\epsilon}$. Since $\chi(H)$ is an integer, this implies $\chi(H)\le \lfloor n^{\epsilon}\rfloor$ and in particular $\chi(H)<n^{\epsilon}$. $\square$

Lemma 75.2 (Caro--Wei bound and an edge upper bound). Let $H$ be a finite graph with $n$ vertices, $m$ edges, and degrees $d(v)$. Then \[ \alpha(H)\ge \sum_{v\in V(H)}\frac{1}{d(v)+1}\ge \frac{n^2}{2m+n}. \] Consequently, if $\alpha(H)>n^{1-\epsilon}$ then necessarily \[ m<\frac{n^{1+\epsilon}-n}{2}. \]

Proof. Step 1 (Caro--Wei inequality). Choose a uniformly random permutation $\pi$ of the vertex set $V(H)$. Define a random vertex subset $I(\pi)$ by \[ I(\pi):=\{v\in V(H): \pi(v)<\pi(u)\text{ for every neighbor }u\text{ of }v\}. \] If $v$ and $w$ are adjacent, they cannot both be earliest among their own neighborhoods (each would require being earlier than the other), so $I(\pi)$ is an independent set.

For a fixed vertex $v$ with degree $d(v)$, consider the set consisting of $v$ and its $d(v)$ neighbors, which has size $d(v)+1$. In a uniformly random permutation, each of these $d(v)+1$ vertices is equally likely to be the earliest among this set, so \[ \mathbb P(v\in I(\pi))=\frac{1}{d(v)+1}. \] Taking expectations and using linearity of expectation, \[ \mathbb E\lvert I(\pi)\rvert = \sum_{v\in V(H)} \mathbb P(v\in I(\pi)) = \sum_{v\in V(H)}\frac{1}{d(v)+1}. \] Since $I(\pi)$ is always an independent set, $\lvert I(\pi)\rvert\le \alpha(H)$ for every $\pi$, hence $\alpha(H)\ge \mathbb E\lvert I(\pi)\rvert$, proving \[\alpha(H)\ge \sum_v \frac{1}{d(v)+1}. \]

Step 2 (convert to an edge bound). The function $x\mapsto 1/(x+1)$ is convex on $[0,\infty)$ (its second derivative is $2/(x+1)^3>0$), so by Jensen's inequality, \[ \frac{1}{n}\sum_{v}\frac{1}{d(v)+1}\ge \frac{1}{\big(\frac{1}{n}\sum_v d(v)\big)+1}. \] But $\sum_v d(v)=2m$, so the right-hand side equals $1/(2m/n+1)=n/(2m+n)$. Multiplying by $n$ gives \[ \sum_v \frac{1}{d(v)+1}\ge \frac{n^2}{2m+n}. \] Combining with Step 1 yields the stated inequalities.

Finally, if $\alpha(H)>n^{1-\epsilon}$, then in particular $\alpha(H)\ge n^{1-\epsilon}+\delta$ for some $\delta>0$, so the inequality $\alpha(H)\ge n^2/(2m+n)$ forces \[ \frac{n^2}{2m+n}< n^{1-\epsilon} \quad\Longrightarrow\quad 2m+n> n^{1+\epsilon}\quad\Longrightarrow\quad m>\frac{n^{1+\epsilon}-n}{2}. \] Taking the contrapositive yields: if $m\ge (n^{1+\epsilon}-n)/2$ then $\alpha(H)\le n^{1-\epsilon}$. Equivalently, if $\alpha(H)>n^{1-\epsilon}$ then $m< (n^{1+\epsilon}-n)/2$, as claimed. $\square$

FAST REALITY CHECK (small parameter sanity). The condition $\alpha(H)>n^{1-\epsilon}$ is asymptotic in $n$. For small $n$, the inequality is easily met for many graphs; for instance, for $n=1,2$ every graph has an independent set of size at least $1>n^{1-\epsilon}$ for any $\epsilon>0$. The nontrivial content is that every large finite subgraph must have very large independent sets; Lemma 75.2 shows this forces every such subgraph to have at most about $\frac12 n^{1+\epsilon}$ edges for each fixed $\epsilon>0$.

VERIFICATION.

• Lemma 75.1: checked that the argument uses only the pigeonhole principle on color classes and does not assume anything about $H$ beyond finiteness.
• Lemma 75.2: verified that $I(\pi)$ is independent, computed $\mathbb P(v\in I(\pi))$ exactly as $1/(d(v)+1)$, and applied Jensen correctly using $\sum_v d(v)=2m$.
• Inequality directions: note that large $\alpha(H)$ implies an upper bound on $m$ via the contrapositive of $\alpha(H)\ge n^2/(2m+n)$; the final displayed implication is stated in that direction.

FINAL: UNRESOLVED.

• (i) Strongest proved partial result. The local requirement $\alpha(H)>n^{1-\epsilon}$ forces strong local sparsity: every $n$-vertex subgraph has at most $<\frac12(n^{1+\epsilon}-n)$ edges (Lemma 75.2), and consequently has chromatic number $<n^{\epsilon}$ (Lemma 75.1).
• (ii) First gap (crisp). Decide whether there exists an $\aleph_1$-chromatic graph $G$ in which every finite induced subgraph on $n$ vertices has at most $O(n^{1+\epsilon})$ edges (for each fixed $\epsilon>0$) while still preventing any countable coloring of $G$.
• (iii) Top 3 next moves. $1$ Try to construct $G$ by transfinite recursion on $\omega_1$, at each stage adding a new vertex with carefully controlled edges to earlier vertices so that every finite set stays sparse. $2$ Attempt a disproof via a decomposition theorem: show that graphs in which every finite subgraph has $O(n^{1+\epsilon})$ edges for all $\epsilon>0$ must be countably chromatic. $3$ Explore whether known uncountably chromatic constructions (e.g. comparability graphs from set theory) can be modified to satisfy the edge bound from Lemma 75.2.
• (iv) Minimal counterexample structure. A minimal failure of the conjecture would be a graph $G$ with $\chi(G)=\aleph_1$ such that for some fixed $\epsilon_0>0$ there exist arbitrarily large $n$ and $n$-vertex subgraphs $H$ with $\alpha(H)\le n^{1-\epsilon_0}$. By Lemma 75.2 such an $H$ would necessarily have at least $\gtrsim \tfrac12 n^{1+\epsilon_0}$ edges, so any counterexample mechanism must force moderately dense finite subgraphs to appear.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - Graphs may be infinite. - $\chi(G)$ is the chromatic number (least cardinal of a proper vertex coloring). - For a graph $H$, $\alpha(H)$ is the independence number (largest size of an independent set). - "$H$ is a subgraph on $n$ vertices" means: $|V(H)|=n$ and $H$ is (not necessarily induced) a subgraph of $G$.

Question. Does there exist a graph $G$ with $\chi(G)=\aleph_1$ such that for every $\varepsilon>0$ there exists $n_0(\varepsilon)$ with the property: for every integer $n\ge n_0(\varepsilon)$ and every subgraph $H\subseteq G$ with $|V(H)|=n$, \[\alpha(H) > n^{1-\varepsilon}?\]

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. I only use the statement as given; I do not rely on external results beyond elementary graph theory inequalities proved below.

3) ATTACK PLAN Proof track ideas: 1. Translate the local independent-set requirement into local sparsity bounds on subgraphs (average degree must be $n^{o(1)}$), then attempt to construct an $\aleph_1$-chromatic graph that is locally extremely sparse. 2. Explore set-theoretic constructions of graphs of chromatic number $\aleph_1$ with strong anti-Ramsey properties.

Disproof track ideas: 1. Prove that any $\aleph_1$-chromatic graph necessarily contains finite subgraphs with relatively small independence number (e.g. bounded by $n^{1-c}$ for some $c>0$), contradicting the requirement for all $\varepsilon$.

Chosen path in this attempt: derive sharp necessary conditions on finite subgraphs $H$ that would follow from the inequality $\alpha(H)>n^{1-\varepsilon}$, to clarify what such a $G$ must look like.

4) WORK Lemma 1 (Greedy bound from maximum degree). Let $H$ be a finite graph on $n$ vertices with maximum degree $\Delta(H)=\Delta$. Then \[\alpha(H)\ge \frac{n}{\Delta+1}.\]

Proof. Run the greedy algorithm: pick any vertex $v_1$, add it to an independent set, and delete $v_1$ and all its neighbors from the graph. Repeat until no vertices remain. At each step, we remove at most $\Delta+1$ vertices (the chosen vertex and its at most $\Delta$ neighbors), and we add exactly one vertex to the independent set. Thus after $t$ steps we have removed at most $t(\Delta+1)$ vertices. To remove all $n$ vertices we need $t(\Delta+1)\ge n$, hence $t\ge n/(\Delta+1)$. The algorithm produces an independent set of size $t$, so $\alpha(H)\ge n/(\Delta+1)$. $\square$

Lemma 2 (Greedy bound from average degree; local sparsity consequence). Let $H$ be a finite graph on $n$ vertices with $m$ edges and average degree $d_{\mathrm{avg}}=2m/n$. Then \[\alpha(H)\ge \frac{n}{d_{\mathrm{avg}}+1}=\frac{n^2}{2m+n}.\] In particular, if $\alpha(H)>n^{1-\varepsilon}$ then $m<\tfrac12 n^{1+\varepsilon}$ for all sufficiently large $n$.

Proof. At each step of the greedy algorithm, choose a vertex of degree at most the current average degree. Since the average degree is $d_{\mathrm{avg}}$, there exists a vertex of degree $\le d_{\mathrm{avg}}$. Removing such a vertex and its neighbors deletes at most $d_{\mathrm{avg}}+1$ vertices per chosen independent vertex. By the same counting as in Lemma 1, this yields an independent set of size at least $n/(d_{\mathrm{avg}}+1)$. The expression $n/(d_{\mathrm{avg}}+1)$ equals $n^2/(2m+n)$.

For the consequence: if $\alpha(H)>n^{1-\varepsilon}$, then in particular \[\frac{n^2}{2m+n}\ge \alpha(H) > n^{1-\varepsilon}.\] Rearranging gives $n/(2m+n)>n^{-\varepsilon}$, i.e. $2m+n < n^{1+\varepsilon}$, hence $m<\tfrac12(n^{1+\varepsilon}-n)$. For large $n$ this implies $m<\tfrac12 n^{1+\varepsilon}$. $\square$

Lemma 3 (Large independent sets imply small chromatic number of finite subgraphs). Let $H$ be a finite graph on $n$ vertices with $\alpha(H)\ge n^{1-\varepsilon}$. Then \[\chi(H)\le n^{\varepsilon}.\]

Proof. Iteratively remove an independent set of maximum size from the current graph and assign it a new color. At each step, the current graph has at most $n$ vertices, so the hypothesis $\alpha(\cdot)\ge (\#V)^{1-\varepsilon}$ is not automatically inherited. However, we only need a crude upper bound: since $\alpha(H)\ge n^{1-\varepsilon}$, the first color class removes at least $n^{1-\varepsilon}$ vertices. Then the remaining graph has at most $n-n^{1-\varepsilon}$ vertices; apply the same argument with the trivial bound $\alpha(\cdot)\ge 1$ to continue.

A simpler direct argument avoids iteration: by definition, $\chi(H)\ge n/\alpha(H)$ because a proper coloring partitions $V(H)$ into $\chi(H)$ independent sets, each of size at most $\alpha(H)$. Thus \[\chi(H)\le \frac{n}{\alpha(H)}\le \frac{n}{n^{1-\varepsilon}}=n^{\varepsilon}.\square\]

FAST REALITY CHECK The condition in the problem would force every large $n$-vertex subgraph $H$ to be extremely sparse: by Lemma 2, $e(H)=O(n^{1+\varepsilon})$ for every fixed $\varepsilon>0$ (hence $e(H)=n^{1+o(1)}$). Also, by Lemma 3, every such finite subgraph would have very small chromatic number $\chi(H)\le n^{\varepsilon}$ for every fixed $\varepsilon>0$. So the challenge is to reconcile these strong local constraints with a global chromatic number of $\aleph_1$.

5) VERIFICATION - Lemma 1 is a standard greedy packing argument. - Lemma 2 uses the same greedy idea but with a degree $\le$ average degree vertex; the algebraic rearrangement is checked. - Lemma 3 uses only the inequality $\chi(H)\ge n/\alpha(H)$ coming from partitioning into independent sets.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: Any graph satisfying the problem's local condition must have all large $n$-vertex subgraphs extremely sparse: $e(H)<\tfrac12 n^{1+\varepsilon}$ for every fixed $\varepsilon>0$ (Lemma 2), and in particular such subgraphs have small chromatic number $\chi(H)\le n^{\varepsilon}$ (Lemma 3).

(ii) First gap: Construct an $\aleph_1$-chromatic graph that is locally this sparse (and hence locally has huge independent sets), or prove that any $\aleph_1$-chromatic graph must contain finite subgraphs violating these bounds.

(iii) Top 3 next moves (concrete): 1. Investigate known $\aleph_1$-chromatic graph constructions (e.g. ladder systems, comparability graphs, shift graphs) and compute/estimate $\alpha(H)$ for their finite subgraphs. 2. Try to prove a universal finite-subgraph theorem for $\aleph_1$-chromatic graphs (analogous to the fact they contain all large odd cycles) that forces some finite subgraph with $\alpha(H)\le n^{1-c}$ for some fixed $c>0$. 3. Attempt a forcing-style construction (if allowed by set theory) where $\chi(G)=\aleph_1$ but finite subgraphs are all locally sparse; determine which axioms are needed.

(iv) What a minimal counterexample would likely look like (structure/parameters): An $\aleph_1$-chromatic graph $G$ together with a sequence of finite subgraphs $H_n\subseteq G$ on $n$ vertices with $\alpha(H_n)\le n^{1-\varepsilon_0}$ for some fixed $\varepsilon_0>0$ (violating the requirement for that $\varepsilon_0$).