A property related to permutations with coprime adjacent values

Question

Sequence A76220 of OEIS enumerates (up to $n=25$) the number $a_n$ of permutations $\sigma$ of $\lbrace 1,\ldots,n\rbrace$ such that $\sigma(i)$ and $\sigma(i+1)$ are coprime for $i=1,\ldots,n-1$.

All these numbers are obviously even for $n>1$.

All these numbers are divisible by $3$ for $n\geq 3$.

All these numbers are divisible by $9$ for $n\geq 5$.

All these numbers are divisible by $5$ for $n\geq 17$.

Such a number $a_n$ is divisible by $k!$ if there are $k-1$ primes larger than $n/2$ and smaller than $n$ (the images of $1$ and of these primes in any permutation contributing to $a_n$ can be arbitrarily permuted).

The above examples suggest however better divisibility properties, suggesting the following problem:

Given an integer $n$, what is the maximal number $k=k(n)\leq n$ such that for every permutation $\sigma$ of $\lbrace 1,\ldots,n\rbrace$ there exists a set $\lbrace a_1,\ldots,a_k\rbrace$ of $k$ elements in $\lbrace 1,\ldots,n\rbrace$ with $\sigma(a_i)$ coprime to $\sigma(a_j\pm 1)$ for all $i$ and $j$ (with $a_j-1$ or $a_j+1$ outside $\lbrace 1,\ldots,n\rbrace$ dropped)?

Can one say something meaningful on the asymptotics of $k(n)$ (e.g., has it sublinear growth)?

Observation: We can of course assume that $a_1,\ldots,a_k$ contains the preimage of $1$ and of all primes larger than $n/2$ in $\lbrace 1,\ldots,n\rbrace$.

Answer 1

Define $k(\sigma)$ as the maximal $k$ satisfying the requirements for that single permutation $\sigma$. Then even $\max_{\sigma\in S_n}k(\sigma)$ is sublinear in $n$.

Consider a graph on $[n]$, where edges are pairs of coprime numbers. A desired set $\{a_1,\dots,a_k\}$ corresponds to a complete bipartite subgraph with parts $V_1=\{\sigma(a_i)\colon i\in[k]\}$ and $V_2=\{\sigma(a_i\pm1)\colon i\in[k]\}$ (not exactly so; see below). The cardinalities of both parts are linear in $k$.

This means that the set $\mathbb P_n=\mathbb P\cap[n]$ is split into two parts, $Q_1$ and $Q_2$, such that the prime divisors of elements in $V_i$ are all in $Q_i$/. Minimal of such parts has a sublinear in $n$ cardinality.

Indeed, fix some number $D$ which is large but much smaller than $n$, and consider the intersections $\mathbb P_i'=\mathbb P_i'\cap [D]$. Then $$ \frac{|V_i|}n\leq \prod_{p\in\mathbb P_i'}\left(1-\frac1p\right)(1+o(1)). $$ Since one of the two products is small, the claim follows.

Correction. The statement about complete bipartite graph is not completely true in the case when $a_i\pm1$ equals some $a_j$. In this case, we put such $\sigma(a_i)$ into only one part of the bipartite graph, so that the sizes of the parts differ by a factor of at most 2; then both sizes are still linear in $k$.