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!!

Improve this question
$\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$
    – Michael Albert
    Commented 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
    Commented 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$
    – Michael Albert
    Commented 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
    Commented 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$
    – Max Alekseyev
    Commented Mar 9, 2015 at 11:40

1 Answer 1

Reset to default
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}

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .