Problem 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\[\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?
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?
Categories:
Number Theory Graph Theory
Progress
A problem of Erdős and Sárkőzy [ErSa97], who prove 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 cn$ for some constant $c>0$.This threshold is the best possible, since one could take $A$ to be the set of $m\leq n$ which are divisible by either $2$ or $3$, in which case $G(A)$ contains no triangles.
The second question was solved by Sárközy [Sa99] who proved that, for large $n$, if $\lvert A\rvert$ exceeds the given threshold then $G(A)$ contains a complete $(1,\ell,\ell)$ triparite graph with\[\ell \gg \frac{\log n}{\log\log n}.\]
Source: erdosproblems.com/883 | Last verified: January 19, 2026