Towards geometric Plünnecke graphs

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 $T(X)$ with nodes decorated with two colours (black and white) and leaves decorated with elements of the infinite set of “variable names” $X$.  I shall denote by $A, B, C$ … such trees and by $x, y, z, u, v, w$ … elements of $X$.

The edges of the trees are oriented upward. By convention we admit $X$ to be a subset of $T(X)$, thinking about $x \in X$ as an edge pointing upwards which is also a leaf decorated with $x$.

The moves act locally, i.e. they can be used for any portion of a tree from $T(X)$ 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 $FinT(X) \subset T(X)$ is the smallest subset of $T(X)$ with the  properties:

• $X \subset FinT(X)$,
• if $A, B \in FinT(X)$ then $A \circ B \in FinT(X)$  , where $A \circ B$ is the tree • if $A, B, C \in FinT(X)$ then $Sum(A,B,C) \in FinT(X)$, where $Sum(A,B,C)$ is the tree • if $A \in FinT(X)$ and we can pass from $A$ to $B$ by one of the moves then $B \in FinT(X)$.

____________________

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

Proposition 1.  If $A, B, C \in T(X)$  then Let us denote by $Dif(A,B,C)$ the tree from the LHS of the first row, by $Q(A,B,C)$ the tree from the middle of the first row and by $Inv(A,B)$ the tree from the LHS of the second row.

Corollary 1.   If $A, B, C \in FinT(X)$ then $Dif(A,B,C) \in FinT(X)$, $Q(A,B,C) \in FinT(X)$ and $Inv(A,B) \in FinT(X)$.

Proof: If $A, B, C \in FinT(X)$ then $Sum(A,B,C) \in FinT(X)$. By Proposition 1  the trees $Dif(A,B,C)$ and $Q(A,B,C)$ can be transformed into $Sum(A,B,C)$, therefore they belong to $FinT(X)$. Also, by the same proposition the tree $Inv(A,B)$ can be transformed into $Dif(A,B,A)$, which we proved that it belongs to $FinT(X)$. Therefore $Inv(A,B) \in FinT(X)$.

____________________

I define now when two graphs are close.

Definition 3. Two graphs $A, B \in FinT(X)$  are close, denoted by $A \sim B$, if there is $C \in FinT(X)$ such that $B$ can be moved into $A \circ C$.

Proposition 3.  The closeness relation is an equivalence.

Proof:  By the move R1a we have $A \sim A$ for any $A \in FinT(X)$.  Take now $A \sim B$, therefore there is $C \in FinT(X)$ such that $B$ can be moved into $A \circ C$. We know that $D = Inv(A,C) \in FinT(X)$ by Corollary 1. On the other hand we can prove that $A$ can be moved into $B \circ D$, therefore $B \sim A$.

Finally, let $A \sim B$  , so there’s a $C \in FinT(X)$ such that $B$ can be moved into $A \circ C$  , and let $B \sim D$, so there’s $E \in FinT(X)$ such that $D$ can be moved into $B \circ E$ . Let now $F \in FinT(X)$ given by $F = Sum(A,C,E)$. Check that $D$ can be moved into $A \circ F$ , therefore $A \sim D$.

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