2
$\begingroup$

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.

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$.

Variation:

We also have, I think, $C_{n-4} \leq P_n^{3n-6}$ for $n\geq 4$. (I had an off-by-one error in a previous version of the question.)

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ My prev. answer did not take planarity into consideration - I somehow missed that condition. $\endgroup$
    – Per Alexandersson
    Commented Nov 16, 2023 at 18:01
  • 2
    $\begingroup$ Can you do the following: take a triangulation of an n-gon and then add a cone vertex (a vertex connected to all the other ones), to get a 3-connected planar graph? $\endgroup$
    – Sam Hopkins
    Commented Nov 16, 2023 at 18:21
  • $\begingroup$ Yes, but I think that this is not injective. Perhaps it works if we join the cone vertex to all the original vertices except the root? $\endgroup$
    – Martin Rubey
    Commented Nov 16, 2023 at 19:52
  • 1
    $\begingroup$ A000944 is counting isomorphism classes, i.e., unlabelled graphs. $\endgroup$
    – Martin Rubey
    Commented Nov 16, 2023 at 19:56
  • 1
    $\begingroup$ Yes, I meant with the adjustment. If the root vertex and it's two neighbors in the n-gon form a triangle, the adjusted cone construction is not three connected. $\endgroup$
    – Martin Rubey
    Commented Nov 16, 2023 at 20:10

0

Reset to default

You must log in to answer this question.