Tag Archives: Plunnecke inequality

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?