3
$\begingroup$

This question is inspired by "Number of collinear ways to fill a grid" by Sebastien Palcoux and the comments of user44191 on this earlier question of Palcoux's.

Let $G=(V,E)$ be a graph. An edge ordering of $E$ (or $G$) is a bijection $\phi$ from $\{1,\dots,|E|\}$ to $E$. Let $G_k$ be the graph induced by the edge set $E_k=\{\phi(i)|1\leq i \leq k\}$. An edge ordering is connected if $G_k$ is connected for all $1\leq k\leq |E|$.

How many connected edge orderings are there for $G=K_n$, the complete graph on $n$ vertices?

Asymptotics would be fine, but I suspect there might be a nice closed-form expression:

For $K_{m,n}$ (the complete bipartite graph on sets of $m$ and $n$ vertices) the conjectured answer is $m!n!(mn)!/(m+n-1)!$, from "Number of collinear ways to fill a grid". This is because there's a bijection between connected edge orderings of $K_{m,n}$ and collinear $m\times n$ grid fillings (take the row and column sets to be the vertex sets of $K_{m,n}$ and grid squares to be the edges).

edit:

As Richard Stanley points out (and as I could have deduced if I'd looked at the earlier questions of Sebastien Palcoux), connected edge orderings of a graph are the same as shellings of that graph viewed as a 1D simplicial complex.

Here are SageMath implementations of user44191's recursion formula in the comments and Richard Stanley's formula in his answer (removing the factor of $n!/2$ coming from different orderings of the vertices). 

def partialrecursionformula(m,n):
    if [m,n] == [1,0]:
        return 1
    elif n<m-1 or m==0:
        return 0
    else:
        i=n-1
        return ((m*(m-1)/2 - i)*partialrecursionformula(m,i)
                + (m-1)*partialrecursionformula(m-1,i))

def recursionformula(m):
    return partialrecursionformula(m,m*(m-1)/2)

def stanleyformula(m):
    f = [rising_factorial(i*m - i*(i+1)/2 + 1, m-i-2) for i in range(m-2)]
    return factorial(m-1)*prod(f)

Numerically, they agree at least up to $K_{8}$ (I am convinced that they both count the connected edge orderings correctly for all $n$, so this was just a check that there are no typos).

The sequence of the number of shellings of $K_n$ that reach the vertices in order thus begins 1, 1, 2, 48, 34560, 1383782400, 4914953551872000, 2256176006302688870400000, and it's easy to get more values with Richard Stanley's formula.

edit 2: Fedor Petrov points out in the comments that this question (phrased in terms of probabilities) has already been asked and answered here.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ You have a similar recursion relation. Let $g(m, n)$ be the number of partial connected edge orderings with $n$ edges on $K_m$ that have reached every vertex. Your specific answer is $g(m, \frac{m (m + 1)}{2})$. Let $\tilde{g}(m, n) = 2 \frac{g(m, n)}{m!}$. This represents the number of partial connected edge orderings that reach every vertex in $K_m$ in order (with ambiguity allowed for the first two vertices). Then we have the following recursion relation: $\tilde{g}(m, n + 1) = (\frac{m(m + 1)}{2} - n) \tilde{g}(m, n) + (m - 1) \tilde{g}(m - 1, n)$ $\endgroup$
    – user44191
    Apr 9, 2018 at 20:40
  • 2
    $\begingroup$ @user44191 I believe your recursion should be $\tilde{g}(m,n+1)=(\frac{m(m-1)}{2}-n)\tilde{g}(m,n)+(m-1)\tilde{g}(m-1,n)$, and the number I'm asking about is actually $g(m,\frac{m(m-1)}{2})$. With those corrections, it agrees with Richard Stanley's formula (at least up to $n=8$ with my slow sage code). $\endgroup$
    – j.c.
    Apr 10, 2018 at 12:07
  • $\begingroup$ @jc You are, of course, correct. $\endgroup$
    – user44191
    Apr 10, 2018 at 22:01
  • 3
    $\begingroup$ mathoverflow.net/questions/199342/… is it the same question? looks so $\endgroup$
    – Fedor Petrov
    Apr 11, 2018 at 18:08
  • $\begingroup$ @FedorPetrov Great! $\endgroup$
    – j.c.
    Apr 11, 2018 at 20:59

1 Answer 1

Reset to default
6
$\begingroup$

Write $\langle m\rangle_i=m(m+1)\cdots (m+i-1)$. There are $\frac 12 n!$ ways to choose the order in which new vertices are attached (since at the first step we attach two at once). There are $(n-1)!$ ways to choose the vertex that each new vertex is attached to. Suppose we have made these choices. Now there are $(n-2)!=\langle 1\rangle_{n-2}$ ways to choose the order in which we add the $n-2$ additional edges incident to the last attached vertex. Then there are $\langle n\rangle_{n-3}$ ways to specify how to add the additional $n-3$ edges adjacent to the next-to-last attached vertex. Then there are $\langle 2n-2\rangle_{n-4}$ ways to specify how to add the additional $n-4$ edges adjacent to the third-from-last attached vertex. Continuing in this way shows that the total number of edge orderings is $$ \frac 12n!\,(n-1)!\prod_{i=0}^{n-3} \left\langle in-\binom{i+1}{2}+1\right\rangle_{n-i-2} = \frac{2^n n! (n - 1)! \binom{n}{2}!}{4 (2n - 2)!} \text{ (see comments)}$$ Perhaps I have made a computational error, but I think the method is correct.

I can also point out, though irrelevant to the solution, that you are asking for the number of shellings of the complete graph, regarded as a one-dimensional simplicial complex.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ The formula can be made shorter, by rewriting the $\langle m \rangle_i$ as a fraction of factorials, and using the fact that the sequence telescopes (after adding in a term to each factorial). If I'm not wrong, the answer is equal to $\frac{n! (n - 1)! \binom{n}{2}!}{2 \prod_{i = 0}^{n - 2} n (i + 1) - \binom{i + 2}{2}}$. $\endgroup$
    – user44191
    Apr 10, 2018 at 22:57
  • 3
    $\begingroup$ And that expression can be further simplified; $n (i + 1) - \binom{i + 2}{2} = (i + 1)(n - \frac{i + 2}{2})$, so the product is $(n - 1)! \prod_{i = 0}^{n - 2} n - \frac{i + 2}{2} = \frac{1}{2^{n - 1}} (n - 1)! \prod_{i = 0}^{n - 2} 2n - i - 2 = \frac{2}{2^n} (n - 1)! \frac{(2n - 2)!}{(n - 1)!}$, so the fully simplified formula is $\frac{2^n n! (n - 1)! \binom{n}{2}!}{4 (2n - 2)!}$ $\endgroup$
    – user44191
    Apr 10, 2018 at 22:59
  • $\begingroup$ @user44191: your comment is a nice complement to Richard Stanley's answer. You should ask him whether you can edit his answer, or you should write a complementary answer. Do you think that your conjecture for $K_{m,n}$ can be proved by: first an analogous of Richard Stanley's argument and then an analogous of your simplification? $\endgroup$
    – Sebastien Palcoux
    Apr 11, 2018 at 15:56
  • $\begingroup$ @SebastienPalcoux If it could be proven analogously, my guess is that it would extend to a proof for any edge-transitive graph. $\binom{n}{2}$ is the size of the automorphism group of the whole graph, while $n! (n - 1)!$ can be related to the number of "flags" (vertex-edge pairs); I'm not sure what relevant thing $\frac{4 (2n - 2)!}{2^n}$ expresses, but there should be some symmetry that gets it. $\endgroup$
    – user44191
    Apr 11, 2018 at 16:28
  • $\begingroup$ Err, $\binom{n}{2}$! is the number of orders of the edges, rather. $\endgroup$
    – user44191
    Apr 11, 2018 at 20:18

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