This post is related to “Geometric Ruzsa triangle inequalities and metric spaces with dilations“. This time the effort goes into understanding the article arXiv:1101.2532 Plünnecke’s Inequality by Giorgis Petridis, but this post is only a first step towards a geometric approach to Plünnecke’s inequality in spaces with dilations (it will be eventually applied for Carnot groups). Here I shall define a class of decorated binary trees and a notion of closeness.

I shall use binary decorated trees and the moves R1a and R2a, like in the post “A roadmap to computing with space“:

To these move I add the “linearity moves”

* Definition 1.* These moves act on the set of binary trees with nodes decorated with two colours (black and white) and leaves decorated with elements of the infinite set of “variable names” . I shall denote by … such trees and by … elements of .

The edges of the trees are oriented upward. By convention we admit to be a subset of , thinking about as an edge pointing upwards which is also a leaf decorated with .

The moves act locally, i.e. they can be used for any portion of a tree from which looks like one of the patterns from the moves, with the understanding that the rest of the respective tree is left unchanged.

____________________

* Definition 2. * The class of finite trees is the smallest subset of with the properties:

- ,
- if then , where is the tree

- if then , where is the tree

- if and we can pass from to by one of the moves then .

____________________

The class of finite trees is closed also with respect to other operations.

* Proposition 1. * If then

Let us denote by the tree from the LHS of the first row, by the tree from the middle of the first row and by the tree from the LHS of the second row.

* Corollary 1.* If then , and .

Proof: If then . By Proposition 1 the trees and can be transformed into , therefore they belong to . Also, by the same proposition the tree can be transformed into , which we proved that it belongs to . Therefore .

____________________

I define now when two graphs are close.

* Definition 3.* Two graphs are close, denoted by , if there is such that can be moved into .

* Proposition 3.* The closeness relation is an equivalence.

Proof: By the move R1a we have for any . Take now , therefore there is such that can be moved into . We know that by Corollary 1. On the other hand we can prove that can be moved into , therefore .

Finally, let , so there’s a such that can be moved into , and let , so there’s such that can be moved into . Let now given by . Check that can be moved into , therefore .

* Question:* do you think this proof is more easy to understand than an equivalent proof given by drawings?