Erdos 1975 problems results finite infinite graphs

../

conjecture_p183: The Erdős–Hajnal–Milner conjecture that a graph on an ordinal without an immediate predecessor has an infinite path or an independent set of the same order type, proved below omega_1^(omega+2), with their four-cycle theorem, Laver's theorem for order types without fixed points, and the pentagon question.

conjecture_p183_taylor: Walter Taylor's conjecture that the finite subgraphs of any graph of chromatic number aleph_1 are the finite subgraphs of graphs of every larger chromatic number, with Erdős's request to characterise the families of finite graphs that occur in graphs of arbitrarily large chromatic number.

conjecture_p184: The Erdős–Hajnal conjecture that for every k and every l at least 3 some graph without a complete graph on l+1 vertices has a monochromatic complete graph on l vertices in every k-coloring of its edges, with Folkman's proof for k = 2 and Nešetřil and Rödl's proof in general.

conjecture_p188_hamiltonian: Erdős recalls the Erdős–Rényi conjecture that G(n; [Cn log n]) is almost surely Hamiltonian, proved by Pósa and with C = 1/2 + ε by Komlós and Szemerédi, and conjectures Hamiltonicity at the threshold where every vertex has valency at least two, with a stronger conditional form.

conjecture_p188_longest_circuit: Erdős expects a circuit longer than (1 − ε)n in almost every random graph with Cn edges for large C, and conjectures that the longest circuit has length (1 + o(1)) f(C) n for a function f(C) tending to 1, with f(1/2) = 0 and f(C) < 1 following from his work with Rényi.

conjecture_p188_trees: The old conjecture of V. T. Sós and Erdős that every graph with n vertices and [(k − 1)n/2] + 1 edges contains every tree with k edges, proved then for many special trees, with no progress in the general case.

conjecture_p191: The conjecture of Faber, Lovász and Erdős that the union of n sets of size n, any two sharing at most one element, can be colored with n colors so that each set receives all n colors, with its failure for n + 1 sets, Greenwell and Lovász's partial result, and Erdős's generalization f(n,m).

problem_p184: The Erdős–Hajnal–Shelah theorem that a graph of chromatic number at least aleph_1 contains every cycle C_n with n above some n_0, and the question, called the simplest unsolved one, whether all these cycles can be made to pass through one edge.

problem_p185: Erdős defines f(k, l_1, l_2), the least order of a graph without a complete graph on l_2 vertices whose k-colorings force a monochromatic complete graph on l_1 vertices, reports f(2,3,6) = 8 and f(2,3,5) at most 18, calls Folkman's bound for f(2,3,4) enormous and offers a prize for a proof or disproof of f(2,3,4) < 10^10.

problem_p186: Erdős defines G_1 ↔ (G,G), every 2-coloring of G_1 containing a copy of G that is monochromatic and induced, reports that a finite such G_1 exists for every finite G, and asks to determine or estimate the least order f(G), its maximum over graphs on m vertices, and the edge analogue F(G).

problem_p188_regular_subgraphs: Erdős defines f_n(k), the smallest number of edges forcing every graph on n vertices to contain a regular subgraph of valency k, notes f_n(1) = 1 and f_n(2) = n, and states that nothing nontrivial was known for k > 2.

problem_p189: The Edwards–Erdős bound that every graph with m edges has a bipartite subgraph with m/2 + C_1 m^(1/2) edges, sharp in order, and Erdős's question whether a triangle-free graph with m edges has one with m/2 + [m^(1/2 + α)] edges for an absolute α > 0.

theorem_p183: The Erdős–Hajnal theorem, reported without proof or reference, that every graph containing no infinite path has chromatic number at most aleph_0.

theorem_p184: The Erdős–Hajnal theorem, assuming the continuum hypothesis, of a graph on aleph_1 vertices with chromatic number aleph_1 and no complete bipartite K(aleph_0, aleph_0), Hajnal's triangle-free strengthening, the question on its shortest odd cycle, and the theorem that chromatic number aleph_1 forces every K(n; aleph_1).

theorem_p186: The Erdős–Hajnal theorem that for every k some graph of chromatic number at least k has an independent set of (1/2 − ε)n vertices in every n-vertex subgraph, the Erdős–Hajnal–Szemerédi theorem for spanned bipartite subgraphs of (1 − ε)n vertices and every infinite chromatic number, and the question on the growth of the chromatic number.

theorem_p189: For E. Koch's function f(n), the largest over graphs on n vertices of the least total valency of a dominating set, Erdős proves f(n) < n^(3/2) and, with Spencer, f(4n) > n^(3/2), so C_1 n^(3/2) < f(n) < n^(3/2); the same proof gives order n m^(1/2) for graphs with n vertices and m edges.

---

