---

Claim. The second question of Problem 883 has a positive answer: for every $\ell\ge1$ there is $n_0(\ell)$ such that for $n\ge n_0(\ell)$ and every $A\subseteq\{1,\ldots,n\}$ with $|A|>\lfloor n/2\rfloor+\lfloor n/3\rfloor-\lfloor n/6\rfloor$, the coprime graph $G(A)$ contains a complete tripartite graph $K(1,\ell,\ell)$ on $2\ell+1$ vertices. This follows from Theorem 1 of G. N. Sárközy, Complete tripartite subgraphs in the coprime graph of integers, Discrete Math. 202 (1999), no. 1-3, 227--238: there are constants $c,n_0$ such that if $n\ge n_0$ and $|A|>f(n,2)$, where $f(n,2)$ counts the integers up to $n$ divisible by $2$ or by $3$, that is, $f(n,2)=\lfloor n/2\rfloor+\lfloor n/3\rfloor-\lfloor n/6\rfloor$, then $K(1,\ell,\ell)\subseteq G(A)$ for $\ell=\lfloor c\log n/\log\log\log n\rfloor$. Since this $\ell$ tends to infinity with $n$, every fixed $\ell$ is reached for all large $n$. The paper poses the result as the answer to the question Erdős raised in his last problem collection after the odd-cycle theorem of Erdős and Sárközy (card), and deduces Theorem 1 from two cases split by the number of members of $A$ congruent to $1$ or $5$ modulo $6$: Theorem 2 treats the case where that number is at most $c_1n$ and gives $\ell$ of order $\log n/\log\log\log n$, and Theorem 3 the case where it is at least $\varepsilon n$ and gives $\ell$ of order $\log n$. The author remarks that the class of size $1$ cannot be enlarged, since for $A$ the set of integers up to $n$ divisible by $2$ or $3$ together with $5$ every complete tripartite subgraph of $G(A)$ has a class of one vertex, and asks for the largest possible $\ell$. The library card is source card. The site's commentary credits the paper with the weaker bound $\ell\gg\log n/\log\log n$.

Covers. The second question, the part tripartite, for every fixed $\ell$, with the explicit growth $\ell=\lfloor c\log n/\log\log\log n\rfloor$. Not covered: the first question, on odd cycles, which is the subject of the pending claims of Della Pietra and Pan; and the best possible order of $\ell$, which the paper leaves open.

Depends on. Nothing in this wiki; the argument is the paper's own.

Acceptance. refereed: Discrete Mathematics is a refereed journal; the DOI record gives volume 202, issue 1-3, pages 227--238, issued May 1999, the paper link's date, and the print records the paper received on 16 October 1997 and accepted on 14 September 1998. The site's curator credits the paper with the second question in the problem's commentary, but labels the problem OPEN, so the commentary settles nothing and gives no reviewed. The formal-conjectures statement file (the record link) marks the second question, erdos_883.parts.ii, as research solved with answer true and cites this paper, which corroborates the claim and lends it no evidence; the file is a statement without a formal proof and is not a formalization.