13
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Do you consider $k$-tuples to be ordered or just subsets of $\Omega$ (likely the latter, but I just wanted to clarify)? $\endgroup$ Nov 14 '17 at 14:50
  • $\begingroup$ @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) $\endgroup$
    – js21
    Nov 14 '17 at 15:07
  • $\begingroup$ Mikhail: ordered tuples. $\endgroup$ Nov 14 '17 at 15:25
  • $\begingroup$ 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$. $\endgroup$ Nov 14 '17 at 16:03
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Nov 16 '17 at 17:46
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ "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)$. $\endgroup$ Nov 23 '17 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.