P. Erdős: Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pp. 183--192 (loose errata), Academia, Prague, 1975 (MR 52 #10500; Zentralblatt 347.05116).

A short survey in which Erdős collects striking, not-widely-known problems on finite and infinite graphs, with a few proofs he hoped were new. Section I concerns graphs G(alpha) whose vertex set has order type alpha, for an ordinal alpha with no immediate predecessor: Erdős, Hajnal and Milner conjectured that every G(alpha) has an infinite path or an independent vertex set of order type alpha and proved it for alpha < omega_1^{omega+2}; they also proved that every G(alpha) contains a C_4 or an independent set of type alpha, and in fact a K(n; aleph_0) or such an independent set; Laver proved their conjecture that the C_4 statement holds for every order type without fixed points. Section I also records the Erdős–Hajnal theorem that a graph with no infinite path has chromatic number at most aleph_0. Section II reports the Erdős–Hajnal graph (assuming CH) on aleph_1 vertices with chromatic number aleph_1 and no K(aleph_0, aleph_0), Hajnal's later such graph with no triangle either, and the Erdős–Hajnal–Shelah theorem that every graph of chromatic number at least aleph_1 contains every circuit C_n with n above some n_0. Section III states the Erdős–Hajnal conjecture that for every k and every l at least 3 there is a graph G_{k,l} containing no K_{l+1} such that every k-coloring of its edges yields a monochromatic K_l; it records that Folkman proved the case k = 2 and that Nešetřil and Rödl proved the general conjecture. That Section III statement is the source of Problem 582, whose K_4-free, 2-coloring, monochromatic-triangle instance is exactly the k = 2, l = 3 case that Folkman settled. The later sections pose problems on induced Ramsey graphs, graphs with independent sets near half of every subgraph, multicolor Ramsey functions, trees and regular subgraphs in graphs with many edges, Hamiltonian cycles and long circuits in random graphs, bipartite subgraphs of triangle-free graphs, the total valency of dominating sets (Section IX, the paper's one full proof) and the conjecture of Faber, Lovász and Erdős.

Source: https://users.renyi.hu/~p_erdos/1975-33.pdf.

