Price of Locality in Permutation Mastermind:
Are TikTok Influencers Chaotic Enough?

If $B$ has no perfect matchings, the statement holds trivially. Thus, let $M$ be a perfect matching of $B$. For each vertex $u$, let $M(u)$ denote its neighbor in the matching $M$, and $D(u)$ denote one neighbor of $u$ via an edge not in $M$, chosen arbitrarily, which must exist since $u$ has degree at least $2$. Now let $u_0$ be any vertex, and construct a walk $u_0,u_1,\mathrm{\dots }$ by

Since $B$ is finite, some vertex appears twice in this walk. Let $u_j=u_k$ with , chosen so that all intermediate vertices are distinct. Then the subwalk $u_j,u_{j+1},\mathrm{\dots },u_k$ forms a simple alternating cycle $C$, which necessarily has even length. Consider the matching $M^{\prime }=M△E(C)$. For vertices not in $C$, $M^{\prime }$ agrees with $M$. Each vertex of $C$ is incident to exactly one edge of $M$ and one edge of $E(C)\setminus M$, so it is matched by exactly one edge in $M^{\prime }$. Thus $M^{\prime }$ is a perfect matching. Since $C$ contains edges not in $M$, we have $M^{\prime }\ne M$, contradicting the uniqueness of $M$. $◀$

We now use Observation 7 to show a much stronger condition implied by having a unique perfect matching.

Let $f(n)$ be the maximum number of edges of a balanced bipartite graph with $2n$ vertices that has a unique perfect matching. We trivially have $f(1)=1$. For $n⩾2$, we claim that $f(n)⩽f(n-1)+n$. Before proving the claim, let us see that it is enough to conclude, since then, using induction we will have

Now, to prove the claim, we consider an arbitrary balanced bipartite graph $B_n$ on $2n$ vertices with a unique perfect matching and such that $|E(B_n)|=f(n)$. Let $\delta$ be the minimum degree in $B_n$, and note that $\delta =1$: since $B_n$ has a perfect matching we have $\delta ⩾1$, and by Observation 7 we have . Let $u\in V(B_n)$ be a vertex of degree $1$, and $v$ its only neighbor. It must be the case that $u$ and $v$ belong to opposite sides of the bipartition, and thus if we consider the graph resulting from $B_n$ by removing vertices $u$ and $v$, we get a balanced bipartite graph $B^{\prime }$ on $2(n-1)$ vertices. Moreover, $\{u,v\}$ must belong to the (unique) perfect matching of $B_n$, and therefore any perfect matching of $B^{\prime }$ would extend (by adding $\{u,v\}$) to a perfect matching of $B_n$, and thus $B^{\prime }$ must also have a unique perfect matching. Therefore, $|E(B^{\prime })|⩽f(n-1)$. On the other hand,

We thus have

concluding the claim. $◀$

The tightness of Lemma 8 is witnessed by half graphs $H_n$ (see Figure 3), which include the edge $\{i,s_j\}$ if and only if $i⩽j$. The uniqueness of a perfect matching in $H_n$ can be easily seen by induction, noting that vertex $n$ has degree one, and upon removing $n$ together with its neighbor $s_n$, we are left exactly with $H_{n-1}$, for which the inductive hypothesis applies.

Suppose for a contradiction that $U_T$ contains a $K_{2,2}$ consisting of the four edges

An illustration with a concrete example is depicted in Figure 4. Now, let ${\sigma }^{\star }$ be an arbitrary permutation such that ${\sigma }^{\star }(i)=s_x$ and ${\sigma }^{\star }(j)=s_y$. From ${\sigma }^{\star }$ we define now the permutation ${\sigma }^{†}$ by

In other words, ${\sigma }^{†}$ is the matching obtained from ${\sigma }^{\star }$ via the alternating $4$-cycle corresponding to the $K_{2,2}$. Now, note that for any guess ${\pi }_t$ we have $b({\pi }_t,{\sigma }^{\star })=b({\pi }_t,{\sigma }^{†})$. Indeed, let $k\in [n]$ and we prove by cases that ${\sigma }^{\star }(k)={\pi }_t(k)$ if and only if ${\sigma }^{†}(k)={\pi }_t(k)$:

