Logo
All Random Solved Random Open
OPEN
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?

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.

Additional thanks to: Stijn Cambie