Read status: the copy read for this card is the Rényi archive's ten-page scan of the printed pp. 183-192 (printed p. n is PDF p. n-182), read on the rendered page images; claims checked. Every passage recorded on a result page below was read clause by clause on the page images: Sections I and II (pp. 183--184), Section III to the f(G) problem (pp. 184--186), Section IV (pp. 186--187), Section VI (pp. 187--188), Section VII (p. 188), Section VIII (p. 189), Section IX with the proof of its display (1) read for structure (pp. 189--190) and the first three paragraphs of Section X (p. 191). The remaining questions of Sections II and III, Section V and the projective-plane paragraph of Section X were read but are not paged. Apart from the proof in Section IX and a one-line justification on p. 186, the paper states conjectures and reports results without proof. Nothing here is independently reviewed. No notice is printed in the file (pp. 183--184 and 191--192 carry no copyright or license line); the hosting archive's site footer speaks for the site, not the paper (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 1975 Academia volume has no publisher page, so the publisher's page was not consulted and no Crossref license is recorded; the term is unstated.

Bears on. #582 (Section III, p. 184: the problem is the case k = 2, l = 3 of the Erdős--Hajnal conjecture, the case the paper reports Folkman proved, conjecture_p184; p. 185: Erdős's offer for a proof or disproof of f(2,3,4) < 10^{10}, which concerns the least order of such a graph and not its existence, problem_p185), #900 (Section VII, printed p. 188 = PDF p. 6, page image: Erdős expects that, for large $C$ and $n\to\infty$, almost every $G(n;Cn)$ contains a circuit longer than $(1-\epsilon)n$, and states what he calls the strongest conjecture that could be true, quoted: "There is a function $f(C)$ so that with probability tending to 1 the longest circuit of $G(n;Cn)$ has size $(1+o(1))f(C)n$, $f(C)\to1$ as $C\to\infty$"; he adds that $f(1/2)=0$ and $f(C)<1$ both follow from his results with Rényi, and suggests that $f(C)$ may be continuous and strictly increasing for $C\ge1/2$; the conjecture Ajtai, Komlós and Szemerédi cite as their reference [4], stated for the longest circuit with an asymptotic and a single function $f(C)$, which asks more than the site's wording of the problem does; conjecture_p188_longest_circuit), #746 (Section VII, printed p. 188 = PDF p. 6, page image: Erdős credits the systematic study of random graphs to Rényi and himself [19], [20], [21], recalls their conjecture that for some absolute constant $C$ almost all graphs $G(n;[Cn\log n])$ are Hamiltonian, and reports that Pósa had recently proved it and that Komlós and Szemerédi had then shown by Pósa's method that $C=1/2+\epsilon$ suffices. He recalls the Erdős--Rényi result that, with $f(n)\to\infty$ as slowly as we please, with probability tending to $1$ every vertex of a $G(n;[\tfrac12n\log n+n\log\log n+nf(n)])$, the paper's display (1), has valency at least $2$, and conjectures that the graphs (1) are Hamiltonian with probability tending to $1$, allowing that this may be "too good to be true" but saying he could not disprove it. He then poses a stronger conjecture on the graphs $G(n;[\tfrac12n\log n+n\log n+Cn])$, the paper's display (2), quoted: "With probability tending to 1 if a graph (2) has all its vertices of valency $\ge2$ then it is Hamiltonian"; displays (1) and (2) are recorded as printed, display (2) with its second "$n\log n$" term; Erdős's 1975 attribution of the conjecture to Rényi and himself with the $1/2+\epsilon$ form credited to Komlós and Szemerédi, earlier than the 1981 and 1982 statements the problem page quotes, and a conjecture at the threshold (1) that the problem page's account of Korshunov's theorem concerns; conjecture_p188_hamiltonian), #601 (Section I, p. 183: the Erdős--Hajnal--Milner conjecture that every graph on an ordinal with no immediate predecessor has an infinite path or an independent set of the same order type, which asserts the problem's property for every limit ordinal, reported proved below omega_1^{omega+2}; conjecture_p183), #736 (Section II, p. 183: Walter Taylor's conjecture, the problem's statement; conjecture_p183_taylor), #737 (Section II, p. 184: the question whether a graph of chromatic number at least aleph_1 has an edge on cycles of every length above some n_0, posed for chromatic number at least aleph_1 where the problem takes aleph_1; problem_p184), #594 (Section II, p. 184: the Erdős--Hajnal--Shelah theorem, reported without proof, that such a graph contains every C_n with n above some n_0, which includes the long odd cycles the problem asks for; problem_p184), #565 (Section III, pp. 185--186: the least order f(G) of a graph in which every 2-coloring has an induced monochromatic G, the problem's R*(G), with the request to estimate its maximum over graphs on m vertices and no bound stated; problem_p186), #750 (Section IV, p. 187: the Erdős--Hajnal--Szemerédi graphs of every infinite chromatic number in which every m-vertex subgraph spans a bipartite graph on (1 - epsilon)m vertices, which give the problem's property for f(m) = epsilon m/2 only, an observation of the result page; theorem_p186), #548 (Section VI, pp. 187--188: the Sós--Erdős tree conjecture with [(k-1)n/2] + 1 edges, that is, more than (k-1)n/2 edges, a threshold never above the problem's (k-1)n/2 + 1, so the conjecture asks at least as much as the problem; conjecture_p188_trees), #182 (Section VI, p. 188: f_n(k), the least edge count forcing a k-regular subgraph, of which the problem's maximum is f_n(k) - 1, with the statement that nothing nontrivial was known for k > 2; problem_p188_regular_subgraphs), #581 (Section VIII, p. 189: the question whether a triangle-free graph with m edges has a bipartite subgraph with m/2 + [m^{1/2+alpha}] edges for an absolute alpha > 0, that is, whether the problem's f(m) is at least that large; problem_p189), #19 (Section X, p. 191: the Faber--Lovász--Erdős conjecture in its set form, equivalent to the problem's statement by the observation on the result page; conjecture_p191).

Results to transcribe.

• Conjecture (p. 183): the Erdős--Hajnal--Milner conjecture on graphs G(alpha), proved for alpha < omega_1^{omega+2}, the C_4 and K(n; aleph_0) theorem, Laver's theorem and the pentagon question.
• Theorem (p. 183): Erdős--Hajnal, a graph with no infinite path has chromatic number at most aleph_0.
• Conjecture (pp. 183--184): Walter Taylor's conjecture.
• Problem (p. 184): the Erdős--Hajnal--Shelah theorem on C_n for all n > n_0 and the question of cycles through one edge.
• Theorem (p. 184): Erdős--Hajnal (assuming CH), a graph on aleph_1 vertices with chromatic number aleph_1 and no K(aleph_0, aleph_0); Hajnal's triangle-free version; K(n; aleph_1) in every graph of chromatic number aleph_1.
• Conjecture (p. 184): the Erdős--Hajnal conjecture proved by Folkman for k = 2 and by Nešetřil and Rödl.
• Problem (p. 185): the numbers f(k, l_1, l_2) and the offer on f(2,3,4) < 10^{10}.
• Problem (pp. 185--186): the induced Ramsey order f(G).
• Theorem (pp. 186--187): properties P(epsilon) and P'(epsilon).
• Conjecture (pp. 187--188): the Sós--Erdős tree conjecture.
• Problem (p. 188): f_n(k) for regular subgraphs.
• Conjecture (p. 188): Hamiltonian random graphs, displays (1) and (2).
• Conjecture (p. 188): the longest circuit of G(n; Cn).
• Problem (p. 189): bipartite subgraphs of triangle-free graphs.
• Theorem (pp. 189--190): C_1 n^{3/2} < f(n) < n^{3/2} for dominating sets.
• Conjecture (p. 191): the Faber--Lovász--Erdős conjecture.

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