OFFSET
1,1
COMMENTS
This can be proved using the definition of the Laakso graph. The Laakso graph of level 0 is two vertices joined by an edge. The level 1 Laakso graph L_1 is obtained by replacing part of the edge of L_0 with a 4-cycle. Then the Laakso graph L_(n+1) is obtained from L_n by replacing each edge {uv} in L_n with a copy of the graph L_1, where u and v are identified with the vertices of degree 1 in L_1.
LINKS
Paolo Xausa, Table of n, a(n) for n = 1..1000
Y. Bartal, L.-A. Gottlieb, and O. Neiman, On the Impossibility of Dimension Reduction for Doubling Subsets of l_p, SIAM Journal on Discrete Mathematics, vol. 29, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1207-1222, Jan. 2015.
F. Baudier, K. Swieçicki, and A. Swift, No dimension reduction for doubling subsets of $\ell_q$ when q > 2 revisited, Journal of Mathematical Analysis and Applications, vol. 504, no. 2. Elsevier BV, p. 125407, Dec. 2021.
S. J. Dilworth, D. Kutzarova, and M. I. Ostrovskii, Lipschitz-free Spaces on Finite Metric Spaces, Canadian Journal of Mathematics, vol. 72, no. 3. Canadian Mathematical Society, pp. 774-804, Feb. 13, 2019.
Stephen J. Dilworth, Denka Kutzarova, and Mikhail I. Ostrovskii, Analysis on Laakso graphs with application to the structure of transportation cost spaces, arXiv:2007.07949 [math.FA], 2020-2021. See drawing of L_1 on page 4.
S. J. Dilworth, D. Kutzarova, and M. I. Ostrovskii, Analysis on Laakso graphs with application to the structure of transportation cost spaces, Positivity 25, 1403-1435 (2021).
S. J. Dilworth, D. Kutzarova, and S. Stankov, Metric embeddings of Laakso graphs into Banach spaces. Banach J. Math. Anal. 16, 60 (2022).
T. Laakso, Ahlfors Q-regular spaces with arbitrary Q > 1 admitting weak Poincaré inequality, GAFA, Geom. funct. anal. 10, 111-123 (2000).
U. Lang and C. Plaut, Bilipschitz Embeddings of Metric Spaces into Space Forms, Geometriae Dedicata 87, 285-307 (2001).
A. Margaris and J. C. Robinson, Some comments on Laakso graphs and sets of differences, Comptes Rendus. Mathématique, vol. 358, no. 4. Cellule MathDoc/CEDRAM, pp. 515-521, Jul. 28, 2020.
MathOverflow, Implementation of the "Laakso Graph" in Python, 2023.
O. Neiman, Low Dimensional Embeddings of Doubling Metrics, Theory Comput Syst 58, 133-152 (2016).
Th. Schlumprecht and G. Tresch, “Stochastic Embeddings of Graphs into Trees.” arXiv preprint arXiv:2306.06222 [math.CO], 2023.
Index entries for linear recurrences with constant coefficients, signature (7,-6).
FORMULA
a(n) = a(n-1) + 4*6^(n-1).
a(n) = (2/5) * (2*6^n+3). - Christian Krause, Sep 30 2023
EXAMPLE
The order 1 Laakso graph L_1 has 6 vertices and 6 edges. L_(n+1) is obtained from L_n by replacing each edge in L_n with a copy of L_1. This gives us 6 vertices, then 30, then 174, and so on.
MATHEMATICA
LinearRecurrence[{7, -6}, {6, 30}, 30] (* Paolo Xausa, Oct 16 2023 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ken McCabe, Aug 30 2023
STATUS
approved