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 $k$ for which we can show that, for $\pi_1,\dotsc,\pi_k$ taken independently and at random (in the weak sense above), $\Gamma^{\pi_1} \cup \Gamma^{\pi_2} \cup\dotsc \cup \Gamma^{\pi_k}$ 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 $k\ll \log n$. I can show $k\ll \log \log n$ (not a great deal harder).

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