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

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).

• Do you consider $k$-tuples to be ordered or just subsets of $\Omega$ (likely the latter, but I just wanted to clarify)? Nov 14, 2017 at 14:50
• @H A Helfgott : Are you able to compute the probability in (a) when the distribution is uniform? (when each vertex belongs to exactly one edge)
– js21
Nov 14, 2017 at 15:07
• Mikhail: ordered tuples. Nov 14, 2017 at 15:25
• js21: for (a), it may be a close shave, but for $k=3$, bounding the probability from above (when we pick our permutations uniformly at random from $\textrm{Sym}(\Omega)$) is easy, at least if one is happy with a large connected component. Say one wants to rule out the existence of a connected component $S$ of size $\rho n$, $0<\rho<1$. The number of possible $S$ (given $\Gamma$) is roughly $n$ choose $m$ for $m\sim \rho n$, and that is $\sim (1/\rho)^{\rho n/2}$. The probability that $S$ is a union of edges of $\Gamma^\pi$ is $\leq \rho^{\rho n/2}$. Clearly $(\rho^2/\rho)^{\rho n/2}<1$. Nov 14, 2017 at 16:03
• If I take a large-dimensional vector space over the finite field $\mathbb F_2$, then most tuples of $k$ elements are linearly independent. Hence a random linear transformation will look like a random permutation on most $k$-tuples. If we take the graph where two vertices are connected if they differ in all but the first coordinate, it takes $\log n$ random permutations to connect the graph. So this shows your $\log n$ upper bound is sharp with a relaxed version of the condition. Nov 16, 2017 at 17:46

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.$"

• "I wonder if the converse is true?" No: you can construct (randomly) a subset of $\textrm{Sym}(n)$ of size about $n^{2k}$ or so such that the uniform distribution over it satisfies the condition with positive probability (indeed with probability close to 1). Simply start with an $n$-cycle and consider its conjugates by about $n^{2k}$ random elements of $\textrm{Sym}(n)$. Nov 23, 2017 at 17:04