2
$\begingroup$

So I am given $n$ points in the plane and I want to create a planar graph such that every face is bounded by $3$ edges (even the "outside" face). Hence if I have say $4$ vertices, then there is a unique way to triangulize it, make all edges adjacent to each other.

Let $L_n$ denote the number of triangulations on $n$ points. I was thinking a way to count $L_n$. To go from $L_4$ to $L_5$ we have an extra vertice that is placed in one of the faces, then in order to triangulize it we can match that point with the vertices of the triangule that points lives in. Since there are $4$ ways of picking which face to place the new vertex we have $L_5=4$. Note that the number of faces goes up by $2$ since we are destroying one face and adding $3$ new ones. Hence $L_6=6L_5$, and in general I would have that $L_n=2^{n-4}(n-3)!$.

I was wondering what is wrong with the above argument since my homework says "Prove $\lim \log L_n$ as $n\rightarrow \infty$ exists" (Since this is homework please only give me hints towards the correct solution, thanks)

  • 1
    For the limit of $\log L_n$ to exist, the limit of $L_n$ would have to exist. If you can prove that the number of triangulations is unbounded, you have busted the problem. Or copied it down wrong.2012-10-15
  • 2
    Since one would typically expect this sort of thing to grow exponentially and the growth rate can be defined via $\lim_{n\to\infty}\frac1n\log L_n$, it seems likely that a factor $\frac1n$ went missing. Regardless of that, I think you're overcounting because you can reach the same result by adding points in different orders.2012-10-15
  • 0
    Yes, Daniel, I am pretty sure this was a typo as joriki says. Compare your count with http://oeis.org/A0002562012-10-15
  • 0
    @IgorPak Yes, the above count is bad, but I still dont quite know exactly what we are counting. For instance say we are given $5$ points $A,B,C,D,E$ in the plane. Then a triangulation must have score $(4,4,4,3,3)$ so as long as we specify which vertices are the ones with degree $3$ then we are done, so the count ought to be $\binom{5}{2}=10$, which does not appear on the oeis that you linked.2012-10-16
  • 0
    In fact it says that the number of triangulations of the plane with $n=5$ is zero, so I am sort of confused.2012-10-16
  • 0
    I think for the problem, the precise definition is unimportant as long as they are unlabeled and up to homeomorphism either on the plane or on a sphere (I like the sphere).2012-10-16

0 Answers 0