7
$\begingroup$

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross each other.

I am interested in the integer sequence for the number of noncrossing acyclic digraphs on $n$ vertices. I computed the first few terms of this sequence using a brute-force method. Starting with $n = 1$, they are:

1, 3, 25, 335, 5521

I was not able to find this sequence in the OEIS, which does contain integer sequences for many other classes of noncrossing graphs.

Does anybody know the sequence, or has an idea for how to derive it? Thanks for your time!

$\endgroup$
  • $\begingroup$ Could you explain what are the 3 things on 2 vertices ? Oh, I see, not necessarily connected, so that you have $1 \to 2$, $ 2 \to 1$ and $1 2$ with no arrow. $\endgroup$ – F. C. Jul 24 '14 at 13:17
  • 1
    $\begingroup$ Are the vertices labelled, or are these some sort of equivalance classes? $\endgroup$ – Brendan McKay Jul 24 '14 at 13:42
  • $\begingroup$ The vertices are labelled, say numbered from $1$ to $n$. I will update the question to make this more clear. Thanks! $\endgroup$ – Marco Kuhlmann Jul 24 '14 at 17:01
11
$\begingroup$

You can split noncrossing graphs and get equations for the generating functions. I like to take the minimal root edge (if it exists). $$N=1+xN+2xN\bar N$$ This says that an acyclic noncrossing graph is either empty ($1$), or has an isolated root ($xN$), or has a minimal root edge ($2$ counts either direction) with a noncrossing graph on one side and an edge-rooted noncrossing graph on the other side (counted by $\bar N$). But now we have to deal with $\bar N$. $$\bar N = \frac{1+xN}{(1-2x\bar N)^2}+\frac{4x\bar N^2}{1-2x\bar N}-\frac{x\bar N^2}{1-x\bar N}$$ It's easier to explain this one with a picture. $\bar N$ explanation Note that $x$ is not counting the root(s), so if you need to weight the root you'd get $x\bar N$. If you need to include the (truly) empty case too you'd need $1+xN$, as in both equations above. You could easily modify these equations to count by components with $z$ by replacing $1+xN$ with $1+xzN$ in both equations.

Then we can compute: $$N(x)=1 + 3x + 25x^2 + 335x^3 + 5521x^4 + 101551x^5 + 1998753x^6 + 41188543x^7 + 877423873x^8 + 19166868607x^9 + \dots$$ $$\bar N(x)=1 + 8x + 106x^2 + 1740x^3 + 31944x^4 + 628040x^5 + 12932888x^6 + 275367248x^7 + 6013043424x^8 + 133923593728x^9 + \dots$$ This method works in general for counting types of noncrossing graphs weighted by different things but the equations can get monstrous.

$\endgroup$
  • $\begingroup$ Thanks Jordan, looks like a great answer! Is your way of counting this particular class of graphs something that you have just come up with, or is it from previous work of yours? In that case, perhaps you could point me to a paper? $\endgroup$ – Marco Kuhlmann Jul 25 '14 at 7:00
  • $\begingroup$ I did a general version counting noncrossing digraphs by components, vertices, edges, inititally connected vertices, and cyclic edges simultaneously. The same method above works but there are many cases and many equations. I never wrote it all down formally but it is on my to-do list. I have some handwritten notes and Sage code I could dig up in the meantime. $\endgroup$ – Jordan Jul 25 '14 at 13:54
  • 1
    $\begingroup$ I added a picture. Let me know if it is clear now. $\endgroup$ – Jordan Jul 27 '14 at 0:45
  • 1
    $\begingroup$ Just one more question: In the unconnected sub-case, why do count $1 + xN$ and not $N$. Could the graph ‘in the middle’ not be an edge-rooted graph. Concrete example: $n = 4$, edges $1 \to 4$, $2 \to 3$ $\endgroup$ – Marco Kuhlmann Aug 1 '14 at 12:17
  • 1
    $\begingroup$ My generating functions do not include the root(s) when counting vertices (and therefore also don't count the truly empty case where there is no root). If you want these things you'd get $1+xN$. I think this makes the equations much nicer but it gets me mixed up sometimes too. I edited my explanation above. $\endgroup$ – Jordan Aug 1 '14 at 17:07
1
$\begingroup$

It is well known that evaluation of the chromatic polynomial of a graph gives (up to sign depending only on the number of vertices) the number of its acyclic digraph. Therefore it is enough to solve the stronger problem: How many pairs (noncrossing graph on $n$ points,good $k$-coloration of it) are there?

Let $f(n,k)$ be that number. Let also $g_1(n,k)$ be that but with restriction that point 1 must be with color 1; $g_2(n,k)$ with restriction that point 1 must have color 1 and point 2 must have color 2, but they are not connected to each other; $g_3(n,k)$ with the restriction that both points 1,2 must have the color 1. (We define $g_1$ only for $n \geq 1$ and $g_2,g_3$ only for $n \geq 2$)

Now the following can be proven:

  • $f(n,k)=k g_1(n,k)$
  • $g_1(n,k)=g_3(n,k)+2(k-1) g_2(n,k)$
  • $g_2(n,k)=g_1(n-1,k)+\sum_{m=2}^{n-1} g_2(n-m+1,k)\left(g_3(m,k)+2(k-2)g_2(m,k)\right)$
  • $g_3(n,k)=g_1(n-1,k)+\sum_{m=2}^{n-1} 2g_2(n-m+1,k)g_2(m,k) (k-1)$

The first two are trivial, and the last two follows from considering the first point that connects to point 1, and dividing the graph to two smaller graphs.

From those relations it is possible to obtain algebraic relations between the ordinary generating functions (over variable $n$). It follows from the calculation that $\sum_{n=0}^{\infty} f(n,k) x^n$ is an algebraic function, a solution of degree 3 polynomial that can be calculated explicitly.

$\endgroup$
  • $\begingroup$ I did not write all the detail because I need to sleep $\endgroup$ – user49822 Jul 24 '14 at 20:18
  • $\begingroup$ Thanks user49822, but I am afraid that I do not immediately get the idea behind your counting method. $\endgroup$ – Marco Kuhlmann Jul 25 '14 at 7:06
  • $\begingroup$ @MarcoKuhlmann The general idea is the "rule of thumb" that acyclic orientation of graph is the same as good $-1$-vertex-coloration of the graph. (I use this because I think building graphs with a coloring is easier conceptually than acyclic digraphs). Rigorously, let $f(n,k)$ as defined above. Then it is equal to the sum over all noncrossing graphs on n points, of their chromatic polynomial evaluated at k. In particular, this is a polynomial in k (for any fixed n). So we can substitute $k=-1$ and the result is what you asked (times $(-1)^n$) $\endgroup$ – user49822 Jul 25 '14 at 11:08

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.