• $\mathrm{■}$

  If $k\notin \{i,j\}$, then ${\sigma }^{\star }(k)={\sigma }^{†}(k)$, and thus the claim holds.

• $\mathrm{■}$

  If $k\in \{i,j\}$, then by construction we have ${\sigma }^{\star }(k)\in \{s_x,s_y\}$ as well as ${\sigma }^{†}(k)\in \{s_x,s_y\}$. But by definition of $U_T$, we have ${\pi }_t(k)\notin \{s_x,s_y\}$. Therefore neither ${\sigma }^{\star }(k)={\pi }_t(k)$ nor ${\sigma }^{†}(k)={\pi }_t(k)$.

We thus have that $b({\pi }_t,{\sigma }^{\star })=b({\pi }_t,{\sigma }^{†})$ for any guess ${\pi }_t$, which implies both ${\sigma }^{\star }$ and ${\sigma }^{†}$ are compatible with transcript $(({\pi }_1,b({\pi }_1,{\sigma }^{\star })),\mathrm{\dots },({\pi }_T,b({\pi }_T,{\sigma }^{\star })))$, and thus ${\pi }_1,\mathrm{\dots },{\pi }_T$ is not sufficient. $◀$

Our lower bound is now a direct consequence of the previous lemma and the quantitative bounds on $K_{2,2}$-free graphs.

Consider a correct strategy whose static part is ${\pi }_1,\mathrm{\dots },{\pi }_T$. Note that before the first guess we have $|E(U_0)|=n^2$. The first guess tests $n$ edges, so $|E(U_1)|=n^2-n$, and after this special first guess the ${\mathrm{\ell }}_k$-locality condition implies for $2⩽t⩽T$ that

Therefore, $|E(U_T)|⩾|E(U_1)|-kT=n^2-n-kT$. Now, since the static strategy is correct, we must have that $U_T$ is $K_{2,2}$-free, and by Theorem 10 it must hold that $|E(U_T)|⩽(1+o(1))n^{3/2}.$ Combining our inequalities, we have $(1+o(1))n^{3/2}⩾n^2-n-kT$, from where $T⩾\frac{n^2-(1+o(1))n^{3/2}}{k}$, thus concluding the proof. $◀$

We write the proof in terms of the static setting, but the adaptive one is identical. Let ${\pi }_1,\mathrm{\dots },{\pi }_{S(n)}$ be a correct static strategy for the standard permutation Mastermind. Then, for each $1⩽i⩽S(n)$, write ${({\pi }_{i-1})}^{-1}{\pi }_i$ as a word ${\omega }_i:={\gamma }_1^{(i)}\mathrm{\dots }{\gamma }_{r_i}^{(i)}$ over $\mathrm{\Gamma }$ that minimizes $r_i$. Then, by definition of the diameter $r_i⩽\text{diam}(\text{Cay}(S_n,\mathrm{\Gamma }))$. Now, construct the guess sequence

which is $\mathrm{\Gamma }$-Permutation-Mastermind strategy, and has size at most

$◀$

We now prove a tight bound on the diameter of the Cayley graph corresponding to the ${\mathrm{\ell }}_k$-local setting.

Since $\text{Cay}(S_n,L_n^{(k)})$ is a Cayley graph and thus vertex transitive, it suffices to upper bound the distance between the identity permutation ${\text{id}}_n$, and an arbitrary permutation $\pi$.

Let $M:=D(\pi ,{\mathrm{id}}_n)=\{i\in [n]:\pi (i)\ne i\}$ be the support of $\pi$, and let $m:=|M|$. Letting $\text{dist}:={\text{dist}}_{\mathrm{Cay}(S_n,L_n^{(k)})}$, we will prove by induction on $m$ that the stronger statement $\text{dist}(\mathrm{id},\pi )⩽\lceil \frac{m-1}{k-1}\rceil$ holds for any $\pi$.

If $m=0$, then $\pi ={\mathrm{id}}_n$ and the bound holds. Otherwise $m⩾2$, since $m=1$ is not possible. If $m⩽k$, then $\pi \in L_n^{(k)}$, so $\text{dist}({\mathrm{id}}_n,\pi )=1$, which agrees with the bound.

