Komjath 2025 erdos hajnal problem list

../

---

Péter Komjáth, The Erdős-Hajnal Problem List. The Bulletin of Symbolic Logic 31 (2025), 418--461. doi:10.1017/bsl.2025.1. The file prints "© The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic." at the foot of its first page with no open access or Creative Commons statement, and the journal's article page for DOI 10.1017/bsl.2025.1 (read 2026-10-02) shows the same line behind a paywall and names no open license, every other right reserved.

Komjath updates the 82-item combinatorial set theory problem list Erdos and Hajnal circulated in 1967 (published 1971, extended 1974), reporting progress on each problem across roughly fifty years; the paper is a survey with attributions, adding a few short arguments of its own, such as the Cohen-forcing argument after Problem 32 (pp. 434--435). Problem 10 asks under GCH whether kappa^+ -> (alpha)^2_2 for every kappa and alpha < kappa^+, with Problem 10/A collecting the omega_1 cases (settled by Baumgartner-Hajnal; Todorcevic extended their theorem and Prikry's earlier omega_1 -> (omega : omega_1, alpha)^2 for alpha < omega_1) and Problem 10/B posing omega_2 -> (omega_1 + omega)^2_2, for which the commentary records Hajnal's consistency with GCH of two negative relations, the second of which, omega_2 not -> [omega_1 + omega]^2_{omega_1}, makes the 10/B relation fail in his models; the CH case omega_2 -> (omega_1 + n)^2_2; Laver's theorem that CH and a normal (aleph_2, aleph_2, aleph_0)-saturated ideal on omega_1 give omega_2 -> (omega_1 2 + 1, alpha)^2 for alpha < omega_2, which at alpha = omega_1 + omega gives the 10/B relation (p. 424); and, under Problem 24 (p. 431), Laver's consistency, from a huge cardinal, of GCH with an (aleph_2, aleph_2, aleph_0)-saturated ideal on omega_1, where the word normal is absent. Komjath draws neither consequence for 10/B; both are this card's one-line deductions. Problem 35 (Hajnal, GCH) asks for a free set of size aleph_{omega+1} for set mappings f: omega_{omega+1} -> [omega_{omega+1}]^{<= aleph_omega} with small pairwise intersections, and the only commentary, printed after Problem 36, is Shelah's positive theorem for regular kappa with kappa^{<kappa} = kappa. Problem 45(A) states the conjecture that every kappa-chromatic graph has a triangle-free kappa-chromatic subgraph and notes Komjath-Shelah's consistent counterexample at aleph_1, while 45(B) was proved by Rodl. Problem 53 asks for a K_4-free graph in which every countable edge-coloring has a monochromatic triangle: Shelah proved consistency and existence in ZFC is stated to be open. For problem 595 this is the material current-status source (Problem 53); for 1170 it supplies context on Problem 10 without resolving it; for 1172 it states no answer, but its two Laver passages would make omega_2 -> (omega_1 + omega)^2_2 consistent with GCH from a huge cardinal if the ideal in Laver's GCH model is normal, a point Laver's paper (Logic Colloquium '80, 1982, pp. 173--180; not in the library) must settle; for 1171 its Problem 13 commentary and Problem 54 discussion record the ZFC theorem omega_1^2 -> (omega_1 omega, 3, 3)^2 of Baumgartner-Hajnal, that CH gives omega_1^2 not -> (omega_1 omega, 4)^2, the attribution of omega_1^2 -> (omega_1 alpha, 3)^2 for alpha < omega_1 to Erdos-Hajnal (1970), and that omega_1^2 -> (omega_1 omega, 3, 3, 3)^2 is unknown; for 1173 it records no answer to Problem 35, Shelah's regular-kappa theorem giving free sets of every order type below kappa^+ rather than one of size kappa^+; for 1175 it shows a formulation mismatch, since Problem 45(A) is the same-cardinal conjecture rather than the website's existential-lambda weakening; and for 624 it is off-point, as the set-mapping sections never treat finite H(n) or the 1968 Mat. Lapok problem. For problem 1219 it is the acceptance record for Problem 3 (p. 419), which states the relation in the catalog's form, attributes its proof to Shelah [152] as the last remaining case of lambda -> (kappa)^2_2, and records Hajnal's conjecture lambda -> (aleph_omega, 4)^3 as unproven.

