Изопериметрический профиль и резистивные диаметры графов Кэли на симметрической группе с порождающими множествами Коксетера

резистивное расстояние, граф Кэли пузырьковой сортировки, изопериметрические неравенства, постоянная Чигера

1. Krebs M., Shaneen A. Expander Families and Cayley Graphs. Oxford University Press, 2011. 288 p.

2. Lyons R., Peres Y. Probability on Trees and Networks, Cambridge University Press, 2016. 699 p. http://doi.org/10.1017/9781316672815

3. Klartag B., Kozma G., Ralli P., Tetali P. Discrete curvature and abelian groups. Canadian Journal of Mathematics, 2016, vol. 6, no. 3, pp. 655–674. https://doi.org/10.4153/CJM-2015-046-8

4. Chung F. Four proofs for the cheeger inequality and graph partition algorithms. AMS/IP Studies in Advanced Mathematics, 2010, vol. 48, pp. 331–349. https://doi.org/10.1090/amsip/048/17

5. Ohring S. R., Sarkar F., Das S. K., Hohndel D. H. Cayley graph connected cycles: a new class of fixed-degree interconnection networks. Proceedings of HICSS’95. Wailea, 1995, pp. 479–488. https://doi.org/10.1109/HICSS.1995.375509

6. Akers S. B., Krishnamurthy B. A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 1989, vol. 38, no. 4, pp. 555– 565. https://doi.org/10.1109/12.21148

7. Sauerwald T. Randomized Protocols for Information Dissemination. Padeborn, 2008. 150 p.

8. Heydemann M. C. Cayley graphs and interconnection networks. Graph Symmetry. NATO ASI Series. Dordrecht, Springer, 1997, vol. 497, pp. 167–224. https://doi.org/10.1007/978-94-015-8937-6_5

9. Luxburg U., Radl A., Hein M. Hitting and commute times in large random neighbourhood graphs. Journal of Machine Learning Research, 2014, vol. 15, no. 52, pp. 1751– 1798. https://dl.acm.org/doi/10.5555/2627435.2638591

10. Klein D. J., Randic M. Resistance distance. Journal of Mathematical Chemistry, 1993, vol. 12, no. 1, pp. 81–95. https://doi.org/10.1007/BF01164627

11. Seshu S., Reed M. B. Linear graphs and electrical networks. Addison-Wesley Publishing Company, 1961. 315 p.

12. Gvishiani A. D., Gurvich V. A. Metric and ultrametric spaces of resistances. Russian Mathematical Surveys, 1987, vol. 42, no. 6, pp. 235–236. https://doi.org/10.1070/rm1987v042n06abeh001494

13. Babai L., Szegedy M. Local expansion of symmetrical graphs. Combinatorics, Probability and Computing, 1992, vol. 1, no. 1, pp. 1–11. https://doi.org/10.1017/S0963548300000031

14. Alahmadi A., Alhazmi H., Ali S., Deza M., Sikiric M. D., Sole P. Hypercube emulation of interconnection networks topologies. Mathematical Methods in Applied Sciences, 2016, vol. 39, no. 16, pp. 4856–4865. https://doi.org/10.1002/mma.3820

15. Hart S. A note on the edges of the n-cube. Discrete Mathematics, 1976, vol. 14, no. 2, pp. 157–163. https://doi.org/10.1016/0012-365X(76)90058-3

16. Mohar B. Isoperimetric numbers of graphs. Journal of Combinatorial Theory, Series B, 1989, vol. 47, no. 3, pp. 274–291. https://doi.org/10.1016/0095-8956(89)90029-4

17. Bollobas B., Leader L. Edge-isoperimetric inequalities in the grid. Combinatorica, 1991, vol. 11, no. 4, pp. 299–314. https://doi.org/10.1007/BF01275667

18. Siconolfi V. Ricci curvature, graphs and eigenvalues. Linear Algebra and its Applications, 2021, vol. 620, pp. 242–267. https://doi.org/10.1016/j.laa.2021.02.026

19. Konstantinova E. Vertex reconstruction in Cayley graphs. Discrete Mathematics, 2009, vol. 309, no. 3, pp. 548–559. https://doi.org/10.1016/j.disc.2008.07.039

20. Vaskouski M. M., Zadorozhnyuk A. O. Asymptotic behavior of resistance distances in Cayley graphs. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2018, vol. 62, no. 2, pp. 140–146 (in Russian). https://doi.org/10.29235/1561-8323-2018-62-2-140-146

21. Godsil C., Royle G. Algebraic Graph Theory. Springer, 2001. 443 p. https://doi.org/10.1007/978-1-4613-0163-9

22. Gould R. Graph Theory. Dover Publications, Inc., 2012. 350 p.

23. Atzmon N., Ellis D., Kogan D. An isoperimetric inequality for conjugation invariant sets in the symmetric group. Israel Journal of Mathematics, 2016, vol. 212, no. 1, pp. 139–162. https://doi.org/10.1007/s11856-016-1296-7

24. Benjamini I., Kozma G. A resistance bound via an isoperimetric inequality. Combinatorica, 2005, vol. 25, no. 6, pp. 645–650. https://doi.org/10.1007/s00493-005-0040-4

25. Friedman J. On Cayley graphs on the symmetric group generated by transpositions. Combinatorica, 2000, vol. 20, no. 4, pp. 505–519. https://doi.org/10.1007/s004930070004

26. Kalpakis K., Yesha, Y. On the bisection width of the transposition network. Networks, 1997, vol. 29, no. 1, pp. 69–76. https://doi.org/10.1002/(sici)1097-0037(199701)29:1<69::aid-net7>3.0.co;2-a

27. Chandra A. K., Raghavan P., Ruzzo W. L., Smolensky R., Tiwari P. The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 1996, vol. 6, no. 4, pp. 312–340. https://doi.org/10.1007/BF01270385

28. Gurvich V. Metric and ultrametric spaces of resistances. Discrete Applied Mathematics, 2010, vol. 158, no. 14, pp. 1496–1505. https://doi.org/10.1016/j.dam.2010.05.007

29. Vaskouski M., Zadorozhnyuk A. Resistance distances in Cayley graphs on symmetric group. Discrete Applied Mathematics, 2017, vol. 227, pp. 121–135. https:/doi.org/10.1016/j.dam.2017.04.044

30. Kaneko K., Suzuki Y. Node-to-node internally disjoint paths problem in bubble-sort graphs. 10th IEEE Pacific Rim International Symposium on Dependable Computing, 2004. Proceedings, pp. 173–182. https://doi.org/10.1109/PRDC.2004.1276568