Assume now that $m>k$. We will construct $\gamma \in L_n^{(k)}$ such that $|D({\gamma }^{-1}\pi ,\mathrm{id})|⩽m-(k-1)$, and then invoke the inductive hypothesis.

Write $\pi$ as a product of disjoint cycles $C_1,\mathrm{\dots },C_r$, and for each nontrivial cycle $C_i$ fix any cyclic ordering of its elements. By listing the elements of the nontrivial cycles in these cyclic orders (cycle by cycle), we obtain a sequence $v_1,\mathrm{\dots },v_m$ that enumerates $M$ with the property that for every , either $\pi (v_j)=v_{j+1}$, or else $v_j$ is the last element of its cycle (in which case $\pi (v_j)$ is the first element of that same cycle and hence appears earlier in the list).

Let $T:=\{v_1,\mathrm{\dots },v_k\}$ be the first $k$ elements of the previously obtained sequence, and observe that for every $x\in T\setminus \{v_k\}$ we have $\pi (x)\in T$: indeed, if $x=v_j$ with , then either $\pi (x)=v_{j+1}\in T$, or $x$ is the last element of its cycle and $\pi (x)$ is the first element of that cycle, which also lies in $T$.

Since $\pi$ is injective and $\pi (T\setminus \{v_k\})\subseteq T$, the set $\pi (T\setminus \{v_k\})$ has size $k-1$, so there is a unique element $y\in T\setminus \pi (T\setminus \{v_k\})$. Define $\gamma \in S_n$ by

By construction, $\gamma$ only moves elements of $T$, so $\gamma \in L_n^{(k)}$. Moreover, for every $x\in T\setminus \{v_k\}$ we have $({\gamma }^{-1}\pi )(x)={\gamma }^{-1}(\pi (x))={\gamma }^{-1}(\gamma (x))=x,$ so ${\gamma }^{-1}\pi$ fixes all elements of $T\setminus \{v_k\}$. Since $T\subseteq M$, these are $k-1$ indices that were moved by $\pi$, and thus $|D({\gamma }^{-1}\pi ,{\mathrm{id}}_n)|⩽m-(k-1).$

Now, since $\pi =\gamma \cdot ({\gamma }^{-1}\pi )$ and $\gamma \in L_n^{(k)}$, we have

where the second inequality is the inductive hypothesis. This completes the induction.

Finally, since $m⩽n$, we conclude that for every $\pi \in S_n$, we have $\text{dist}({\mathrm{id}}_n,\pi )⩽\lceil \frac{n-1}{k-1}\rceil ,$ and hence $\text{diam}(\mathrm{Cay}(S_n,L_n^{(k)}))⩽\lceil \frac{n-1}{k-1}\rceil$. $◀$

Larcher, Martinsson, and Steger proved that $S(n)⩽28n\lg n$ [17], and thus combining Lemma 13 and Lemma 14 directly yields the first result.

On the other hand, El Ouali et al. [20] proved that $A(n)⩽(n-3)\lceil \lg n\rceil +\frac{5}{2}n-1$. Again, combining Lemma 13 and Lemma 14 yields the result. $◀$

Consider the permutation ${\pi }^{†}:i\mapsto n+1-i$, and let us prove that $\text{dist}({\pi }^{†},{\mathrm{id}}_n)⩾\frac{\lceil n^2/2\rceil }{k(k-1)}$. For this, define the function $\delta :S_n\to \mathbb{N}$ by $\delta (\pi ):={\sum }_{i=1}^n|\pi (i)-i|.$ Note that $\delta ({\mathrm{id}}_n)=0$, whereas

where the last equality can be seen by splitting the sum into two parts depending on whether the argument of the absolute value is positive or not.

To conclude, it suffices to show that, for any $\pi \in S_n$ and $\omega \in W_k$, we have

Indeed, if , we could write ${\pi }^{†}$ as ${\omega }_1{\omega }_2\mathrm{\dots }{\omega }_t{\mathrm{id}}_n$ with and ${\omega }_i\in W_k$ for all $i$. But then we would have

