Document Zbl 1441.60009

Floodings of metric graphs. (English) Zbl 1441.60009

Probab. Theory Relat. Fields 177, No. 1-2, 577-620 (2020).

This paper studies the flooding on metric graphs, which examines the most likely location of \(M\) peaks with respect to the graph structure (given there are \(M\) peaks) when its vertices are randomly labeled. This is treated by introducing a sequence of subdivision metric graphs with vertex numbers tending to infinity, which are embedded in the underlying graph. Based on large deviation theory, it is shown that floodings are associated with entropy-like quantities, and the most likely flooding asymptotically is the one maximizes the entropy. Moreover, the floodings originated from different sources will only meet at the end. The obtain results are used to characterize the root vertex and an adjacent vertex of \(d\)-regular tree of depth at least 2 and \(d\) greater than or equal to 3.

Reviewer: Yilun Shang (Newcastle)

Cited in 1 Document

MSC:

60C05	Combinatorial probability
60F10	Large deviations
05C80	Random graphs (graph-theoretic aspects)

Keywords:

metric graph; flooding; subdivision graph; large deviation

Cite Review PDF

Full Text: DOI arXiv

References:

[1]	Ambjørn, J.; Budd, TG, Trees and spatial topology change in causal dynamical triangulations, J. Phys. A, 46, 31, 315201, 33 (2013) · Zbl 1273.81224 · doi:10.1088/1751-8113/46/31/315201
[2]	Agarwal, R.; Musiker, G.; Sotirov, V.; Wei, F., Involutions on standard Young tableaux and divisors on metric graphs, Electron. J. Comb., 20, 3, P33 (2013) · Zbl 1298.05322 · doi:10.37236/2590
[3]	Aguiar, M.; Nyman, K.; Orellana, R., New results on the peak algebra, J. Algebr. Comb., 23, 2, 149-188 (2006) · Zbl 1107.20009 · doi:10.1007/s10801-006-6922-8
[4]	Bóna, M.: Combinatorics of permutations. In: Discrete Mathematics and Its Applications (Boca Raton), With a Foreword by Richard Stanley, 2nd edn. CRC Press, Boca Raton (2012) · Zbl 1255.05001
[5]	Billey, S.; Burdzy, K.; Pal, S.; Sagan, BE, On meteors, earthworms and WIMPs, Ann. Appl. Probab., 25, 4, 1729-1779 (2015) · Zbl 1322.60208 · doi:10.1214/14-AAP1035
[6]	Billey, S., Burdzy, K., Sagan, B.E.: Permutations with given peak set. J. Integer Seq. 16(6). Article 13.6.1, 18 (2013) · Zbl 1295.05008
[7]	Bouchard, P.; Chang, H.; Ma, J.; Yeh, J.; Yeh, Y-N, Value-peaks of permutations, Electron. J. Comb., 17, 1, R46 (2010) · Zbl 1189.05012 · doi:10.37236/318
[8]	Baker, M.; Faber, X.; Berkolaiko, G.; Carlson, R.; Fulling, SA; Kuchment, P., Metrized graphs, Laplacian operators, and electrical networks, Quantum Graphs and Their Applications, Volume 415 of Contemporary Mathematics, 15-33 (2006), Providence: AMS, Providence · Zbl 1114.94025
[9]	Bergeron, F., Flajolet, P., Salvy, B.: Varieties of increasing trees. In: CAAP ’92 (Rennes, 1992), volume 581 of Lecture Notes in Computer Science, pp. 24-48. Springer, Berlin (1992)
[10]	Buckley, F.; Harary, F., Distance in Graphs (1990), Redwood City: Addison-Wesley Publishing Company, Advanced Book Program, Redwood City · Zbl 0688.05017
[11]	Billera, LJ; Hsiao, SK; van Willigenburg, S., Peak quasisymmetric functions and Eulerian enumeration, Adv. Math., 176, 2, 248-276 (2003) · Zbl 1027.05105 · doi:10.1016/S0001-8708(02)00067-1
[12]	Burdzy, K.; Pal, S., Twin peaks, Random Struct. Algorithms, 56, 432-460 (2020) · Zbl 1436.05091 · doi:10.1002/rsa.20883
[13]	Baker, M.; Rumely, R., Harmonic analysis on metrized graphs, Can. J. Math., 59, 2, 225-275 (2007) · Zbl 1123.43006 · doi:10.4153/CJM-2007-010-2
[14]	Chinburg, T.; Rumely, R., The capacity pairing, J. Reine Angew. Math., 434, 1-44 (1993) · Zbl 0756.14013
[15]	Dembo, A.; Zeitouni, O., Large Deviations Techniques and Applications, Volume 38 of Applications of Mathematics (New York) (1998), New York: Springer, New York · Zbl 0896.60013
[16]	Eden, M.: A two-dimensional growth process. In: Proceedings of 4th Berkeley Symposium on Mathematical Statistics and Probability, vol. IV, pp. 223-239. University of California Press, Berkeley (1961) · Zbl 0104.13801
[17]	Friedlander, L., Genericity of simple eigenvalues for a metric graph, Isr. J. Math., 146, 149-156 (2005) · Zbl 1077.58016 · doi:10.1007/BF02773531
[18]	Françon, J.; Viennot, G., Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d’Euler et nombres de Genocchi, Discrete Math., 28, 1, 21-35 (1979) · Zbl 0409.05003 · doi:10.1016/0012-365X(79)90182-1
[19]	Kitaev, S.: Patterns in permutations and words. In: Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg. With a foreword by Jeffrey B. Remmel (2011) · Zbl 1257.68007
[20]	Kermack, W.O., McKendrick, A.G.: Tests for randomness in a series of numerical observations, vol. 57, pp. 228-240 (1937) · Zbl 0016.41301
[21]	Kuchment, P., Quantum graphs: I. Some basic structures, Waves Random Media, 14, 1, S107-S128 (2004) · Zbl 1063.81058 · doi:10.1088/0959-7174/14/1/014
[22]	Ma, S-M, Derivative polynomials and enumeration of permutations by number of interior and left peaks, Discrete Math., 312, 2, 405-412 (2012) · Zbl 1242.05013 · doi:10.1016/j.disc.2011.10.003
[23]	Nicaise, S.: Some results on spectral theory over networks, applied to nerve impulse transmission. In: Orthogonal Polynomials and Applications. Volume 1171 of Lecture notes in mathematics, pp. 532-541. Springer, Berlin (1985) · Zbl 0586.35071
[24]	Nicaise, S.: Approche spectrale des problèmes de diffusion sure les résaux. Séminaire de Théorie du potentiel. In: Volume 1235 of Lecture notes in mathematics, pp. 120-140. Springer, Berlin (1989) · Zbl 0659.31011
[25]	Nyman, KL, The peak algebra of the symmetric group, J. Algebr. Comb., 17, 3, 309-322 (2003) · Zbl 1021.06003 · doi:10.1023/A:1025000905826
[26]	Petersen, TK, Enriched \(P\)-partitions and peak algebras, Adv. Math., 209, 2, 561-610 (2007) · Zbl 1111.05097 · doi:10.1016/j.aim.2006.05.016
[27]	Post, O.; Arzhantseva, G.; Valette, A., Spectral analysis of metric graphs and related spaces, Limits of Graphs in Group Theory and Computer Science, Fundamental Sciences, 109-140 (2009), Lausanne: EPFL Press, Lausanne · Zbl 1219.05089
[28]	Roth, J.P.: Le spectra du Laplacien sur un graphe. Théorie du potentiel. In: Volume 1096 of Lecture Notes in Mathematics, pp. 521-538. Springer, Berlin (1984)
[29]	Rumely, R.: Capacity theory on algebraic curves. In: Lecture Notes in Mathematics, vol. 1378. Springer, Berlin (1984) · Zbl 0623.14011
[30]	Schocker, M., The peak algebra of the symmetric group revisited, Adv. Math., 192, 2, 259-309 (2005) · Zbl 1132.20009 · doi:10.1016/j.aim.2004.04.007
[31]	Stembridge, JR, Enriched \(P\)-partitions, Trans. Am. Math. Soc., 349, 2, 763-788 (1997) · Zbl 0863.06005 · doi:10.1090/S0002-9947-97-01804-7
[32]	Strehl, V., Enumeration of alternating permutations according to peak sets, J. Comb. Theory Ser. A, 24, 2, 238-240 (1978) · Zbl 0373.05005 · doi:10.1016/0097-3165(78)90010-9
[33]	von Below, J., A characteristic equation associated to an eigenvalue problem on \(c^2\)-networks, Linear Algebra Appl., 71, 309-325 (1985) · Zbl 0617.34010 · doi:10.1016/0024-3795(85)90258-7
[34]	von Below, J., Sturm-Liouville eigenvalue problems on networks, Math. Methods Appl. Sci., 10, 4, 383-395 (1988) · Zbl 0652.34025 · doi:10.1002/mma.1670100404
[35]	Van der Hofstad, R.: Random Graphs and Complex Networks, vol. I. Book in preparation (2014) · Zbl 1361.05002
[36]	Warren, D.; Seneta, E., Peaks and Eulerian numbers in a random sequence, J. Appl. Probab., 33, 1, 101-114 (1996) · Zbl 0845.60035 · doi:10.2307/3215267
[37]	Zhang, S., Admissible pairing on a curve, Invent. Math., 112, 1, 171-193 (1993) · Zbl 0795.14015 · doi:10.1007/BF01232429

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.