Skip to main content
6 of 7
deleted 3 characters in body
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Injection of Catalan objects into 3-connected planar graphs

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Update:

Let $P_n^m$ be the number of three-connected planar graphs on $n$-vertices with $m$ edges. In particular, $P_n^{3n-6}$ are the triangulations. I think we have, in fact, $C_{n-3} \leq P_n^{3n-6}$ for $n\geq 4$.

Is there a nice injection from $C_{n-3}$ into $P_n^{3n-6}$?

Here is an alternative refinement:

Let $C_n^m$ be the number of Dyck paths of semilength $n$ with $m$ returns, i.e., https://www.findstat.org/StatisticsDatabase/St000011.

Then, it seems that $C_{n-3}^{m - 2n + 3} \leq P_n^m$ for $n\geq 4$ and all $m$, or, if you prefer, $C_n^m \leq P_{n+3}^{2n+3+m}$ for $n\geq 1$.

Martin Rubey
  • 5.8k
  • 1
  • 24
  • 39