Erdos 1981 combinatorial problems which i would most

../

---

P. Erdős: On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981) no. 1, 25--42 MR 82k:05001; Zentralblatt 486.05001.

The copy read for this card is a 22-page re-typeset copy of the article (TeX, "Received 15 September 1979" on its first page) with its own pagination, 1--22, and a clean text layer; the journal pagination 25--42 was not compared, and the locators below are pages of the copy. Part V, "Problems of Ramsey Theory", is on pp. 9--10 of the copy, read on the page images. No notice is printed in it, the archive's own re-typeset copy rather than the journal pages (pp. 1--2 and 21--22 carry no copyright or license line); the hosting archive's legal notice covers all material on the site (https://users.renyi.hu/~p_erdos/, read 2026-10-02, prints "(C) 2005-2007 All rights reserved. All material on this site is for scientifics purposes only."); the Springer page for DOI 10.1007/BF02579174 could not be read on 2026-10-02 (it redirected to a login endpoint), and the Crossref record (read 2026-10-07) names only Springer's text-and-data-mining terms (http://www.springer.com/tdm) and no Creative Commons license, every other right reserved.

Read status: claims checked for the five Ramsey displays of Part V ((1)--(4), p. 9, with the prize sentences of (1) and (4), and (5) with its prize, p. 10), for the closing paragraph of Part V (p. 10), for Part III item 2 (pp. 6--7), Part IV item 3 (p. 8) and the $\sum1/\log n_i$ paragraph of p. 15, all read clause by clause on the page images (the last four on 2026-09-18), and for Part III item 1 (p. 6) and the Hamiltonicity sentences of Part VIII (p. 16), read clause by clause on the page images, and for Part III item 3 (p. 7: the Erdős--Sauer function $F(n;r)$ and the Berge sentences), read clause by clause on the page image, and for display (2) of Part V (p. 9), Part III item 2 display (3) with its p. 7 upper bound and Part III item 3 (p. 7), re-read on the page images for the Problem 159, 714 and 182 rows, and for Part IV, item 2 (p. 8: the Hajós and Hajnal--Mader passages, the exponent of Mader's bound checked on a 300 dpi crop), the Murty--Plesnik and Gyárfás sentences of p. 15 and the opening of Part VIII (p. 16: the singularity at $k=n/2$ and the second largest component), read clause by clause on the page images for the Problem 717, 718, 742, 743 and 745 rows; the statements of the other parts are unread; the paper proves nothing, so there is no proof to check.

This is a prize-laden problem survey in eight parts, I to VIII (the copy's headings: I set systems, II combinatorial number theory, III extremal graph theory, IV graph theory, V Ramsey theory, and three further parts ending with VIII, "Two Problems on Random Graphs and Hypergraphs", on p. 16). No new theorems are proved, but the state of the art is recorded for each question. Part I states the Erdős-Rado sunflower conjecture f_k(n) < c_k^n with a prize for k = 3 (best known f_3(n) < (1+eps)^n n! by Spencer, f_3(3) = 21 by Abbott), the Erdős-Faber-Lovász coloring conjecture with a prize in both set and graph form, the Erdős-Lovász representation problem with f(n) < n^{3/2+eps} proved and a prize for f(n) <= Cn, and the T(n,r) conjecture T(n,r) < (2-eta)^n with a prize, which would give exponential growth of the space chromatic numbers L_n. Part II records the Erdős-Turán conjecture r_k(n) = o(n) for every k >= 3, proved by Szemerédi, and Erdős's own conjecture ("I conjecture", p. 4) that divergent reciprocal sums force arbitrarily long arithmetic progressions (with a prize), together with the r_3(n) bounds of Roth and Behrend and a prize offer for an asymptotic formula, the plus-minus one discrepancy conjecture max |sum f(kd)| > c, Sidon-sequence questions, and van der Waerden's function with a prize for f(n)^{1/n} tending to infinity. Part III includes the Ruzsa-Szemerédi theorem f(n; G^{(3)}(6,3)) = o(n^2) and the Erdős-Sauer regular-subgraph problem F(n,r) = O(n^{1+eps}), and Part IV reviews perfect graphs, reconstruction, Hadwiger's conjecture and the conjecture of Hajós, quoting the Erdős-Fajtlowicz lower bound S(n) > c_1 n^{1/2}/log n for S(n) = max chi(G)/t(G) and conjecturing it best possible; Part V asks for lim r(K(n),K(n))^{1/n} (with prizes), r(K(n),C(4)) < n^{2-eps}, the Bondy-Erdős bound r(C_n,C_n,C_n) <= 4n-3, and the size Ramsey behavior of paths. In the copy's words (p. 9): "Prove that (1) lim_{n→∞} r(K(n),K(n))^{1/n} exists and determine the value of the limit. I offer 100 dollars for the first problem and 500 for the second. The proof of the existence of the limit in (1) will perhaps be easy, the determination of its value will probably be difficult (it is between 2^{1/2} and 4)", the statement of Problem 77 with its prizes; and, posed as a problem of Faudree, Rousseau, Schelp and Erdős: "Let r̂(P_n) be the smallest integer for which there is a graph G of r̂(P_n) edges so that if we color the edges of G with two colors, there is always a monochromatic path P_n of length n. Is it true that (4) r̂(P_n)/n → ∞, r̂(P_n)/n² → 0?" Erdős adds that the four had no success with (4), that an asymptotic formula or a good inequality for r̂(P_n) would be useful but (4) comes first, and "I offer 100 dollars for a proof or disproof of (4)", the statement of Problem 720 with the site's prize. Page 10 adds (5), whether log log r(K^{(3)}(n),K^{(3)}(n)) > cn, with a prize offered. Each of the fifteen listed problems (3, 19, 20, 57, 67, 111, 138, 140, 142, 576, 664, 712, 734, 740, 1159) is printed in Parts I--III or VI--VII, three of them in a narrower or different form: Part III (display (2), p. 6) asks 576 for the cube only, Part VI (p. 12) states 664 for pairwise balanced block designs only, and Part VII (p. 14) states 57 for the lengths of all cycles, not of odd cycles, and reports that form proved by Gyárfás, Komlós and Szemerédi. The paper offers prizes for 3, 19, 20, 138, 142 and 712 among them and serves as a published statement of them rather than as a source of solutions.

Four further passages, read on the page images, for the problem pages that quote them. Part III, item 2, pp. 6--7: "Let $\mathcal G$ be bipartite. Is it true that for some $\alpha=\alpha(\mathcal G)$, ($0\le\alpha<1$) (1) $\lim f(n;\mathcal G)/n^{1+\alpha}=c_{\mathcal G}$, $0<c_{\mathcal G}<\infty$. I offer 500 dollars for a proof or disproof of this conjecture. We know that it does not hold for hypergraphs. (See Ruzsa--Szemerédi [74].) Is the $\alpha=\alpha(\mathcal G)$ in (1) always rational? Is it true that for every rational $\alpha$, $1\le\alpha<2$ there is a $\mathcal G$ satisfying (1)? Is it true that (2) $f(n;\mathcal G)>cn^{8/5}$, where in (2) $\mathcal G$ is the graph determined by the edges of a cube? Is it true that (3) $f(n;K(r,r))>cn^{2-1/r}$?" and, at the top of p. 7, "$f(n;\mathcal G)<c_1n^{8/5}$ is a theorem of Simonovits and myself [sic] $f(n;K(r,r))<c_2n^{2-1/r}$ is an old theorem of Kővári, T. Sós, Turán [61] and myself." The prize offer attaches to display (1), the conjecture for every bipartite $\mathcal G$, not to the cube question (2). Part IV, item 3, p. 8, its last paragraph: "Gallai and I conjectured that the edges of every $\mathcal G(n)$ can be covered by $\le Cn$ edge disjoint circuits or edges of our $\mathcal G(n)$. We easily showed that the result holds with $cn\log n$ replacing $Cn$." Part V, its closing paragraph, p. 10, proposes van der Waerden analogues of the Ramsey numbers and defines them: "$f(u,v)$ is the smallest integer for which if we divide the integers not exceeding $f(u,v)$ into two classes either Class 1 [sic] contains an arithmetic progression of $u$ terms or Class II contains an arithmetic progression of length $v$." Erdős knows nothing about the growth of $f(u,v)$ for $u\ne v$; from display (1) of Part II he gets "(6) $f(3,v)<\exp\exp v$", which he expects to be far from best possible, has no non-trivial lower bound for $f(3,v)$, and "would not be surprised if $f(3,v)<\exp v^\alpha$ would hold for some $\alpha<1$." And p. 15, a paragraph of its own: "Let $\mathcal G$ be a graph whose vertices are the integers. Consider $\sup\sum\frac1{\log n_i}$ where the set of vertices $n_1<n_2<\ldots$ either are independent or form a complete graph. I conjecture $\sup\sum\frac1{\log n_i}=\infty$." Erdős says that Ramsey's theorem does not suffice to prove this and that he could not decide it; the finite version asks for the growth rate of $\max\sum_{n_i<X}\frac1{\log n_i}$ as $X\to\infty$.

Two further passages, read on the page images. Part III, "Problems on Extremal Graph Theory", p. 6 of the copy, first defines, in its unnumbered opening paragraph before item 1, $f(n;\mathcal G^{(r)}(k;l))$, for an $r$-uniform hypergraph $\mathcal G^{(r)}(k;l)$ of $k$ vertices and $l$ hyperedges, as the smallest integer such that every $r$-uniform hypergraph on $n$ vertices with that many edges contains a copy of $\mathcal G^{(r)}(k;l)$. Item 1 then recalls that Turán [81] began extremal graph theory by determining $f(n;K^{(2)}(k))$ for every $k$ and asked for $f(n;K^{(r)}(k))$ for all $r$ and $k>r$, where $K^{(r)}(k)$ is the complete $r$-graph on $k$ vertices with $\binom kr$ hyperedges, and that "Turán made some plausible conjectures for $r=3$, $k=4$ and $r=3$, $k=5$." The two offers, quoted: "I offer 500 dollars for the determination of $\lim_{n\to\infty}f(n;K^r(k))/\binom nk=C_{r;k}$, for even a single $k>r>2$", with $c_{2,k}=\frac12\bigl(1-\frac1{k-1}\bigr)$ recorded as Turán's value, and "I offer 1000 dollars for clearing up the whole set of problems." (The copy prints the denominator $\binom nk$ and the constant with a fraction $\frac12$, which the text layer drops; the problem pages record both as printed.) Part VIII, p. 16 of the copy, records that Erdős and Rényi [35] proved that almost all graphs $\mathcal G(2n;[(1+\varepsilon)n\log n])$ have a perfect matching, that this is best possible, and that their conjecture of the same threshold for Hamiltonicity was settled by Pósa [70] and by Komlós and Szemerédi [60]; the sentences are quoted in the Problem 746 row below.

Source: https://users.renyi.hu/~p_erdos/1981-16.pdf.

Bears on. #3: Part II, item 1, p. 4 of the copy, Erdős's own conjecture ("I conjecture") that $\sum1/a_r=\infty$ forces $k$ terms in arithmetic progression for every $k$, with the prize offer; #19: Part I, item 2, p. 2 of the copy, the Erdős--Faber--Lovász conjecture in set and graph form, with a prize; #20: Part I, item 1, p. 2 of the copy, conjecture (1) $f_k(n)<c_k^n$, with a prize for $k=3$; #57: Part VII, p. 14 of the copy, the Erdős--Hajnal conjecture that the lengths $n_1<n_2<\cdots$ of all cycles of a graph of infinite chromatic number satisfy $\sum1/n_i=\infty$, "and perhaps the $n$'s have positive upper density", which the paper reports "recently proved by Gyárfás, Komlós and Szemerédi" (the odd-cycle form of the problem is not printed); #67: Part II, item 2, display (3), p. 4 of the copy, without a prize; #77: display (1) of Part V, p. 9 of the copy, with the two prize offers and the bounds 2^{1/2} and 4; #111: Part VII, p. 16 of the copy, a problem of Hajnal, Szemerédi and Erdős: prove that a graph of chromatic number $\ge\aleph_1$ has, for every $c$, a finite $m$ and a subgraph of $m$ vertices that cannot be made bipartite by omitting $cm$ edges; #138: Part II, item 5, pp. 5--6 of the copy, van der Waerden's $f(n)$, with a prize for $f(n)^{1/n}\to\infty$ and the questions $f(n+1)/f(n)\to\infty$ and $f(n+1)-f(n)\to\infty$; #140: Part II, item 1, display (2), p. 4 of the copy, $r_k(n)=o(n/(\log n)^c)$ for every $k$ and $c$, without a prize of its own; #142: Part II, item 1, p. 4 of the copy, the prize offer for an asymptotic formula for $r_3(n)$ and more generally for $r_k(n)$; #159: display (2) of Part V, p. 9 of the copy (page image): "Let $C(n)$ denote a circuit of $n$ vertices. Prove that (2) $r(K(n),C(4))<n^{2-\varepsilon}$," stated without a prize, a bound or a reference, the site's [Er81] source; #182: Part III, item 3, p. 7 of the copy (page image), the Erdős--Sauer passage quoted below for Problem 715: $F(n;r)$ defined, "We could not disprove $F(n;3)<cn$ and our only upper bound for $F(n;3)$ is $cn^{8/5}$. We conjectured that $F(n,r)=O(n^{1+\varepsilon})$ for every $r$ and $\varepsilon>0$", the conjecture for every valency that is the problem's second question, the site's [Er81] source; #184: Part IV, item 3, p. 8 of the copy, the Erdős--Gallai covering conjecture with the $cn\log n$ result; #191: p. 15 of the copy, the conjecture $\sup\sum1/\log n_i=\infty$ over independent or complete vertex sets, with its finite form; #500: Part III, item 1, p. 6 of the copy, Turán's question for $f(n;K^{(r)}(k))$ with his "plausible conjectures for $r=3$, $k=4$ and $r=3$, $k=5$" and the two prize offers, the site's [Er81] source; #556: display (3) of Part V, p. 9 of the copy, the Bondy--Erdős conjecture $r(C_n,C_n,C_n)\le4n-3$, printed with no restriction on $n$ and followed by "It is easy to see that if (3) is true then for odd $n$ it is best possible"; #564: display (5) of Part V, pp. 9--10 of the copy, a problem of Hajnal, Rado and Erdős, "Is it true that (5) $\log\log r(K^{(3)}(n),K^{(3)}(n))>cn$?", with the prize offer; #576: Part III, item 2, displays (1)--(3), pp. 6--7 of the copy, the cube question (2) $f(n;\mathcal G)>cn^{8/5}$ and the Erdős--Simonovits upper bound of p. 7; the item's prize offer attaches to display (1), not to (2); #664: Part VI, item 1, p. 12 of the copy, the "more generally" question whether to every $c_1$ there is a $c_2$ such that every pairwise balanced block design on $n$ points with all $|A_i|>c_1n^{1/2}$ has a $Q$ with $1\le|Q\cap A_i|\le c_2$ for every $i$; #702: Part I, item 5, p. 3 of the copy, after the observation of Sós and Erdős that $n+1$ triples of an $n$-set always contain two with exactly one common element, which fails for $n$ triples when $n\equiv0\pmod4$: "We then conjectured that if $A_i\subset S$, $|A_i|=k$, $l\leqq i\leqq\binom{n-2}{k-2}+1$ [sic] then there are again two $A$'s which have precisely one element in common. This conjecture was proved by Katona [57] for $k=4$, and by P. Frankl [45] for all $k$." (the $l$ stands for $1$); the conjecture is printed with no range on $n$ and none on $k$, where Erdős's statements in [Er75f], [Er76b] and [Er82e] carry $k>3$ and $n>n_0(k)$; the site's [Er81] source; #712: Part III, item 1, p. 6 of the copy, the prize offer "for even a single $k>r>2$" and the prize offer "for clearing up the whole set of problems", with $c_{2,k}=\frac12(1-\frac1{k-1})$ as Turán's value, the site's [Er81] source for both prizes; #714: Part III, item 2, display (3), p. 6 of the copy (page image), "Is it true that (3) $f(n;K(r,r))>cn^{2-1/r}$?", with the matching upper bound at the top of p. 7, "$f(n;K(r,r))<c_2n^{2-1/r}$ is an old theorem of Kővári, T. Sós, Turán [61] and myself", the problem's statement in Erdős's words, the site's [Er81] source; #715: Part III, item 3, p. 7 of the copy (page image), the problem Erdős investigated with Sauer: "Denote by $F(n;r)$ the smallest integer for which every $\mathcal G(n;F(n;r))$ contains a regular subgraph of valency $r$." Trivially $F(n;1)=1$ and $F(n;2)=n$, and the two knew nothing about $F(n;3)$: "We could not disprove $F(n;3)<cn$ and our only upper bound for $F(n;3)$ is $cn^{8/5}$. We conjectured that $F(n,r)=O(n^{1+\varepsilon})$ for every $r$ and $\varepsilon>0$. Berge conjectured that every regular graph of valency 4 contains a subgraph of valency 3. As far as I know it is not known whether there is an $r$ for which every regular graph of valency $r$ contains a regular graph of valency 3." The site's [Er81] source for the problem: the last two sentences are its two questions in Erdős's words (the copy writes "a subgraph of valency 3" where the 1975 survey writes "a regular subgraph of valency three" and attributes the conjecture to Sauer and Berge), and Tashkinov's 1982 note cites this paper for both Berge's conjecture and the question about $r$; #717: Part IV, item 2, p. 8 of the copy (page image). The item recalls the conjecture of Hajós [55], that a graph of chromatic number $r$ contains a subdivision of $K(r)$, which Erdős writes $K_{\mathrm{top}}(r)$ (the copy's gloss prints "a topologically complete graph or $r$ vertices"), proved for $r\le4$ and disproved for $r\ge7$ by Catlin [16], and announces the Erdős--Fajtlowicz disproof [22] "in a very strong form": for a labeled graph $\mathcal G(n)$ on $n$ vertices with chromatic number $\chi(\mathcal G(n))$ and largest topologically complete subgraph of size $t(\mathcal G(n))$, Hajós's conjecture reads $\chi(\mathcal G(n))\le t(\mathcal G(n))$, and $S(n)=\max_{\mathcal G(n)}\chi(\mathcal G(n))/t(\mathcal G(n))$ (the copy writes the solidus as "lt"). Quoted: "Fajtlowicz and I prove that (1) $S(n)>c_1n^{1/2}/\log n$. In fact we prove that (1) holds for almost all of the graphs $\mathcal G(n)$. Very likely (1) is best possible i.e. $S(n)<c_2n^{1/2}/\log n$, but this conjecture remains open for the time being", the problem's conjecture in Erdős's words, with [16] Catlin, Discrete Math. 10 (1974) 225--233 and [22] the Erdős--Fajtlowicz paper "to appear in Combinatorica" (pp. 17--18), the site's [Er81] source; #718: Part IV, item 2, p. 8 of the copy (page image; the exponent read on a 300 dpi crop). The item records that Dirac [20] proved that every $\mathcal G(n;2n-2)$ contains a $K_{\mathrm{top}}(4)$, with $2n-2$ best possible, and conjectured that every $\mathcal G(n;3n-5)$ contains a $K_{\mathrm{top}}(5)$, which would again be best possible, and, in parentheses, that Pelikán [69] showed every 5-chromatic graph contains a topological $K_5$ minus an edge. Then, quoted: "Hajnal, Mader and I conjectured that every $\mathcal G(n;cr^2n)$ contains a $K_{\mathrm{top}}(r)$. Mader [65] proved the weaker $K_{\mathrm{top}}(r)\subset\mathcal G(n;2^{\binom r2}n)$. (See Erdős--Hajnal [26].)", the problem's conjecture in Erdős's words with his attestation of Dirac's and Mader's theorems; [20] is Dirac, Math. Nachrichten 22 (1960) 61--85, [26] Erdős and Hajnal, Annales Univ. Sci. Budapest 7 (1969) 193--199 and [65] Mader, Math. Annalen 174 (1967) 265--268 (pp. 18 and 20); the site's [Er81] source; #719: Part IV, item 3, p. 8 of the copy, the conjecture of Sauer and Erdős that every $r$-graph $\mathcal G^{(r)}(n)$ is the union of at most $f(n;K^{(r)}(r+1))-1$ cliques, each a $K^{(r)}(r)$ or a $K^{(r)}(r+1)$, no two sharing a $K^{(r)}(r)$; #720: display (4) of Part V, p. 9 of the copy, the two path questions with the prize offer; #721: the closing paragraph of Part V, p. 10 of the copy, $f(u,v)$ defined, display (6) $f(3,v)<\exp\exp v$ and the guess $f(3,v)<\exp v^\alpha$ for some $\alpha<1$; #734: Part VI, p. 12 of the copy, "Prove that there is a pairwise balanced block design" with fewer than $cn^{1/2}$ blocks of each size $t$, $c$ an absolute constant; #736: Part VII, p. 14 of the copy, Walter Taylor's conjecture that a graph of chromatic number $\aleph_1$ contains, for every cardinal $\mathfrak m$, every finite subgraph of some graph of chromatic number $\mathfrak m$; #737: Part VII, p. 14 of the copy, whether a graph of chromatic number $\aleph_1$ has an edge lying on a $C_m$ for every $m>m_0$; #739: Part VII, p. 15 of the copy, Galvin's question whether, for infinite cardinals $\mathfrak m>\mathfrak n$, a graph of chromatic number $\mathfrak m$ has a subgraph of chromatic number $\mathfrak n$; #740: Part VII, p. 15 of the copy, the Erdős--Hajnal question whether a graph of chromatic number $\mathfrak m$ has a subgraph of chromatic number $\mathfrak m$ whose smallest odd circuit has length $\ge2k+1$, with Rödl's case $\mathfrak m=\aleph_0$, $k=2$; #742: p. 15 of the copy (page image): "Murty and Plesnik [67] conjectured that if $\mathcal G(n)$ has diameter two and if the omission of any edge increases the diameter of $\mathcal G(n)$ then $\mathcal G(n)$ has at most $\left[\frac{n^2}4\right]$ edges." Erdős records several failed attempts of his own at this "surprising conjecture" and notes that the complete bipartite graph with $\left[\frac n2\right]$ white and $\left[\frac{n+1}2\right]$ black vertices shows the bound would be best possible; the reference is "[67] U. S. R. Murty, unpublished. See L. Caccetta and R. Häggkvist, On diameter critical graphs, Discrete Math. 28 (1979) 223--229" (p. 20), the problem's statement in Erdős's words, the site's [Er81] source; #743: p. 15 of the copy (page image): "Another attractive conjecture of Gyárfás states that if $T_k$, $k=2,3,\ldots,n$ is any set of $n-1$ trees, and $v(T_k)=k$, then $K(n)$ is the edge disjoint union of the $T_k$'s", stated without a reference, the problem's statement in Erdős's words, the site's [Er81] source; #744: Part VII, pp. 15--16 of the copy, the conjecture of Hajnal, Szemerédi and Erdős that for $k>k_0$ there is $f(n;k)\to\infty$ such that no critical $k$-chromatic graph of $n$ vertices can be made bipartite by omitting $f(n;k)$ edges, with Gallai's and Lovász's upper bounds and the expectation $f(n;4)>c\log n$; #745: Part VIII, p. 16 of the copy (page image). Erdős takes $\mathcal G(n;k)$, a random graph of $n$ vertices and $k$ edges, in the uniform sense: all labeled, or all unlabeled, graphs with $n$ vertices and $k$ edges, and theorems holding for almost all of them. He recalls that he and Rényi studied how the largest component of $\mathcal G(n;k)$ depends on $k$ and found "an unexpected singularity at $k=\frac n2$", which he calls perhaps their most interesting result, and that Rényi's death ended their plan to study the second largest component. Quoted: "I expect that it almost surely will never be large, perhaps not much larger than $\log n$ and certainly $o(n^\varepsilon)$, but nothing definite is known. (Added in proof: These questions were cleared up by Komlós and Szemerédi.)", the problem's origin: the uniform model $\mathcal G(n;k)$, the singularity at $k=n/2$ that the site's $p=1/n$ matches, Erdős's expectation about the second largest component, and his added-in-proof attestation, the site's [Er81] source; #746: Part VIII, p. 16 of the copy, the sentences "Rényi and I [35] proved that almost all graphs $\mathcal G(2n;[(1+\varepsilon)n\log n])$ have a perfect matching and that this result is best possible. We conjectured the same for the graph being Hamiltonian, our conjecture was settled by Pósa [70], Komlós and Szemerédi [60]", Erdős's printed attestation of the two proofs; #1159: Part VI, item 1, p. 12 of the copy, whether there is an absolute constant $C$ such that every finite plane has a blocking set meeting every line in at most $C$ points.

Results to transcribe.

• I.1 (Erdős-Rado sunflowers): Conjecture f_k(n) < c_k^n for the least size forcing k sets with pairwise the same intersection; a prize for k = 3, best known f_3(n) < (1+eps)^n n! (Spencer) and f_3(3) = 21 (Abbott).
• I.2 (Erdős-Faber-Lovász): Conjecture that the union of n complete graphs on n vertices, pairwise sharing at most one vertex, has chromatic number n; a prize offered.
• I.3 (Erdős-Lovász representation): f(n) < n^{3/2+eps} is proved for the least number of pairwise intersecting n-sets that cannot be represented by fewer than n elements (no n-1 elements meet them all); a prize for f(n) <= Cn, and f(n) < 3n is not even decided.
• I.5 (Sós and Erdős on singleton intersections), p. 3 of the copy: n+1 triples of an n-set always contain two meeting in exactly one element, which fails for n triples when n ≡ 0 (mod 4); conjecture, printed with no range on n, that binom(n-2,k-2)+1 k-subsets always contain two meeting in exactly one element, reported proved by Katona for k = 4 and by Frankl "for all k" (Problem 702).
• I.5 (T(n,r) conjecture): T(n,0) = 2^{n-1}+1, T(n,1) is determined by Frankl, and T(n,r) < (2-eta)^n is conjectured for eps n < r < (1/2-eps)n; a prize, and it would imply exponential growth of L_n, the chromatic number of the unit-distance graph of n-dimensional space.
• II.1 (Erdős-Turán on progressions): r_k(n) = o(n) for every k >= 3 was proved by Szemerédi; n exp(-c_1 (log n)^{1/2}) < r_3(n) < c_2 n/log log n, a prize for an asymptotic formula and a prize for the divergent-reciprocal-sum version.
• IV.2 (conjecture of Hajós): Hajós's conjecture chi(G) <= t(G) holds for r <= 4 and was disproved for r >= 7 by Catlin; Erdős and Fajtlowicz prove S(n) > c_1 n^{1/2}/log n for S(n) = max chi(G)/t(G), indeed chi(G)/t(G) > c_1 n^{1/2}/log n for almost all graphs G(n), and conjecture that this is best possible, i.e. S(n) < c_2 n^{1/2}/log n.
• V (1), p. 9 of the copy (page image): prove that lim r(K(n),K(n))^{1/n} exists and determine its value; a prize for the existence and one for the value, "between 2^{1/2} and 4" (Problem 77).
• V (2)-(3), p. 9: prove that r(K(n),C(4)) < n^{2-ε}, posed without a prize; the Bondy-Erdős conjecture r(C_n,C_n,C_n) <= 4n-3, best possible for odd n if true; Rosta and, independently, Faudree and Schelp determined r(C_n,C_m).
• V (4), p. 9 (page image): is it true that r̂(P_n)/n → ∞ and r̂(P_n)/n² → 0, where r̂(P_n) is the least number of edges of a graph every two-coloring of which has a monochromatic path of length n; a prize for a proof or disproof (Problem 720).
• V (5), p. 10: log log r(K^{(3)}(n),K^{(3)}(n)) > cn?, with a prize.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.