12
$\begingroup$

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, after the $k$th edge in the list is placed, the so-far created graph will have exactly $k$ edges).

Let $H_k$ be the graph induced by the first $k$ edges. Let $p(n)$ be probability that $H_k$ is connected for all $k \in \{1,2,\dots,{n \choose 2}\}$.

As a corollary to a completely different problem I'm working on, and through a very round-about way, we were able to show that the answer for $p(n)$ is beautiful. Indeed, it is simply

$$\frac{2^{n-2}}{C_{n-1}},$$ where $C_{m}$ is the $m$th Catalan number.

I'd like to find a good combinatorial reason why this is the answer.

(This is the easiest case of a more general problem I'm working on. I do have one semi-combinatorial argument but unfortunately it doesn't generalize well.)

Any thoughts would be appreciated! Thanks!!

$\endgroup$
6
  • $\begingroup$ Typo, I think you mean $p(k)$ in the definition. The formula doesn't feel quite right, but should follow from Cayley's formula for labelled trees on $n$ vertices (in this process, when $n$ edges have been added we're asking for a tree plus an edge.) $\endgroup$ Mar 8, 2015 at 0:06
  • $\begingroup$ Hmm.. I think I do mean $p(n)$. Starting with the empty graph on $n$ vertices we can add in ${n \choose 2}$ edges, one at a time, and ask whether the induced graphs were connected at every stage. Does that clear up the confusion? Or does something still seem amiss? Thanks! $\endgroup$
    – user43928
    Mar 8, 2015 at 0:17
  • $\begingroup$ I don't understand how the graphs can be connected at every stage. Do you mean that there is at most one non-singleton component? If so (and I guess that's it) then ignore my comment about Cayley's theorem! $\endgroup$ Mar 8, 2015 at 0:36
  • 1
    $\begingroup$ Exactly. The way I phrased it was that $H_k$ is the graph ${induced}$ by the first $k$ edges, but maybe your way is more clear. $\endgroup$
    – user43928
    Mar 8, 2015 at 0:38
  • 2
    $\begingroup$ The total number of such permutations now forms the sequence oeis.org/A255886 in the OEIS. $\endgroup$ Mar 9, 2015 at 11:40

1 Answer 1

11
$\begingroup$

Here's one. You can think of the graph construction process as gradually building a set $S$ of vertices that have been touched so far, beginning with a random two vertices. Let $S_k$ be the set of the first $k$ vertices in this process.

Now $p(n)$ is exactly the probability that, after the first two vertices, each additional edge we select either has both endpoints in the current $S_k$, or else crosses the cut between $S_k$ and the rest of the graph. (In this case, the other endpoint becomes the next vertex to add to our set.)

Thus $p(n)$ is the probability that, at each set size $k$, conditioned on picking an edge that does not have both endpoints in $S_k$, the edge selected crosses the cut. Well, the number of edges crossing the cut is exactly $k(n-k)$, and the number of edges entirely outside of $S_k$ is exactly ${n-k \choose 2}$. Therefore the probability of picking an edge crossing the cut conditioned on one of these occurring is exactly \begin{align} \frac{k(n-k)}{k(n-k) + {n-k \choose 2}} &= \frac{2k}{2k + n-k-1} \\ &= \frac{2k}{n + k - 1} \end{align}

As base cases, immediately $p(2) = 1$. For $n \geq 3$, we get \begin{align} p(n) &= \prod_{k=2}^{n-1} \frac{2k}{n-1 + k} \\ &= 2^{n-2} \prod_{k=2}^{n-1} \frac{k}{n-1 + k} \\ &= 2^{n-2} \frac{1}{C_{n-1}} . \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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