Largest permutation of subset of $[n]$ with the property that every element in the right half is near to ($<n/2$ from) every element in the left half

Question

Let $\ n\in\mathbb{N}\ $ and consider rearrangements/permutations, $\ \sigma_k\ (k\leq n)$ of subsets of $\ [n]:= \{ 1,2,\ldots, n\}\ $ with the property that no member of the right half of $\ \sigma_k\ $ is greater than $\ \frac{n}{2}\ $ distance away from a member of the left half of $\ \sigma_k.\ $

So, for example, for $\ n=80,\ $ the arrangement $\ 4, 61 \vert 23, 5\ $ has left half $\ 4, 61,\ $ and right half $\ 23, 5.\ $ This arrangement fails to satisfy the desired property because $\ 61 - 5 > 40.$

An example in $n=80$ that does satisfy the property is $\ 35, 28, 53\vert 19, 37, 63,\ $ because everything in the left half is not further than $40$ away from anything in the right half.

My question is: what the maximum value of is $k$ , i.e., the cardinality of a rearranged subset of $[n]$ with the desired property?

I have been able to figure out is that $k$ cannot equal $n$ because in the $n=80$ example, whatever half contains $\ 1\ $ would need to contain $\ 42\to 80,\ $ but then (due to pigeonhole principle) $\ 2\ $ would have to be in the other half, but $\ 80-2>40.$

Also, $\ k\geq n/2$ because of $\ 1\to \frac{n}{4}\ \Big\vert\ (\frac{n}{4}+1)\to n/2.$

But with the $n=80$ example, we can add larger numbers onto the left-hand side to get, for example: $\ 44\to 41, 1\to 18\ \Big\vert\ 19\to 40,\ $ and so $\ k\geq 44,\ $ and you can do this up to $\ 54\ $ instead of $\ 44,\ $ but I'm not sure how to improve on that.

The following table might have mistakes, but it is my attempt to find the best sequences for some small values of $n$.

\begin{array}{|c|c|c|} \hline \text{n} & \text{Example maximal permutation subset} & \text{k} \\ \hline \mathbb{4} & 1,4 \vert 2,3 & 4 \\ \hline \mathbb{6} & 1,4 \vert 2,3 & 4 \\ \hline \mathbb{8} & 1,6,2 \vert 5,3,4 & 6 \\ \hline \mathbb{10} & 1,8,2,7 \vert 3,6,4,5 & 8 \\ \hline \mathbb{12} & 1,8,2,7 \vert 3,6,4,5 & 8 \\ \hline \mathbb{14} & 1,10,2,9,3 \vert 8,4,7,5,6 & 10 \\ \hline \mathbb{16} & 1,12,2,11,3,10 \vert 4,9,5,8,7,6 & 12 \\ \hline \mathbb{18} & 1,12,2,11,3,10 \vert 4,9,5,8,7,6 & 12 \\ \hline \mathbb{20} & 1,14,2,13,3,12,4 \vert 11,5,10,6,9,7,8 & 14 \\ \hline \end{array}

I imagine the details, like

• odds and even $n$
• whether it's $>40$ or $\geq 40$

don't matter, because I imagine the behaviour is similar in terms of the asymptotic value of $\ k(n)\ $ which is what I'm interested in. It feels like it should have to do with some logarithmic function.

Answer 1

This is simpler than I first thought. In order to minimise the (maximum) distance between the left and right half, I think we carry on the pattern in the table in the question, and so our largest permutation should be of the form:

$$ \left[\ \text{lower quarter of } [k]\ \right] , [\ \text{ upper quarter of } [k]\ ] \Bigg\vert\ [\ \text{middle half of } [k]\ ]\ , $$

in which case the maximum distance between members of the left half and members of the right half is $\ \approx \frac{3}{4} k,\ $ which should be equal to $\frac{n}{2}$ if we are maximising. So we get: $\ \approx \frac{3}{4} k = \frac{n}{2},\ \implies k \approx \frac{2}{3} n,\ $ or to be more precise, it would be something like, $\ k = \frac{2}{3}n \pm 4,$ or maybe $\pm 2,$ but as I'm not interested in this detail, it doesn't really matter.