which contradicts the fact that $\delta ({\pi }^{†})=\lceil n^2/2\rceil$. We now prove (1). let $I_{\omega }$ be the interval $\{i,\mathrm{\dots },i+k-1\}$ from the definition of $W_k$ in which $\omega$ is potentially different from ${\mathrm{id}}_n$, and then observe that

But by definition of $W_k$, we have that $\omega (I_{\omega })=I_{\omega }$, and thus $|\omega (j)-j|⩽k-1$ for $j\in I_{\omega }$. Therefore,

which proves (1) and thus concludes the proof. $◀$

Naturally, the diameter of the Cayley graph yields a lower bound on $A_w(n,k)$, but in this case such a bound is weaker than the one we get from the trivial inequality $A_{\mathrm{\ell }}(n,k)⩽A_w(n,k)$, combined with Theorem 1.

While using the diameter bound between guesses of a normal permutation Mastermind strategy would only yield an $O\left(\frac{n^3\lg n}{k^2}\right)$ upper bound, we show that $O(n^2)$ is always a valid upper bound for $S_w(n,k)$, and it holds already for $k=2$. Since the diameter lower bound immediately shows $S_w(n,2)=\mathrm{\Omega }(n^2)$, we focus on proving the upper bound of Theorem 3.

First, let us assume the codemaker is generous, in the sense of Section 2, and thus reveals after every guess which of the $k=2$ changed positions is correct. We will then show how to get rid of this assumption with only a constant overhead.

We will now use the following “conveyor belt” strategy (see Algorithm 1): take the sequence of $n-1$ adjacent transpositions $(\mathrm{1\hspace{0.17em}2}),(\mathrm{2\hspace{0.17em}3}),\mathrm{\dots },(n-1n)$ and repeat it $n$ times. For example for $n=4$, this strategy guesses:

The nice property of this sequence of adjacent transpositions is that each element goes through every position, and thus, since the codemaker is generous, after this sequence of guesses, the codebreaker will know exactly what the secret permutation is.

More formally, for each value $1⩽m⩽n$ (line 3 of Algorithm 1), the first element of ${\pi }^{\prime }$ right after line 4 is $m$, and it will be at position $2⩽j⩽n$ after exactly $j-1$ guesses. Thus, the exact position of $m$ must be revealed by the generous codemaker on that pass.

After having identified the position of each element, the codebreaker knows the target permutation, and can reach the secret permutation through a shortest path. Using the well-known identity $\text{diam}(S_n,W_2)=\left(\genfrac{}{}{0pt}{}{n}{2}\right)$, the codebreaker will reach the secret permutation in $O(n^2)$ guesses.

Now, it only remains to show how to simulate the generous codemaker with only a constant factor overhead. For this, consider for example that for $n=3$ the last guess was $(\mathrm{1\hspace{0.17em}2\hspace{0.17em}3})$ and we now want to guess $(\mathrm{2\hspace{0.17em}1\hspace{0.17em}3})$ but receiving generous feedback. We will do the sequence of guesses: $(\mathrm{1\hspace{0.17em}2\hspace{0.17em}3})\to (\mathrm{1\hspace{0.17em}3\hspace{0.17em}2})\to (\mathrm{3\hspace{0.17em}1\hspace{0.17em}2})\to (\mathrm{3\hspace{0.17em}2\hspace{0.17em}1})\to (\mathrm{2\hspace{0.17em}3\hspace{0.17em}1})\to (\mathrm{2\hspace{0.17em}1\hspace{0.17em}3}).$ Intuitively, the scores received throughout this sequence will uniquely determine the “generous” feedback for the guess $(\mathrm{2\hspace{0.17em}1\hspace{0.17em}3})$. More in general, we will replace each transposition $(ii+1)$ by $6$ guesses that traverse the $6$ possible permutations of $\{i,i+1,i+2\}$ (or $\{i-1,i,i+1\}$ in case $i=n-1$). The fact that going through the $6$ permutations allows us to determine if any of the $3$ cycled elements should go into one of the $3$ positions of the cycle can be checked via finite computation. Indeed, the following Python3 code is enough: