9512.net

# GEOMETRIC PROPERTIES OF INFINITE GRAPHS AND THE

GEOMETRIC PROPERTIES OF INFINITE GRAPHS AND THE HARDY-LITTLEWOOD MAXIMAL OPERATOR
JAVIER SORIA AND PEDRO TRADACETE Abstract. We study di?erent geometric properties on in?nite graphs, related to the weak-type boundedness of the Hardy-Littlewood maximal averaging operator. In particular, we analyze the connections between the doubling condition, having ?nite dilation and overlapping indices, uniformly bounded degree, the equidistant comparison property and the weak-type boundedness of the centered Hardy-Littlewood maximal operator. Several non-trivial examples of in?nite graphs are given to illustrate the di?erences among these properties.

arXiv:1602.01029v1 [math.CA] 2 Feb 2016

1. Introduction Let G = (VG , EG ) be a simple and connected graph, with vertices having ?nite degrees 1 ≤ dx < ∞ (conditions that we will always assume from now on), where VG is the set of vertices and EG is the set of edges between them. Unless otherwise stated, we will only consider the case of in?nite graphs. For a function f : VG → R, the (centered) Hardy-Littlewood maximal operator is de?ned as 1 | f (y )| . MG f (x) = sup r ≥0 |B (x, r )|
y ∈B (x,r )

Here, B (x, r ) denotes the ball of center x and radius r on the graph, equipped with the metric dG induced by the edges in EG . That is, given x, y ∈ VG the distance dG (x, y ) is the number of edges in a shortest path connecting x and y , and B (x, r ) = {y ∈ VE : dG (x, y ) ≤ r }. Similarly, we de?ne the sphere S (x, r ) = {y ∈ VE : dG (x, y ) = r }. Observe that B (x, r ) = B (x, [r ]), where [r ] denotes the integer part of r , B (x, r ) = {x}, if 0 ≤ r < 1 and B (x, r ) = {x} ∪ NG (x), if 1 ≤ r < 2, where NG (x) = S (x, 1) is the set of neighbors of x; i.e., all vertices adjacent to x. Also, given a ?nite set A ? VG we denote its cardinality by |A|. Thus, dx = |NG (x)|. It is clear that, since the vertices’ degrees are ?nite, all balls are ?nite sets. We refer to [3, 4] for standard notations and terminology on graphs. Since the distance dG introduced above only takes natural numbers as values, the radius r ≥ 0 considered in the de?nition of the Hardy-Littlewood maximal operator
2010 Mathematics Subject Classi?cation. 05C12, 05C63, 42B25. Key words and phrases. In?nite graph; maximal operator; weak-type estimate; doubling property. The ?rst author has been partially supported by the Spanish Government grants MTM2013-40985, and the Catalan Autonomous Government grant 2014SGR289. The second author has been partially supported by the Spanish Government grants MTM2013-40985 and MTM2012-31286, and also Grupo UCM 910346.

2

can be taken to be a natural number r ∈ N = {0, 1, 2, . . . }: 1 | f (y )| . MG f (x) = sup r ∈N |B (x, r )|
y ∈B (x,r )

The relevance of the Hardy-Littlewood maximal operator is well-known. It is a key tool in the study of averages of functions, and in particular in their limiting behavior, since it yields applications to di?erentiation theorems, among others. We refer the reader to the book by E. Stein [18] as a reference for maximal operators and their use in analysis. Motivated by the results of A. Naor and T. Tao [13], for the case of the in?nite k -regular tree, as well as our previous work [17], for ?nite graphs, our aim in this paper is to study weak-type (1, 1) boundedness for MG in terms of the geometry of the graph; that is, estimates of the form CG (1) | {x ∈ VG : MG f (x) > λ} | ≤ f L1 (G) , λ for all f ∈ L1 (G) and λ > 0, where CG is a constant depending only on G. This inequality is usually written as MG : L1 (G) → L1,∞ (G), where f
1,∞

= sup λ| {x ∈ VG : |f (x)| > λ} |,
λ>0

and it is denoted as the weak-type (1,1) boundedness of MG . The Hardy-Littlewood maximal operator in metric measure spaces has been mainly considered in a doubling setting (cf. [9]). In non-doubling spaces a natural modi?cation of the maximal operator has also been studied (see [14, 16, 20]). There has also been several attempts to analyze discrete versions of the Hardy-Littlewood maximal operator [1, 6, 11, 19]. For our purpose, we will consider in Section 2 dilation and overlapping indices, Dk (G) and O(G), and the ECP property, related to estimate (1), and show some preliminary results, in particular the boundedness on the Dirac deltas (Proposition 2.10). In Section 3, we will study the di?erent relationships among all these tools, and we will compute the explicit values of these indices for some relevant examples of in?nite graphs, allowing us to show concrete counterexamples to the necessity or su?ciency of these properties (we summarize all this in Table 1). Finally, in Section 4, we follow the ideas used in [13] to analyze the case of the closely related spherical maximal function (Theorem 4.1). 2. Geometrical properties In order to study the analogous results of the classical weak-type (1, 1) bounds for the Hardy-Littlewood operator on Rn , we introduced in [17] two numbers associated to a graph G: the dilation and the overlapping indices. The dilation index of a graph is related to the so called doubling condition, and measures the growth of the number of vertices in a ball when its radius is enlarged in a ?xed proportion. De?nition 2.1. Given a graph G, for every k ∈ N, k ≥ 2, we de?ne the k -dilation index as |B (x, kr )| : x ∈ VG , r ∈ N . Dk (G) = sup |B (x, r )|

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

