Problem 883

For $A\subseteq \{1,\ldots,n\}$ let $G(A)$ be the graph with vertex set $A$ , where two integers are joined by an edge if they are coprime.

Is it true that if

\lvert A\rvert >\lfloor\tfrac{n}{2}\rfloor+\lfloor\tfrac{n}{3}\rfloor-\lfloor\tfrac{n}{6}\rfloor

then $G(A)$ contains all odd cycles of length $\leq \frac{n}{3}+1$ ?

Is it true that, for every $\ell\geq 1$ , if $n$ is sufficiently large and

\lvert A\rvert >\lfloor\tfrac{n}{2}\rfloor+\lfloor\tfrac{n}{3}\rfloor-\lfloor\tfrac{n}{6}\rfloor

then $G(A)$ must contain a complete $(1,\ell,\ell)$ triparite graph on $2\ell+1$ vertices?

Second statement

For $A\subseteq \{1,\ldots,n\}$ let $G(A)$ be the graph with vertex set $A$ , where two integers are joined by an edge if they are coprime.

Is it true that if $n$ is sufficiently large and

\lvert A\rvert >\lfloor\tfrac{n}{2}\rfloor+\lfloor\tfrac{n}{3}\rfloor-\lfloor\tfrac{n}{6}\rfloor

then $G(A)$ contains all odd cycles of length $\leq \frac{n}{3}+1$ ?

Is it true that, for every $\ell\geq 1$ , if $n$ is sufficiently large and

\lvert A\rvert >\lfloor\tfrac{n}{2}\rfloor+\lfloor\tfrac{n}{3}\rfloor-\lfloor\tfrac{n}{6}\rfloor

then $G(A)$ must contain a complete $(1,\ell,\ell)$ triparite graph on $2\ell+1$ vertices?

Source: erdosproblems.com/883

Number theory
Graph theory

Wiki page

Status

ClaimedProved

A full solution has been claimed but not yet accepted. The statement is true.

Claimed: pending claims answer the first question and an accepted claim settles the second; the site's label is OPEN.

Notes

The site's wording of the first question carries no largeness quantifier. On the problem's proof-claims thread (29 July 2026) the site's curator wrote that the question was meant for sufficiently large $n$ , with the small cases a subsidiary problem, and the corrected Statement follows that reading. What Erdős printed in [Er98], the site's source for the question, is not recorded: the paper is not held, so its wording, its page and whether it carries a largeness quantifier have not been read. The question refines Theorem 1 of [ErSa97], which is asymptotic: it holds for $n\ge n_0$ with an unspecified constant $c$ in place of $1/6$ . Della Pietra's pending claim answers the corrected first question; Pan's pending claim answers it for every $n$ , so it also answers the site's wording.

Er98: Erdős, P., Some of my new and almost new problems and results in combinatorial number theory. Proceedings of the 1996 Eger number theory conference (1998). The site's third source key; [Sa99] cites it as its [5] and quotes in its introduction the passage that poses the second question, with the request to determine or estimate the largest possible $\ell$ .
ErSa97: Erdős, Paul and Sárközy, Gábor N., On cycles in the coprime graph of integers. Electron. J. Combin. 4 (1997), no. 2, Research Paper 8, doi:10.37236/1323. Library card Erdős and Sarkozy 1997; Theorem 1 and the remark proposing $c=1/6$ .
Sa99: Sárközy, Gábor N., Complete tripartite subgraphs in the coprime graph of integers. Discrete Math. 202 (1999), no. 1-3, 227--238, doi:10.1016/S0012-365X(98)00359-8 (received 16 October 1997, accepted 14 September 1998). Library card Sárközy 1999; Theorem 1, Theorems 2 and 3 from which it is deduced, and the remark that the singleton class cannot be enlarged.

Problem 883

Second statement

Status

Notes

Proof claims

Discussion