A ten-level 2-tree is drawn in the plane: a vertex is marked, it is connected by segments with two vertices and , each of and is connected by segments with two of the four vertices (each is connected with one exactly); and so on, up to 512 vertices . Each of the vertices is coloured blue or golden. Consider all permutations of the vertices of this tree, such that (i) if and are connected with a segment, then so are and , and (ii) if is coloured, then has the same colour. Find the maximum such that there are at least permutations with these properties, regardless of the colouring.
Solution
The answer is . First we need a suitable terminology. Similarly to 10-level 2-tree we can define a -level 2-tree for . For convenience we suppose that all the segments between vertices are directed from a letter to the next one. The number of the letter marking a vertex we call the level of this vertex; thus is the only vertex of level and belong to level 2 and so on). We will also call descendants of a vertex all vertices which can be reached from by directed segments. Let and be two -level 2-trees with coloured leaves. We call a bijection isomorphism when two conditions are satisfied: (i) if two vertices and are connected by an edge in , then and are connected by an edge in , and (ii) if has some colour in , then has the same colour in . When , we call automorphism of the tree. By we denote the minimal number of automorphisms a -level 2-tree with coloured leaves can have (the minimum is over all colourings). Our problem is to find . We start with almost obvious Lemma 1. Isomorphism of trees preserves the level of a vertex. Proof. Isomorphism cannot diminish the degree of a vertex. Indeed, neighbours of each vertex become neighbours of , therefore the degree of is not less than the degree of . By pigeonhole principle it also means that the degree can not increase. It follows that the last level vertices go to the last level vertices. Therefore vertices of the previous level go to the same level, since they remain neighbours of the last-level vertices, and so on. Now we are ready to solve the problem. Proposition 1. For each we have . Proof. In a -level tree the descendants of (including ) form a -1-level tree . This graph has at least different automorphisms. The same is true for tree formed by the descendants of . Let and be automorphisms of and respectively. Now we can define mapping of the whole tree applying to descendants of to descendants of and to itself. Obviously is an automorphism: for the condition holds since and were mapped to themselves (by Lemma 1 ), and for in or because and are automorphisms. Thus for each pair there is an automorphism , different pairs produce different , and the number of pairs is at least . Corollary. For we have . Proof. This inequality is proved by induction, with Proposition 1 as induction step. It remains to check it for . If in a 3 -level 2 -tree at least one of the vertices has two descendants of the same colour, there is an automorphism exchanging these two vertices and preserving the rest. If each of has one blue and one golden descendant, there is an automorphism exchanging and and preserving colours of their descendant. In both cases the number of automorphisms (including the identical one) is at least 2. We already know that every 3-level 2-tree with (four) coloured leaves there are at least two colour-preserving automorphisms. Now every -level tree, , has vertices of level , and the descendants of each of these vertices form a 3-level tree. It is enough to consider automorphisms preserving vertices of level (and, a fortiori, of all lesser levels). Such an automorphism can act on the descendants of each of vertices of level in at least 2 ways. Thus there are at least such automorphisms. It remains to construct for each a colouring of -level tree a colouring admitting exactly automorphisms. As it happens sometimes, we will prove somewhat more. Proposition 2. For each there are three colourings of leaves of -level 2-tree such that the trees with these colourings are not isomorphic, and each of these colourings admits automorphisms exactly. Proof. For let be the descendants of , and the descendants of . The three colourings are the following: blue, golden; golden, blue; blue, golden. Obviously the trees with these colourings are not isomorphic and admit two automorphisms each. The induction step. Let be the desired colourings of -level tree. Consider the following colourings of the -level tree: - for descendants of and for descendants of ; - for descendants of and for descendants of ; - for descendants of and for descendants of . It is quite obvious that these three colourings are not isomorphic and have the desired number of automorphisms.