3

Remark 2.2. Given k ≥ 2, one can easily compute the k -dilation index of some relevant ?nite graphs: For n ∈ N, n ≥ 2, let Kn be the complete graph, and Sn the star graph with n vertices (i.e., Sn is a graph with one vertex of degree n ? 1, and n ? 1 leaves, or vertices of degree 1). Then we have n D k ( Kn ) = 1 and D k ( Sn ) = . 2 Also, for Ln , the linear tree with n vertices, we have that Dk (Ln ) < k , for all n ∈ N, and limn→∞ Dk (Ln ) = k . For the case of in?nite graphs, see Section 3. It is easy to see that if k, k ′ ∈ N, with 2 ≤ k < k ′ , then D k ( G) ≤ D k ′ ( G) ≤ D k ( G)
log k′ log k

+1

.

In particular, if for a certain graph G, there is k0 ≥ 2 such that Dk0 (G) < ∞, then for every k ≥ 2, Dk (G) < ∞. The dilation index is very much related to the following property: A metric measure space (X, dX , ?) satis?es the doubling condition (cf. [9]) if there is K > 0 such that, for every r > 0 and every x ∈ X , we have that (2) ?(B (x, 2r )) ≤ K?(B (x, r )). However, the fact that we only need to consider r ∈ N makes the k -dilation index more suitable, and less restrictive, as the following result shows. Before, let us recall that the maximum degree of a graph G is de?ned as ?G = sup{dx : x ∈ VG }. Proposition 2.3. Let G be a graph and denote K (G) = sup Then, max D2 (G), 1 + ?G ≤ K (G) ≤ D2 (G)(1 + ?G ). In particular, a graph G satis?es the doubling condition (2) if and only if both ?G and D2 (G) are ?nite. Proof. It is clear that K (G) ≥ D2 (G). Also, for any x ∈ VG we have that K ( G) ≥ Hence, K (G) ≥ 1 + ?G . Conversely, for 0 < r < 1 we have |B (x, 2r )| ≤ |B (x, 1)| ≤ 1 + ?G ≤ D2 (G)(1 + ?G ). While for r ≥ 1 we have B (x, [r ] + 1) =
y ∈B (x,[r ])

|B (x, 2r )| : x ∈ VG , r > 0 . |B (x, r )|

|B (x, 1)| = 1 + dx . |B (x, 1/2)|

S (y, 1).

