---

Claim. The conjecture of Problem 1078 holds. In the transversal language of the problem page, with $\Delta(r,n)$ the largest integer such that every $r$-partite graph with parts of size $n$ and maximum degree below it has an independent transversal and $\Delta_r=\lim_n\Delta(r,n)/n$, the note proves $\Delta_r\ge\frac12$ for every $r$; by the complementation written on the problem page, $c_r=(r-1)-\Delta_r\le r-\frac32$ for every $r\ge3$, where $c_r$ is the limit of $f_r(n)/n$ and $f_r(n)$ the largest minimum degree of a $K_r$-free $r$-partite graph whose parts all have size $n$. With the 1975 lower bound $c_r\ge r-\frac32-\frac1{r-2}$ for $r>4$ (the construction printed on p. 105 of the 1975 paper; p. 98 states it with $\frac1{2(r-2)}$) this gives $\lim_{r\to\infty}(c_r-r+2)=\frac12$, the conjecture of Bollobás, Erdős and Szemerédi that the site's statement renders with its $o(1)$. The claimed result is the theorem of P. E. Haxell, A note on vertex list colouring, Combin. Probab. Comput. 10 (2001), no. 4, 345--347, which its abstract states in list-coloring form: if every vertex has a list of $2k$ colors and each color appears on the lists of at most $k$ neighbors of any vertex, a proper coloring from the lists exists, which the abstract calls a weak form of a conjecture of Reed. The note is not held, so the exact finite form of its transversal statement is recorded here from the later account of Haxell and Szabó, the claimant's own, which says that the note improved the bound to $\Delta_r\ge\frac12$ and settled the 1975 conjecture; the sharp finite threshold is the later theorem on the claim page Haxell and Szabó.

Depends on. Nothing in this wiki beyond the complementation written on the problem page, which turns the transversal bound into the degree threshold.

Acceptance. Refereed: Combinatorics, Probability and Computing (the Crossref record: volume 10, issue 4, pp. 345--347, issued July 2001, online 2 October 2001; the day is the issue's nominal first day, used for this page's date). Reviewed: the site's curator, T. F. Bloom, labels the problem proved and names this note as the proof. The refereed paper of Haxell and Szabó of 2006 (theorem_1_1, the introduction on p. 2 of the preprint), which says that the note settled the conjecture of Bollobás, Erdős and Szemerédi, is the claimant's own later account and the source of the transversal form of the result recorded above; it is not independent review. This corpus holds no copy of the note; its abstract is public on the publisher's page, and no step of its proof was checked. The acceptance recorded here rests on the publication and the curator's credit, not on a local review.