Source: https://doi.org/10.1017/bsl.2025.1.

Bears on. #595, #624, #737, #740, #1128, #1169, #1170, #1171, #1172, #1173, #1174, #1175, #1218, #1219, #1220

Results to transcribe.

• Problem 3 (p. 419): If aleph_omega < 2^{aleph_{n_0}} < 2^{aleph_{n_1}} < ... and lambda = 2^{aleph_{n_0}} + 2^{aleph_{n_1}} + ..., then lambda -> (aleph_omega)^2_2; proved by Shelah [152]; Hajnal's conjecture lambda -> (aleph_omega, 4)^3 under the same assumption still unproven.
• Problem 10: Under GCH, does kappa^+ -> (alpha)^2_2 hold for every kappa and every alpha < kappa^+? Komjath gives no verdict, and by the 10/B commentary GCH is consistent with its failure at omega_2 -> (omega_1 + omega)^2_2; omega_1 cases settled by Baumgartner-Hajnal and extended by Todorcevic.
• Problem 10/B: Under GCH, does omega_2 -> (omega_1 + omega)^2_2 hold? Komjath gives no verdict. Hajnal showed (unpublished) that omega_2 not -> (omega_1 + 2)^2_omega and omega_2 not -> [omega_1 + omega]^2_{omega_1} are separately consistent with GCH, and Rebholz deduced this from a gap-2 morass and diamond; the second relation gives omega_2 not -> (omega_1 + omega)^2_2, so GCH does not prove the 10/B relation (a one-line deduction, not Komjath's). In the positive direction Erdos-Hajnal proved omega_2 -> (omega_1 + n)^2_2 for n < omega under CH (unpublished), and Laver proved omega_2 -> (omega_1 2 + 1, alpha)^2 for alpha < omega_2 from CH and a normal (aleph_2, aleph_2, aleph_0)-saturated ideal on omega_1 (pp. 423--424); under Problem 24 (p. 431) Komjath adds that Laver, from a huge cardinal, made GCH consistent with an (aleph_2, aleph_2, aleph_0)-saturated ideal on omega_1, without the word normal.
• Problem 13 commentary and Problem 54 discussion: Erdos-Hajnal (1970) proved omega_1^2 -> (omega_1 alpha, 3)^2 for alpha < omega_1; Baumgartner-Hajnal (1987) proved omega_1^2 -> (omega_1 omega, 3, 3)^2 in ZFC and, under CH, omega_1^2 not -> (omega_1 omega, 4)^2, which by forcing and compactness yields a finite K_4-free graph whose every two-edge-coloring has a monochromatic triangle; whether omega_1^2 -> (omega_1 omega, 3, 3, 3)^2 holds is unknown.
• Problem 35: Under GCH, for f: omega_{omega+1} -> [omega_{omega+1}]^{<= aleph_omega} with |f(alpha) cap f(beta)| < aleph_omega, is there a free set of size aleph_{omega+1}? No answer is recorded. The only commentary, printed after Problem 36 (p. 436), is Shelah's theorem that for regular kappa with kappa^{<kappa} = kappa every set mapping f: kappa^+ -> P(kappa^+) with |f(xi) cap f(eta)| < kappa has a free set of every order type alpha < kappa^+; its case kappa = omega answers Problem 36, and it asserts no free set of size kappa^+.
• Problem 45: (A) every infinite-chromatic graph has a triangle-free subgraph of the same chromatic number - consistently false at aleph_1 by Komjath-Shelah; (B) the finite analog with f(k) -> infinity, proved by Rodl.
• Problem 53: Is there a K_4-free graph such that every countable coloring of its edges yields a monochromatic triangle? Shelah proved consistency; existence in ZFC is open.

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