Hence, |B (x, 2r )| ≤ |B (x, 2([r ] + 1)| ≤ D2 (G)|B (x, [r ] + 1)| ≤ D2 (G)|B (x, r )|?G . In conclusion, in any case we get that K (G) ≤ D2 (G)(1 + ?G ).

4

We will see in Proposition 3.1 an example of a graph G for which ?G = ∞ but Dk (G) is ?nite, and Proposition 3.3 provides another graph where ?G is ?nite and Dk (G) = ∞ (hence, in both cases K (G) = ∞). This shows that the conditions on Proposition 2.3 are actually independent. We now recall the overlapping index of a graph G, which represents the smallest number of balls that necessarily overlap in any covering of G. De?nition 2.4. Given a graph G, we de?ne its overlapping index as O(G) = min m ∈ N : ?{Bj }j ∈J , Bj a ball in G, ? I ? J, Bj =
j ∈J i∈I

Bi and
i∈I

χBi ≤ m .

The overlapping index of the following families of ?nite graphs can be easily computed: O(Kn ) = 1, n ≥ 1; O(Ln ) = 1, 2, 1 ≤ n ≤ 2, n ≥ 3; O(Sn ) = n ? 1, n ≥ 2; O (C n ) = 1, 2, n = 3, n ≥ 4,

where Cn is the cycle with n vertices. Examples for in?nite graphs will be given in Section 3. Remark 2.5. The de?nition of the overlapping index suggests some connection with dimension theory. Recall that for a metric space (X, d), its asymptotic dimension asdim(X ) is the smallest n ∈ N such that, for every r > 0, there is D (r ) > 0 and a covering of X with sets of diameter smaller than D (r ), such that every ball in X of radius r intersects at most n + 1 members of the covering (cf. [8, page 29]). Note that if a graph G has ?nite overlapping index, then for every r > 0 we can always ?nd a collection of balls of radius r , (Bi )i∈I such that χBi ≤ O(G).
i∈I

Hence, we always have asdim(G) ≤ O(G) ? 1. Analogous estimates hold for other notions of dimension considered in the metric setting (such as Assouad-Nagata dimension, cf. [12].) Note however, that for the k -regular tree Tk we have asdim(Tk ) = 1, while O(Tk ) = ∞, for k ≥ 3 (see Proposition 3.3). The dilation and overlapping indices were used in [17] to obtain an upper bound for the weak-type (1, 1) norm of the maximal operator of a ?nite graph. The proof also works for in?nite graphs, yielding the estimate (3) MG
1,∞

≤ min D3 (G), O(G) .

We will introduce next a new property concerning the size of balls on equidistant points, and we will also study its relation with the boundedness of MG .

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

5

De?nition 2.6. A graph G has the equidistant comparability property (ECP, in short) if there is a constant C ≥ 1 such that, for every x, y ∈ VG 1 |B (x, d(x, y ))| ≤ |B (y, d(x, y ))| ≤ C |B (x, d(x, y ))|. C In this case, we de?ne the ECP constant of G as C (G) = sup |B (x, d(x, y ))| : x, y ∈ VG . |B (y, d(x, y ))|

Remark 2.7. Every vertex-transitive graph G (i.e., for every x, y ∈ VG there is an automorphism of G mapping x to y ) has the ECP. In particular, every Cayley graph has the ECP. Also if every pair of balls in the graph with equal radius are comparable, then G has the ECP. For instance, the in?nite k -regular tree Tk satis?es that |B (x, r )| = |B (y, r )|, for every x, y ∈ V and r ≥ 0, and hence the ECP holds with C (Tk ) = 1 (for more information, see Proposition 3.3). Observe also that, since for any pair of vertices x, y in a graph G, we have that B (x, d(x, y )) ? B (y, 2d(x, y )), then the dilation condition implies the ECP. In fact, C ( G) ≤ D 2 ( G) . Other important estimates relating these indices are given in the following result. Proposition 2.8. Suppose G is a graph with the ECP and O(G) < ∞. Then, D 2 ( G) ≤ 1 + O ( G) C ( G) . Proof. Fix x ∈ VG and r ∈ N. Since O(G) < ∞, if we consider the collection of balls {B (y, r ) : y ∈ S (x, r )}, we can ?nd a subset F ? S (x, r ) such that B (y, r ) =
y ∈S (x,r ) y ∈F

B (y, r ),

with the additional property that χB(y,r) ≤ O(G)
y ∈F

(observe that since G is an in?nite graph, then S (x, r ) = ?). Note that x ∈ B (y, r ), for every y ∈ F ? S (x, r ), and we have that |F | =
y ∈F

χB(y,r) (x) ≤ O(G).

Now, since G has the ECP, for every y ∈ S (x, r ) we have |B (y, r )| ≤ C (G)|B (x, r )|. Hence, since B (x, 2r ) = B (y, r ) ∪ B (x, r ),
y ∈S (x,r )

we get |B (x, 2r )| ≤
y ∈F

B (y, r ) + |B (x, r )| ≤
y ∈F

|B (y, r )| + |B (x, r )|

≤ 1 + O(G)C (G) |B (x, r )|, which proves the result.

6

Remark 2.9. Arguing in a similar manner one can show that if a graph G has the ECP and ?G < ∞, then G satis?es the so-called local doubling condition ; i.e., for every r ∈ N, there exists Dr < ∞ such that for every x ∈ VG , |B (x, 2r )| ≤ Dr |B (x, r )| (cf. [5]). Indeed, since B (x, 2r ) =
y ∈S (x,r )

B (y, r ) ∪ B (x, r ),

we have |B (x, 2r )| ≤
y ∈S (x,r )

|B (y, r )| + |B (x, r )| ≤ |S (x, r )|C (G)|B (x, r )| + |B (x, r )|

≤ 1 + ?r G C (G) |B (x, r )|. The following result shows that ECP implies the weak-type (1,1) boundedness of MG on the Dirac deltas (this should be compared to [17, Lemma 2.5]): Proposition 2.10. If G has ECP, then
x∈VG

sup MG δx

1,∞

≤ C ( G) .

Proof. For any x ∈ VG and 0 < λ < 1, if we set rx = max d(x, y ) : |B (x, d(x, y ))| < then we have that B (x, rx ) = y ∈ VG : |B (x, d(x, y ))| < |{y ∈ VG : |MG δx (y )| > λ}| = C ( G) , λ
C (G) λ

and

1 λ C ( G) ≤ y ∈ VG : |B (x, d(x, y ))| < λ C ( G) = |B (x, rx )| < . λ y ∈ VG : |B (y, d(x, y ))| <

Therefore, MG δx
1,∞

= sup λ |{y ∈ VG : |MG δx (y )| > λ}| ≤ C (G).
λ>0

3. Examples of graphs The purpose of this section is to study the relations between the geometric conditions introduced in Section 2 and the weak-type estimates for MG , illustrating, by means of several examples, the di?erences between boundedness of MG 1,∞ , ECP, dilation and overlapping conditions, and the maximum degree. 3.1. The direct sum of complete graphs: ⊕Kn . Let V⊕Kn = {(m, n) ∈ N2 : m ≥ 2, 1 ≤ n ≤ m ? 1}. We set two vertices (m1 , n1 ), (m2 , n2 ) in V⊕Kn to be adjacent as follows ? ? m1 = m2 + 1, n1 = 1; or, m2 = m1 + 1, n2 = 1; or, (m1 , n1 ) ?⊕Kn (m2 , n2 ) ? ? m1 = m2 .

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

7

Proposition 3.1. The following properties hold for the graph ⊕Kn : (i) (ii) (iii) (iv) (v) ?⊕Kn = ∞. O(⊕Kn ) = 2. D2 (⊕Kn ) ≤ 48. C (⊕Kn ) ≤ 48. M⊕Kn : L1 → L1,∞ is bounded, with norm not exceeding 2.

Proof. It is clear that for m ≥ 2, d(m,1) = (m ? 1) + (m ? 2) = 2m ? 3, and hence ?⊕Kn = ∞. To describe the balls of this graph, we are going to think of ⊕Kn as the union of all complete graphs with a common cut vertex vj between Kj and Kj +1, j = 1, 2, . . . (we will write vj = (j + 1, 1) ∈ Kj ∩ Kj +1 ). All the other vertices v in Kj will be referred ?j ). Now, it is easy to see that, if r = 1, 2, . . . , and we de?ne as interior vertices (v ∈ K [m]1 = max{m, 1}, then ? j +r ? ? ? Kl , if v ∈ Kj ∩ Kj +1 , ? ? ? ?l=[j ?r]1 (4) B (v, r ) = ? j +r ?1 ? ? ? ?j . ? Kl , if v ∈ K ? ?
l=[j ?r +1]1

Thus, if we consider any 3 balls B1 , B2 , and B3 with common intersection, and Bp is the one with the largest index lmax and Bq is the one with the smallest lmin , for the complete graphs Kl appearing in (4), then B1 ∪ B2 ∪ B3 = Bp ∪ Bq .

Therefore, by a simple inductive argument, we deduce that O(⊕Kn ) = 2, which is (ii). Using (4) again, it is a straightforward calculation to show that, if v ∈ Bj , then we have ? jr ? ? , 6jr , if j ≥ r ≥ 1, ? 2 |B (v, r )| ∈ 2 ? ? r , 6r 2 , if 1 ≤ j < r. ? 2 Thus, |B (v, 2r )| ≤ 48, |B (v, r )| which proves (iii). Remark 2.7 and (iii) prove also (iv). Finally, the boundedness in (v) follows from (3) and (ii). This ?nishes the proof.

r r r r

r r r r

r r r

r

r r ? ? ?

r

r

Figure 1. The graph ⊕Kn .

8

3.2. The upwards shift direct sum of complete graphs: L∞ ⊕ Kn . Let us consider the following variation of ⊕Kn : VL∞ ⊕Kn = {(m, n) ∈ N2 : m ≥ 2, 0 ≤ n ≤ m}, with adjacent vertices as follows (m1 , n1 ) ?L∞ ⊕Kn ? |m1 ? m2 | = 1, n1 = n2 = 0; or, ? ? ? m1 = m2 , n1 = 0, n2 = 1; or, (m2 , n2 ) ? m1 = m2 , n2 = 0, n1 = 1; or, ? ? ? m = m , n , n ≥ 1. 1 2 1 2
s s s s s s s s s s s s s s s s s s s s s s s ? ? ? ? s s

Figure 2. The graph L∞ ⊕ Kn . Proposition 3.2. The following properties hold for the graph L∞ ⊕ Kn : (i) ?L∞ ⊕Kn = ∞. (ii) O(L∞ ⊕ Kn ) = 5. (iii) D2 (L∞ ⊕ Kn ) = ∞. (iv) C (L∞ ⊕ Kn ) = ∞. (v) ML∞ ⊕Kn : L1 → L1,∞ is bounded, with norm not exceeding 5. Proof. Since d(m,1) = m we clearly have ?L∞ ⊕Kn = ∞. That O(L∞ ⊕ Kn ) ≥ 5 follows from the fact that for m ≥ 4, (m, 0) belongs to the intersection of the balls B (m ? 2, 0), 2 ∩ B (m ? 1, 1), 2 ∩ B (m, 1), 1 ∩ B (m + 1, 1), 2 ∩ B (m + 2, 0), 2 , while the union of these ?ve balls cannot be covered by only four of them. For the converse, let us consider the following: Claim: Suppose (Bi )6 i=1 is a collection of balls in L∞ ⊕ Kn , with for some i0 ∈ {1, . . . , 6}, we have Bi =
i∈{1,...,6} i∈{1,...,6}\{i0 } 6 i=1

Bi = ?. Then,

Bi .

Once this is proved, an inductive application of this argument shows that, in fact, O(L∞ ⊕ Kn ) ≤ 5, proving (ii). In order to prove the claim, for 1 ≤ i ≤ 6, let (mi , ni ) and ri denote respectively the center and radius of Bi . If ri ≤ 1, for some i = 1, . . . , 6, it is easy to see, by simple inspection, that for some i0 ∈ {1, . . . , 6} we have Bi =
i∈{1,...,6} i∈{1,...,6}\{i0 }

Bi .

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

9

Hence, without loss of generality, we can assume that ri ≥ 2, for each i = 1, . . . , 6. Observe that if for some 1 ≤ i, j ≤ 6, it holds that mi = mj , then necessarily Bi ? Bj or Bj ? Bi . Hence, we can suppose that m0 < m1 < m2 < m3 where (m0 , n0 ) ∈ 6 i=1 Bi . For each i = 1, 2, 3, let us denote li = min{m ≥ 2 : (m, 0) ∈ Bi } and ui = max{m ≥ 2 : (m, 0) ∈ Bi }. Now, if l2 < l1 , then B1 ? B2 . Similarly, if u2 > u3 , then B3 ? B1 . Otherwise, we have l1 ≤ l2 and u2 ≤ u3 , and in this case we get B2 ? B1 ∪ B3 . Therefore, the claim is proved. In order to see (iii), note that, for m ≥ 3, we have that |B (m, 0), 1 | = 4, while |B (m, 0), 2 | = m + 7. Hence, D2 (L∞ ⊕ Kn ) = ∞. As for (iv), for m ≥ 3, we ?nd that d (m, 0), (m, 1) = 1 and |B (m, 0), 1 | = 4, while |B (m, 1), 1 | = m + 1. Hence, C (L∞ ⊕ Kn ) = ∞. Finally, the boundedness in (v) follows from (3) and (ii). This ?nishes the proof. 3.3. The k -regular tree: Tk . We consider now the in?nite regular tree of degree k (for k ≥ 2). The main non-trivial result regarding this graph is the weak-type (1,1) boundedness of MTk , with a norm estimate independent of k , [13, Theorem 1.5] (see also [7, 15]). In the following proposition we complete the information about the remaining properties.
s s s s s s s s s s s s s s s s

Figure 3. The graph Tk , with k = 3.

Proposition 3.3. The following properties hold for the graph Tk : (i) ?Tk = k . (ii) O(Tk ) = ∞, for k ≥ 3. (iii) D2 (Tk ) = ∞. (iv) C (Tk ) = 1. (v) [13, Theorem 1.5] MTk : L1 → L1,∞ is bounded, with norm uniformly on k . Proof. Condition (i) is trivial and (v) is [13, Theorem 1.5]. A simple calculation shows that |B (x, r )| = (k r+1 ? 1)/(k ? 1), which proves (iv). Similarly, k 2r+1 ? 1 |B (x, 2r )| = r+1 ?→ ∞, |B (x, r )| k ?1 as r → ∞.

Hence, D2 (Tk ) = ∞. To ?nish, ?x a vertex x ∈ Tk and consider the set of points y ∈ S (x, r ), the sphere of radius r = 1, 2, . . . Then, x belongs to all balls in the family Br = B (y, r ) {y∈S (x,r)} , and for each y ∈ S (x, r ) there exists a point xy ∈ B (y, r ) which is in no other ball of

10

Br (it su?ces to consider xy such that d(xy , x) = 2r and y belongs to the unique path joining x and xy ). Since for k ≥ 3, |Br | → ∞, as r → ∞, then O(Tk ) = ∞.

3.4. The in?nite comb: X∞ . Let VX∞ = {(j, k ) : j ∈ Z, k ∈ N}. Given two vertices (j1 , k1 ), (j2 , k2 ) in VX∞ we de?ne them to be adjacent according to the following (j1 , k1 ) ?X∞ (j2 , k2 ) ? |j1 ? j2 | = 1, and k1 = k2 = 0; or, j1 = j2 , and |k1 ? k2 | = 1.

? ? ? ? r r ? ? ? ? r

? ? ? ? r r r

? ? ? ? r r r

? ? ? ? r r r

? ? ? ? r r r

? ? ? ? r r r

? ? ? ? r r r

? ? ? ? r r r

? ? ? ? r r r

? ? ? ? r r r ? ? ? ?

Figure 4. The in?nite comb graph X∞ .

Proposition 3.4. The following properties hold for the graph X∞ : (i) (ii) (iii) (iv) (v) ?X∞ = 3. O (X∞ ) = ∞ . D 2 (X∞ ) = ∞ . C (X∞ ) = ∞ . L1,∞ is not bounded (even on Dirac deltas). MX∞ : L1

Proof. It is clear that the degree of a vertex (j, k ) is d(j,k) = 3, if k = 0, 2, otherwise.

This proves (i). It is easy to check that for (j, k ) ∈ VX∞ and r ∈ N we have |B ((j, k ), r )| = 2r + 1, (r ? k + 1)2 + 2k, if r < k, if r ≥ k.

Let o = (0, 0). For any (j, k ) ∈ VX∞ we have that d(o, (j, k )) = |j | + k . In particular, |B ((j, k ), |j | + k )| = (|j | + 1)2 + 2k.

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

11

Now, given λ ∈ (0, 1) we have |{(j, k ) : |MX∞ δo (j, k )| > λ}| = =
j,k
1 ?2 2λ

(j, k ) : (|j | + 1)2 + 2k < χ{(|j |+1)2 +2k< 1 } (j, k ) =
λ

1 λ 1
k ∈N 1 2k< λ ?1 j ∈Z 1 (|j |+1)2 < λ ?2k

k =0
1 ?2 2λ

j ∈ Z : (|j | + 1)2 < 1 ? 2k ? 2 λ

1 ? 2k λ

k =0

2
1 ?1 2λ

≥2
0

1 ? 2s ? 2 ds λ

≥ Therefore, we get that MX∞ δo
1,∞

3 2λ
3 2

?

2 + 2. λ
1,∞ δo (j, k )|

= sup λ|{(j, k ) : |MX∞ δo
λ>0

> λ}|

≥ sup
λ∈(0,1)

3 2λ 2
1

? 2 + 2λ

= ∞.

This proves (v). Using (v) and (3), we get (ii) and (iii). Also by Proposition 2.10, we get (iv). 3.5. The steplike dyadic tree: Υ∞ 2 . Let us consider the set of vertices V Υ∞ = 2
n∈N

{(2n , k ) : 0 ≤ k ≤ 2n } ∪ {(j, 0) : j ∈ N, j = 2n , n ∈ N}.

Given two vertices (j1 , k1 ), (j2 , k2) in VΥ∞ we de?ne them to be adjacent according to 2 the following (j1 , k1) ?Υ∞ (j2 , k2 ) ? 2 |j1 ? j2 | = 1, and k1 = k2 = 0; or, j1 = j2 , and |k1 ? k2 | = 1.

Proposition 3.5. The following properties hold for the graph Υ∞ 2 : (i) ?Υ∞ = 3. 2 ∞ (ii) O(Υ2 ) = ∞. (iii) D2 (Υ∞ 2 ) < ∞. (iv) C (Υ∞ 2 ) < ∞. (v) MΥ∞ : L1 → L1,∞ is bounded. 2 Proof. It is clear that ?Υ∞ = 3. 2 In order to see (ii), let us consider for n ≥ 1 the ball Bn with center (2n , 1) and radius 2n . It is clear that (1, 0) ∈ n≥1 Bn . Moreover, for each m ≥ 1 we have (2m , 2m ) ∈ Bm \
n =m

Bn .

12

r r r r r r r r r r

r r r r r r r r r r r r

r r r r r r r r r r r r r r r r r r r r r r r r?

···

Figure 5. The graph Υ∞ 2 . This shows that O(Υ∞ 2 ) = ∞. The rest of the proof will follow from the following: Claim: For every x ∈ VΥ∞ and r ∈ N 2 r ≤ |B (x, r )| ≤ 24r.
∞ Once this is proved, it is clear that D2 (Υ∞ 2 ) ≤ 48, C (Υ2 ) ≤ 24 and by (3) we get MΥ∞ 1,∞ ≤ 72. 2

The proof of the claim will be split into several steps: (a) Suppose ?rst x = (2n , 0) for some n ∈ N. (a.1) Let us consider rj = 2n ? 2j , for some 0 ≤ j < n. In this case, the ball B (x, rj ) contains 2rj +1 points of the form (m, 0) and can only have points of the form (2i , k ), with k = 0, whenever j + 1 ≤ i ≤ n. Thus, we have that
n

(5)

|B ((2 , 0), rj )| ≤ 2rj +
i=j +1

n

2i = 2rj + (2n+1 ? 2j +1) = 4rj .

(a.2) Consider now rj = 2j ? 2n , for some j ≥ n + 1. In this case, the ball B (x, rj ) consists of all the points of the form (m, 0) for 1 ≤ m ≤ 2j and those of the form (2i , k ), with 0 < k ≤ 2i for i < j . Hence,
j ?1

|B ((2 , 0), rj )| ≤ 2 +
i=0

n

j

2i ≤ 2j +1.

Note that for j ≥ n + 1, we have 2j ?1 ≤ 2j ? 2n , so we get that (6) |B ((2n , 0), rj )| ≤ 4rj . (a.3) Let us consider now arbitrary r ≥ 1. For 1 ≤ r < 2n?1 , we have |B ((2n , 0), r )| = 3r + 1.

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

13

For 2n?1 ≤ r < 2n , there is some 0 ≤ j < n ? 1 such that 2n ? 2j +1 < r ≤ 2n ? 2j . Since for j < n ? 1 we have 2j < 2n ? 2j +1 , and using (5), we get |B ((2n , 0), r )| ≤ |B ((2n , 0), 2n ? 2j )| ≤ 4(2n ? 2j ) = 4(2n ? 2j +1) + 2j +2 ≤ 8(2n ? 2j +1) ≤ 8r. Finally, for r ≥ 2n , there is j ≥ n + 1 such that 2j ? 2n ≤ r < 2j +1 ? 2n . In particular, for such j we have 2j ≤ 2(2j ? 2n ). Hence, using (6), we have |B ((2n , 0), r )| ≤ |B ((2n , 0), 2j +1 ? 2n )| ≤ 4(2j +1 ? 2n ) = 4(2j + 2j ? 2n ) ≤ 12(2j ? 2n ) ≤ 12r. Therefore, for any r ≥ 1 we have |B ((2n , 0), r )| ≤ 12r. (b) Let x = (2n , k ). For r ≤ k we clearly have |B ((2n , k ), r )| = 2r +1. While for r > k , all the vertices in B ((2n , k ), r ), except at most r vertices of the form (2n , m), belong to the ball B ((2n , 0), r ). Thus, |B ((2n , k ), r )| ≤ |B ((2n , 0), r )| + r ≤ 13r. (c) Let x = (j, 0) with j = 2n for any n ∈ N. In particular, there is m ∈ N such that 2m < j < 2m+1 , and we clearly have B ((j, 0), r ) ? B ((2m , 0), r ) ∪ B ((2m+1 , 0), r ). Hence, |B ((j, 0), r )| ≤ |B ((2m , 0), r )| + |B ((2m+1 , 0), r )| ≤ 24r.

We summarize in Table 1 the di?erent results we have previously obtained. To read this list, we indicate at a given entry whether the statement on the left column implies the corresponding one on the ?rst row. ECP ?G < ∞ Weak-type Yes No Yes D k ( G) < ∞ ? Rem. 2.7 Prop. 3.1 (3) No No No Yes O ( G) < ∞ ? Prop. 3.2 Prop. 3.2 Prop. 3.1 (3) No No No True on deltas ECP ? Prop. 3.3 Prop. 3.3 Prop. 3.1 Prop. 2.10 No No No No ?G < ∞ ? Prop. 3.3 Prop. 3.3 Prop. 3.4 Prop. 3.4 No No No No Weak-type ? [13] & Prop. 3.3 [13] & Prop. 3.3 Prop. 3.2 Prop. 3.1 Table 1. All di?erent combinations between the main parameters and properties. =? D k ( G) < ∞ O ( G) < ∞ No Prop. 3.5

14

4. Expander type bounds for the spherical maximal function In this section we will consider the spherical maximal function
? MG f (x) = sup r ∈N

1 |S (x, r )|

| f (y )| ,
y ∈S (x,r )

where S (x, r ) denotes the sphere S (x, r ) = {y ∈ G : d(x, y ) = r }. Note that if the graph G is in?nite, then S (x, r ) is never empty. The spherical maximal function has been considered in a di?erent discrete setting (Zd , with euclidean metric) in [11]. See also [10] for the corresponding endpoint estimates. Since every ball can be written as the disjoint union of spheres, we have the pointwise estimate ? MG f (x) ≤ MG f (x).
? Therefore, a weak-type (1, 1)-estimates for MG implies a similar estimate for MG . We will need to control the size of the spheres of a graph, so for r ∈ N let

SG (r ) = sup |S (x, r )|.
x∈VG

In all what follows we impose that the graph satis?es SG (r ) < ∞ for every r ∈ N. Notice that we can compute the degree of a vertex as dx = |S (x, 1)|, therefore ?G = maxx∈VG dx = SG (1). In particular, the following requires ?G < ∞. Motivated by the ideas in [13], for a graph G, we introduce the function E G (r ) = sup
A,B ?VG , | A | , | B | <∞

1 |A||B |

|A ∩ S (x, r )| |S (x, r )| x∈B

2

.

This function is related to the expander properties of G. Indeed, given ?nite subsets A, B ? VG , let us consider E (A, B ) = |{(x, y ) ∈ A × B : d(x, y ) = 1}| . This quantity can be thought of as a measure for the size of common boundary between A and B . If G were a k -regular expander (see [2, Section 9.2] for details), then the number E (A, B ) would behave approximately as what one would expect in a random graph. Moreover, for k -regular G we always have EG (1) = 1 k2 sup
A,B ?VG , | A | , | B | <∞

E (A, B )2 . |A||B |

In particular, for the k -regular in?nite tree Tk it is shown in [13, Lemma 5.1] that ETk (r ) ? 1/k r . Note also that EG (r ) provides a lower estimate for the size of the spheres on the graph. Indeed, for every x ∈ VG , if we consider A = {x} and B = S (x, r ), we get |S (x, r )| ≥ EG (r )?1 .

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

15

Theorem 4.1. Let G be an in?nite graph such that SG (r ) < ∞ for every r ∈ N.
? MG L1 (G)→L1,∞ (G)

sup 2 2
n∈N∪{0}

n

E G ( r ) SG ( r ) 2 .
r ∈N∪{0} SG (r )≥2n?1

1

For each r ≥ 0, let A? r denote the spherical averaging operator A? r f (x) = 1 |S (x, r )| | f (y )| .
y ∈S (x,r )

? Thus MG f (x) = supr≥0 A? r f (x). Following [13], let us start with a distributional estimate on A? . r

Lemma 4.2. Let f ∈ L1 (G), r > 0 and λ > 0. Then | {A? r f ≥ λ} |
n∈N∪{0} 1≤2n ≤2SG (r )

2 2 E G ( r ) SG ( r ) 2 | | f | ≥ 2 n ? 1 λ | .

3n

1

Proof. We may take f to be non-negative, and by dividing f by λ we may take λ = 1. For n ∈ N, let us consider the set En = x ∈ VG : 2n?1 ≤ f (x) < 2n . Let n(r ) ∈ N be such that 2n(r) ≤ SG (r ) < 2n(r)+1 . Since we have 1 f≤ + 2n 1En + f 1{f ≥2n(r) } , 2 n=0 we can also bound, A? rf Note that x ∈ VG : A? r f 1{f ≥2n(r ) } (x) = 0 ?
f (y )≥2n(r ) n(r ) n(r )

1 ? 2n A? ≤ + r (1En ) + Ar f 1{f ≥2n(r ) } . 2 n=0 S (y, r ),

so in particular we have x ∈ VG : A? r f 1{f ≥2n(r ) } (x) = 0 ≤ SG ( r ) x ∈ VG : f (x) ≥ 2n(r) ? 1? . .

Thus, putting these together we have ? ? ? |{x ∈ VG : Ar f (x) ≥ 1}| ≤ x ∈ VG : ? + SG ( r ) Note that if x ∈ VG satis?es
n(r )

n(r )

2n A? r (1En ) (x) ≥
n=0

x ∈ VG : f (x) ≥ 2n(r)

2?

2n A? r (1En ) (x) ≥
n=0

1 2

16

then, for some 0 ≤ n ≤ n(r ), we necessarily have 1 2n+4 2n SG ( r )
1/4

A? r (1En ) (x) ≥

.

Indeed, otherwise we would have 1 ≤ 2
n(r )

2
n=0

n

A? r

1 (1En ) (x) ≤ 16

n(r )

n=0

2n SG ( r )

1/4

1 21/4 SG (r )1/4 ? 1 < , 16SG (r )1/4 (21/4 ? 1) 2

which is a contradiction. Now, for 0 ≤ n ≤ n(r ) let us consider the set 1 2n+4 2n SG ( r )
1/4

Fn =

x ∈ VG :

A? r

(1En ) (x) ≥

,

which is clearly ?nite and satis?es |Fn | 2n+4 2n SG ( r )
1/4

y ∈Fn

A? r ( 1E n ) ( y ) ≤
y ∈Fn
1 2

|En ∩ S (y, r )| |S (y, r )|

≤ (|En ||Fn |EG (r )) . Hence, for 0 ≤ n ≤ n(r ) we have |Fn | ≤ 2 2 +8 EG (r )SG (r ) 2 |En |. Finally, this estimate together with the fact that SG (r )1/2 ≤ 2 EG (r ) ≥ 1 (since G is in?nite) yield
3(n(r )+1) 2 3n 1

and that

n(r )

|{x ∈ VG :

A? r f (x)

≥ 1}| ≤
n=0

|Fn | + SG (r )
3n

x ∈ VG : f (x) ≥ 2n(r)
1

2 2 E G ( r ) SG ( r ) 2
n∈N∪{0} 1≤2n ≤2SG (r )

x ∈ VG : f (x) ≥ 2n?1

.

GEOMETRIC PROPERTIES OF INFINITE GRAPHS

17

? Proof of Theorem 4.1. Since MG f = supr≥0 A? r f , Lemma 4.2 implies that ∞

|{x ∈ VG :

? MG f (x)

≥ λ}| ≤
r =0 ∞

|{x ∈ VG : A? r f (x) ≥ λ}| 2 2 E G ( r ) SG ( r ) 2
r =0 n∈N∪{0} 1≤2n ≤2SG (r ) ∞
3n 1

x ∈ VG : |f |(x) ≥ 2n?1 λ

=
x∈T n=0 r ∈N∪{0} SG (r )≥2n?1

EG (r )SG (r ) 2 2 2 1{|f (x)|≥2n?1 λ}

1

3n

sup 2
n∈N∪{0}

n 2

E G ( r ) SG ( r )

1 2

2n 1{|f (x)|≥2n?1 λ}
x∈T n=0

r ∈N∪{0} SG (r )≥2n?1
n

sup 2 2
n∈N∪{0}

E G ( r ) SG ( r ) 2
r ∈N∪{0} SG (r )≥2n?1

1

x∈T

1 |f (x)|, λ

as desired. The proof of Theorem 4.1 is complete. References
[1] D. Aalto and J. Kinnunen, The discrete maximal operator in metric spaces, J. Anal. Math. 111 (2010), 369–390. [2] N. Alon and J. H. Spencer, The Probabilistic Method. Third edition. With an appendix on the life and work of Paul Erd¨ os. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008. [3] B. Bollob? as, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer-Verlag, New York, 1998. [4] A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics 244, SpringerVerlag, New York, 2008. [5] A. Carbonaro, G. Mauceri, and S. Meda, H 1 and BMO for certain locally doubling metric measure spaces, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 8 (2009), no. 3, 543–582. [6] E. Carneiro and K. Hughes, On the endpoint regularity of discrete maximal operators, Math. Res. Lett. 19 (2012), no. 6, 1245–1262. [7] M. Cowling, S. Meda, and A. G. Setti, A weak type (1, 1) estimate for a maximal operator on a group of isometries of homogeneous trees, Colloq. Math. 118 (2010), no. 1, 223–232. [8] M. Gromov, Asymptotic invariants of in?nite groups, Geometric Group Theory, Vol. 2 (Sussex, 1991), 1–295, London Math. Soc. Lecture Note Ser. 182, Cambridge Univ. Press, Cambridge, 1993. [9] J. Heinonen, Lectures on Analysis on Metric Spaces, Universitext. Springer-Verlag, New York, 2001. [10] A. Ionescu, An endpoint estimate for the discrete spherical maximal function, Proc. Amer. Math. Soc. 132 (2004), no. 5, 1411–1417. [11] A. Magyar, E. M. Stein, and S. Wainger, Discrete analogues in harmonic analysis: spherical averages, Ann. of Math. (2) 155 (2002), no. 1, 189–208. [12] J. Nagata, Note on dimension theory for metric spaces, Fund. Math. 45 (1958), 143–181. [13] A. Naor and T. Tao, Random martingales and localization of maximal inequalities, J. Funct. Anal. 259 (2010), no. 3, 731–779. [14] F. Nazarov, S. Treil, and A. Volberg, Weak type estimates and Cotlar inequalities for Calder? onZygmund operators on nonhomogeneous spaces, Internat. Math. Res. Notices 1998, no. 9, 463– 487.

18