---

Statement

Problem 6 (printed p. 225), quoted: "Is it true that if $f(n)$ increases arbitrarily fast then there is an $\aleph_1$-chromatic $G$ so that if $g(n)$ is the smallest integer for which $G$ has an $n$-chromatic subgraph of $g(n)$ vertices then $f(n)/g(n)\to0$?"

The paper gives no proof or partial result.

Source. P. Erdős, Some problems on finite and infinite graphs, Logic and Combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, Amer. Math. Soc. (1987), 223--228; Problem 6, p. 225, PDF p. 3 of the Rényi archive's scan (printed p. $n$ = PDF p. $n-222$), read on the rendered page image. The edition read is identified in the source digest.

Read depth. Claims checked: the question was read clause by clause on the page image. A question has no proof to check.

Proof pointer

None in the source.

Dependencies

None.

Bears on

• Problem 110: this problem asks whether one function $F$ bounds, for all large $n$, the least size of an $n$-chromatic subgraph of every $\aleph_1$-chromatic graph. A yes answer to Problem 6 gives a no answer there: for a proposed $F$, take $f=F$; the graph Problem 6 provides has $g(n)>F(n)$ for all large $n$. The site does not cite this paper for the problem, and the paper records no result on either question.