How many homomorphism are there for an n-node binomial tree? e.g., for n = 2, f(n)=1; n= 5, f(n)=2.

QuoteOriginally posted by: EytHow many homomorphism are there for an n-node binomial tree? e.g., for n = 2, f(n)=1; n= 5, f(n)=2.What is a homomorphism of a tree? Is it a map which permutes the nodes and leaves the levels the same?

How exactly do you define a binomial tree with 2 nodes? Also, not all binary trees with n nodes are equivalent and could have a different number of homomorphisms. For instance, the following two binomial trees both have 7 nodes, but the one on the left has only 2 homomorphisms while the one on the right has 8. (Hopefully it's clear where the edges go in the diagrams.)________X___________X ______Y___A______Y____Z____Z__B_______A__B__C_D__C__D(Sorry for the sloppy diagrams, but the forum ate my whitespace, so it had to be replaced with underscores...)

In general a graph is a set of vertices V and a map E : V x V -> {0, 1} which specifies whether two vertices have an edge between them or not. An undirected graph satisfies E(u, v) = E(v, u). A homomorphism from the graph (V, E) to the graph (W, F) preserves connectivity, so it is a map f : V -> W such that F(f(u), f(v)) = E(u, v) for all u, v in V. I assume that when Eyt says a homomorphism for an n-node binomial tree, he means an automorphism of an n-node binomial tree, i.e. f : V -> V is a bijection. In this case, f preserves degree, and the only node with degree 2 is the root, so the root is preserved. Hence since connectivity is preserved, the level of a node must be preserved as well.Unless Eyt meant something nonstandard by homomorphism of a graph.

To clarify:we can not discriminate the nodes, say, root and leaves are identical. For example, if n=2, we have only one structure:x----xif n = 4, the tree coule be any of the two forms below:x----x----x----x or x||x----x||x

Ah, okay, so basically you just mean tree, not binomial tree. In that case, yes, the root is not necessarily distinguishable, so levels need not be preserved. But again, it's not a function of n, because for example with the two graphs you gave, the first has 2 automorphisms, while the second has 6, despite the fact that both have the same number of vertices. Also, to clarify, the 2-vertex tree you show in fact has 2 automorphisms (the identity, and switching the two vertices). In your original post, you said that f(2) = 1. Also, not all 5-vertex trees have 2 automorphisms. Consider the graph with one vertex in the middle and 4 edges coming off of that vertex. This has 5 vertices and 24 automorphisms.

So you are saying that:R--X|X|XAnd R---X---X---XAre homomorphic under your discrimination function? That would break the directedness inherent in binomial trees -- you lose the parent-child discrimination of time steps.And what about this n=4 structure:......R........../..\.......A....B........\../..........C.....What types of indegree structures do you permit?

Yeah, those first two he's saying are equivalent for his purposes. Basically he's just looking at arbitrary trees, not necessarily binomial and not necessarily with a well-defined root node.That last one is not a tree, since it contains a cycle. In finance it's often called a binomial tree, but that's a bit of a misnomer from the graph theory perspective.

QuoteOriginally posted by: mhughesThat last one is not a tree, since it contains a cycle. In finance it's often called a binomial tree, but that's a bit of a misnomer from the graph theory perspective.Right, that graph which is cyclic if the edges are undirected and which isn't a tree (but might be misnamed an example of a binomial tree) is only admissible for binomial processes that are commutative (i.e., path independent).It seems we're left with homomorphisms of trees of degree 3 or less.