2
$\begingroup$

I apologize if the questions are too elementary for the forum, but I am not an expert in this fields.

  1. How many (rooted or unrooted) binary trees with $n$ vertices are there up to isomorphism?

  2. How many maximal planar graphs with $n$ nodes are there up to isomorphism?

  3. How many graphs with $n$ nodes and valence $v$ at every node are there up to isomorphism?

$\endgroup$
  • 2
    $\begingroup$ Have you tried OEIS? It is the usual first place to look for sequences like this. $\endgroup$ – Russ Woodroofe Oct 23 '13 at 2:00
  • $\begingroup$ OEIS = On-line Enciclopedia of Integer Sequences? I am basically looking for a compact formula in order to establish the growth rate, not just a table of numbers. $\endgroup$ – yanglee Oct 23 '13 at 2:06
  • $\begingroup$ Question 1 is unclear. Are you allowing nodes with a single child? What version of isomorphism do you have in mind? For full binary trees where L and R are distinct, the number is the Catalan number. There's certainly no "compact formula" for question 3. $\endgroup$ – Alon Amit Oct 23 '13 at 2:21
  • 8
    $\begingroup$ The idea of OEIS is, you type in the numbers you know (or even a key phrase), and it gives you lots of information, including formulas if there are any. $\endgroup$ – Gerry Myerson Oct 23 '13 at 2:25
  • $\begingroup$ 2 and 3 are difficult and important problems. $\endgroup$ – Gil Kalai Oct 23 '13 at 5:27
5
$\begingroup$

For question 1, I believe you refer to unordered trees, for which a summary of the available information is given page 4 of "The CRT is the scaling limit of unordered binary trees" by Marckert and Miermont, Random Structures & Algorithms, 2011. Also see Sloane A001190, for the Etherington-Wedderburn numbers, and Otter for an asymptotic formula. There is also something in Flajolet Sedgewick Analytic Combinatorics, according to Marckert and Miermont. Quoting Marckert and Miermont, the generating function: $$\mathfrak{T}(z)=\sum_{n\geq 1}T_n\, z^n$$ of rooted binary trees unordered trees counted by the number of leaves satisfies $$\mathfrak{T}(z)=z+\frac{\mathfrak{T}(z^2)+\mathfrak{T}(z)^2}{2}\, ,$$ leading to an asymptotic formula $$T_n\sim_{n\to\infty}^{}\frac{c}{2\sqrt{\pi} n^{3/2}\varrho^n},$$ in which $\varrho$ is the radius of convergence of $\mathfrak{T}$. I would say that this is actually taken from R. Otter, "The number of trees", Ann. of Math. (2), 49, 583-599, 1948, but did not check. For general unordered trees, elements of answer seem to date back to Cayley 1857 for the equation satisfied by the generating function, and to Polya 1937 for the asymptotic formula (see Flajolet Sedgewick page 67).

I must add it is a rather common view that counting up to isomorphism is often much more difficult than "regular counting".

In the same order of idea, I should perhaps cite L. B. Richmond and N. C. Wormald. Almost all maps are asymmetric. J. of Combinat. Theory, Ser. B, 63(1):1–7, 1995. that says the group of isomorphisms of a planar map is nontrivial only for an exponentially small fraction of the set of planar maps with $n$ faces, edges or vertices (to be checked).

The enumeration of planar graphs has received a satisfactory answer only very recently, I think, see "Asymptotic enumeration and limit laws of planar graphs", Omer Giménez and Marc Noy, J. Amer. Math. Soc. 22 (2009), 309-329. I don't think that the enumeration is up to isomorphism, but this should not make any difference for the asymptotics if the result of Richmond and Wormald extends from planar maps to planar graphs.

$\endgroup$
1
$\begingroup$

(1) for rooted trees could be tackled by generating functions, as an isomorphism type of order $n$ is a choice of two isomorphism types whose orders sum to $n-1$. (The details depend on exactly what type of binary trees you want to look at.) Somebody else might be able to say more about this.

(2) and (3) are hard and open in general. (3) has appeared as a question at least twice before: see this question for some discussion of the problem.

$\endgroup$
1
$\begingroup$

One good source for information on the sort of questions you're asking about is "Graphical Enumeration" by Harary and Palmer (although I do not recall that it has anything about planar graphs).

As noted by Ben Barber above, exact answers to (2) and (3) are not known, but there are very good asymptotic estimates available.

$\endgroup$
  • $\begingroup$ Thank you. The asymptotic estimates for (2) and (3) are in the book you mentioned? $\endgroup$ – yanglee Nov 6 '13 at 22:00
  • $\begingroup$ I do not have a copy at hand, so I cannot check now. $\endgroup$ – Chris Godsil Nov 7 '13 at 2:42

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.