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“:

roadmap_4

To these move I add the “linearity moves”

roadmap_6

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

roadmap_7

  • if A, B, C \in FinT(X) then Sum(A,B,C) \in FinT(X), where Sum(A,B,C) is the tree

roadmap_8

  • 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

roadmap_9

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?

Advertisements

3 thoughts on “Towards geometric Plünnecke graphs”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s