6
$\begingroup$

There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of vertices growing linearly, such that the number of matchings (not complete matchings) of $G_i$ is the $i$th Catalan number?

I have checked Richard Stanley's book on Catalan numbers, but such an interpretation is not there. The closest I found is a family of graphs, where one counts the number of complete matchings, but this is not what I am after.

Edit: I thought that the linearity condition was sufficient to force nice answers, but perhaps not. Ok so there is the classical recursion for Catalan numbers, $$C_{n+1} = \sum_k C_k C_{n-k}.$$ The family of graphs should be defined such that the number of matchings is seen to satisfy the above recursion without too much work.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Write the $n$th Catalan number as $C_n = p_1 p_2 \cdots p_k$ where the $p_i$'s are prime numbers. Define $G_n$ to be the disjoint union of $k$ star graphs, where the $j$th star graph has $p_j$ vertices. Then it is easy to see that the number of matchings of $G_i$ is $C_n$ (we can choose at most one edge from each star graph, and the $j$th star graph has $p_j-1$ edges). Since Catalan numbers have a nice product formula, all the $p_j$ will be $\leq 2n$; thus, I'm not sure if this $G_n$ has linear in $n$ number of vertices, but its number of vertices will not be huge. $\endgroup$
    – Sam Hopkins
    Commented Mar 22, 2023 at 18:39
  • $\begingroup$ @SamHopkins Ok, so there is another condition; the family of graphs should be 'appealing' in a combinatorial sense. That is, it should have been included in Stanley's book. $\endgroup$
    – Per Alexandersson
    Commented Mar 22, 2023 at 18:53
  • 1
    $\begingroup$ @FedorPetrov: you can convert the usual Dyck path interpretation of Catalan numbers to perfect matchings in a certain graph made out of hexagons, in the usual way. See e.g. "Perfect Matchings, Catalan Numbers, and Pascal's Triangle" by Došlić (jstor.org/stable/27643031). But I think this graph will have a quadratic number of vertices, not linear. $\endgroup$
    – Sam Hopkins
    Commented Mar 22, 2023 at 21:44
  • 1
    $\begingroup$ @SamHopkins thank you! By the way, your graph certainly has superlinear number of vertices, since all prime between $n+2$ and $2n$ divide $C_n$, and there are many of them. $\endgroup$
    – Fedor Petrov
    Commented Mar 23, 2023 at 4:48
  • 2
    $\begingroup$ @SamHopkins Ah, yes, ok quadratic for the complete matching case, it is figure 2 in Stanleys .pdf: math.mit.edu/~rstan/ec/catadd.pdf $\endgroup$
    – Per Alexandersson
    Commented Mar 23, 2023 at 5:42

0

Reset to default

You must log in to answer this question.