When is the union of a graph and a random permutation thereof connected?

Question

First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and more weakly, it will mean a permutation chosen randomly in such a way that, for $k$ bounded (say $k\leq 100$, if you wish), the probability that a particular element of the set $\Omega^{(k)}$ of $k$-tuples of distinct elements of $\Omega$ will be taken to another particular element of $\Omega^{(k)}$ is contained in $\left(\frac{1-\epsilon}{\left|\Omega^{(k)}\right|},\frac{1+\epsilon}{\left|\Omega^{(k)}\right|}\right)$, where $\epsilon$ is very small.

Let $\Gamma=(\Omega,E)$ be a graph with $\Omega$ as its set of vertices, such that every vertex lies on at least one edge. (Say "exactly one edge", if you wish.) Given $\pi\in \textrm{Sym}(\Omega)$, write $\Gamma^\pi$ for the graph $(\Omega,E^{\pi})$ to which $\pi$ sends $\Gamma$.

(a) Can it be shown that $\Gamma\cup \Gamma^\pi$ is connected with positive probability, or that it has a large connected component (with $>0.9 |\Omega|$ vertices, say) with positive probability?

(b) What is the smallest $\ell$ for which we can show that, for $\pi_1,\dotsc,\pi_\ell$ taken independently and at random (in the weak sense above), $\Gamma^{\pi_1} \cup \Gamma^{\pi_2} \cup\dotsc \cup \Gamma^{\pi_\ell}$ has a large connected component with positive probability?

---

My intuition is that the answer to (a) is "no". As for whether the answer to (b) should be "a constant": I do not know! It is easy to show that $\ell\ll \log n$. I can show $\ell\ll \log \log n$ (not a great deal harder).

Answer 1

I will assume that $\Gamma$ is regular of degree $1$ (so $n=2m$ for some $m$.) You say that you don't care specifically about the uniform distribution on $S_n=S_{2m}.$ However I will deal mainly with that case. At the end I'll argue that your weaker condition might lead to about the same results, but that is a guess.

$\Gamma$ has $2m$ vertices and $m$ edges. Imagine they are red. Also $\Gamma^{\pi}$ has $m$ edges, imagine they are green. Then in $G= \Gamma \cup \Gamma^{\pi},$ each vertex is on one edge of each color so $G$ is the union of one or more even length cycles (including the possibility of a digon, a cycle of length $2$ with two points and two edges, one of each color.)

Consider these probabilities

• $p_m(k)$ is the probability that the cycle containing a particular (red) edge $e$ has length $2k$

• $q_m(k)$ is the probability that the largest cycle in $G$ has length $2k.$

After some work it turns out that, for $t=m-k,$

$$p_m(k)=\frac1{2m-1}\frac{\binom{2t}t}{2^{2t}}\frac{2^{2m-2}}{\binom{2m-2}{m-1}}$$

Also, for $\frac{m}2 \lt k \leq m,$ $$q_m(k)=\frac{mp_m(k)}k.$$

I have nice proofs for these formulas. They show good agreement with the results of random computations.

---

simulation details

I did $100,000$ trials with $m=15.$ The expected numbers (out of $10^5$) with longest cycle of length at least $16,18,\cdots,30$ are the first line below. The second is the actual values from the trial:

$$89290, 80228, 71553, 63035, 54432, 45418, 35435, 23074$$

$$89211, 80202, 71542, 63137, 54448, 45530, 35359, 23062$$

---

In particular, the probability that $G$ is connected is $$p_m(m)=\frac{2^{2m-2}}{(2m-1)\binom{2m-2}{m-1}} \approx \sqrt{\frac{\pi}{4m}}. $$

For $t=m-k$ not too small, $$p_m(k) \sim \frac{\sqrt{\frac{m}t}}{2m-1}.$$

I would expect, for reasons given in a moment, that the probability that the longest cycle is at least $ 2m\rho$ (for $\rho \gt \frac12$) should converge to a limit.

Here are the calculated probabilities to be above $ 2m\rho$ for $\rho=0.5,0.6,0.7,0.8,0.9.$ The first line is for $m=200$ and the next for $m=400:$

$$.70666, .63186, .54692, .44610, .31445$$ $$.70689, .63216, .54732, .44665, .31534$$

The reason I suspected this was that (as is well known) for a random permutation of $X$ , a set of size $n,$ one has probability that the cycle of $x$ has length $k$ is independent of $k:$ $$p_n(k)=\frac1n$$ and the probability that the longest cycle has length $k$ is (for $\frac{n}2 \lt k \leq n$) is independent of $n:$ $$q_n(k)=\frac1k$$

So the probability that the longest cycle has length at least $j=\rho n \gt \frac{n}2$ is $$\sum_{k=j}^n\frac1k \sim -\ln{\rho}.$$

Regarding random permutations

Certainly, saying that each permutation is chosen with probability $\frac{1+\varepsilon}{n!}$ with $|\varepsilon|$ sufficiently small will satisfy your condition (essentially, this is just your condition for $k=n.$). I wonder if the converse is true?

I guess, under that assumption, the results for $\Gamma \cup \Gamma^{\pi}$ (such as they are) would stay pretty much the same. It might be delicate Perhaps it would be worth studying the simpler problem of cycles in $S_n$ under that variation.

In a (now hidden) comment you describe the process of a random walk on a connected Cayley Graph for $S_n$. This does converge rapidly to the uniform distribution (the metric being $\sum_{S_n}|p(\pi)-\frac1{n!}|.$ Certainly some choices converge faster than others but it is (after a while) an exponential decay.

As you may know, Persi Diaconis has nice results for this. An easy overview is here with more detailed results easy to find. If we have an $n! \times n!$ matrix where each row has all entries $0$ except that $k$ of them are $\frac1k$ then no power will have all entries $\frac1{n!}.$ However there are strong stopping rules (such as wait until a certain event occurs, then do one more multiplication) which, if followed, will eventually give the uniform distribution. We can't say what the stopping time is, there is a minute chance that it is huge, but I recall results such as "the stopping time is almost surely less than $\frac32 n log_2 n.$"