Probability of picking neighbors in $\{1,\ldots, n\}$

Question

Motivation. Swiss license plates consist of $2$ letters indicating the region, followed by a number, such that the pairing (region, number) is unique by car. In the small town where I live, I saw two cars today, both from my region, having license plate numbers differing by $1$. This motivated the following.

Question. Let $n\geq 2$ be an integer. We say that $S\subseteq \{1,\ldots,n\}$ contains neighbors if there is $k\in S$ such that $k+1\in S$. Let $M(n)$ denote the minimum integer $\leq n$ such that at least half of the sets $S\subseteq \{1,\ldots, n\}$ with $|S| = M(n)$ contain neighbours. What is the value of $$\lim\inf_{n\to\infty}\frac{M(n)}{n}?$$

Answer 1

Claim The number of sets $S$ of cardinality $m$ with no neighbors is precisely $\binom{n+1-m}{m}$.

Proof Encode a subset $S$ of $[n]$ as a binary string $x_0 x_1 \ldots x_n$ where $x_0=0$ and $x_j = 1$ if and only if $j \in S$. Then the sets we want correspond to strings with $m$ ones and no consecutive $11$'s, starting with $0$. A string starting with $0$ has no $11$'s if and only if it is a concatenation of $0$'s and $01$'s. If $x_0 x_1 \ldots x_n$ has $m$ ones then it must be made of $m$ copies of $01$ and $n+1-2m$ copies of $0$; the number of ways to order these is $\binom{n+1-m}{m}$. $\square$

We want to understand when $\binom{n+1-m}{m} \geq \tfrac{1}{2} \binom{n}{m}$. Dividing both sides by $\tfrac{n^m}{m!}$, we want $$\prod_{j=m-1}^{2m-2} (1-j/n) \geq \tfrac{1}{2} \prod_{k=0}^{m-1} (1-k/n)$$ or $$\sum_{j=m-1}^{2m-2} \log (1-j/n) \geq - \log 2 - \sum_{k=0}^{m-1} \log (1-k/n)$$ $$ - \left( \tfrac{3m^2}{2} + O(m) \right) \tfrac{1}{n} + O(m^3/n^2) \geq - \log 2- \left( \tfrac{m^2}{2} + O(m) \right) \tfrac{1}{n} + O(m^3/n^2).$$ So $$m^2/n = \log 2 + O(m/n) + O(m^3/n^2)$$ and the threshold is at $m = \sqrt{(\log 2) n}$.

---

This makes sense intuitively: If we choose a random set of size $m \approx \sqrt{(\log 2) n}$, then the probability that it contains $k$ and $k+1$ is $\approx \sqrt{(\log 2) n}^2/n^2 \approx (\log 2)/n$. Nonrigourously, the probability that $S$ does not contain $k$ and $k+1$ for any $k$ should be about $(1-(\log 2)/n)^{n-1} \approx e^{- \log 2} = 1/2$.

Answer 2

$\renewcommand{\S}{\mathcal S}\newcommand{\Si}{\Sigma}$Let us assume that you meant to write $|S| = M(n)$ instead of $|S| = M(k)$ (otherwise, the question does not seem to make sense).

For $j\in[n]:=\{1,\dots\}$, let, as usual, $\binom{[n]}j$ stand for the set of all subsets of cardinality $j$ of the set $[n]$, and then let $\nu_{n,j}$ denote the cardinality of the set, say $\S_{n,j}$, of all set $S\in\binom{[n]}j$ without neighbors.

The set $\S_{n,j}$ is in the standard bijective correspondence with the set, say $\Si_{n,j}$, of all sequences in $\{0,1\}^n$ with exactly $j$ $1$'s such that no $1$ is followed by a $1$. So, in each sequence in $\Si_{n,j}$, each $1$ is followed by a $0$, except that a $1$ in the last, $n$th position is not followed by anything. To erase this exception, let us append an additional fixed $0$ in position $n+1$. So, making $10$ a letter, we see that the cardinality $\nu_{n,j}$ of the set $\Si_{n,j}$ is the number of words in the alphabet $\{10,0\}$ of length $n+1-j$ containing exactly $j$ instances of the character $10$ (as the initial $n+1$ positions for $j$ $1$'s and $n+1-j$ positions for $0$'s got reduced to $n+1-j$ positions for $j$ $10$'s and $n+1-2j$ $0$'s).

Thus, \begin{equation} \nu_{n,j}=\binom{n+1-j}j. \end{equation}

So, $M(n)$ is the smallest $j$ such that \begin{equation} \binom{n+1-j}j\le\frac12\binom nj. \end{equation} For $j\asymp\sqrt n$, we have \begin{equation} \binom nj=n^j\,\prod_{i=0}^{j-1}\Big(1-\frac in\Big)=n^j\,\exp-\frac{j^2}{2+o(1)n} \end{equation} and, similarly, \begin{equation} \binom{n+1-j}j=n^j\,\exp-\frac{3j^2}{2+o(1)n}. \end{equation} We conclude that \begin{equation} M(n)\sim\sqrt{n\ln 2}. \end{equation}