Зависимость между песочной группой графа и его матроидом


https://doi.org/10.15217/issn1684-8853.2015.3.23

Полный текст:


Аннотация

Постановка проблемы: определение структуры песочных групп графов представляет собой сложную вычислительную задачу. В попытке снизить сложность решения данной задачи для некоторых классов графов была обнаружена зависимость между песочной группой графа и его матроидом: структура песочной группы графа зависит только от его матроида. Целью статьи является доказательство данного утверждения. Методы: для доказательства изоморфности песочных групп 2-изоморфных графов были использованы элементарные операции с матрицами Лапласа этих графов. Основной результат статьи получен как следствие теоремы Уитни о 2-изоморфных графах. Результаты: доказано, что структура песочной группы графа полностью определяется структурой матроида этого графа.

Об авторе

Илья Александрович Крепкий
Санкт-Петербургский государственный университет
Россия


Список литературы

1. Bak P., Tang C., Wiesenfeld K. Self-organized Criticality: an Explanation of 1/f noise// Physical Review Letters. 1987. N 59(4). P. 381-384.

2. Dhar D. Self-organized Critical State of Sandpile Automaton Models// Physical Review Letters. 1990. N 64(14). P. 1613-1616.

3. Pietronero L., Tartaglia P., Zhang Y. Theoretical Studies of Self-Organized Criticality. Physica A: Statistical Mechanics and its Applications. 1991. N 173(1). P. 22-44.

4. Kirchhoff G. Über die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird// Archives of Chemistry and Physics. 1847. N 72. P. 497-508.

5. Bernardi Olivier. Tutte Polynomial, Subgraphs, Orientations and Sandpile Model: New Connections via Embeddings//The Electronic Journal of Combinatorics. 2008. N 15(1). P. 109.

6. Cori Robert, Rossin Dominique. On the Sandpile Group of Dual Graphs//European Journal of Combinatorics. 2000. N 21(4). P. 447-459.

7. Baker M., Norine S. Riemann-Roch and Abel- Jacobi Theory on a Finite Graph//Advances in Mathematics. 2007. N 215(2). P. 766-788.

8. Perkinson David, Perlman Jacob, Wilmes John. Primer for the Algebraic Geometry of Sandpiles, Tropical and non-Archimedean Geometry//Contemporary Mathematics. 2013. N 605. P. 211-256.

9. Florescu Laura, Morar Daniela, Perkinson David, Salter Nick, Xu Tianyuan. Sandpiles and Dominos. http://arxiv.org/abs/1406.0100 (дата обращения: 21.05.2015).

10. Duzhin S., Pasechnik D. Automorphisms of Necklaces and Sandpile Groups. http://arxiv.org/abs/1304.2563 (дата обращения: 21.05.2015).

11. Matthews K. R. Smith Normal Form. http://www. numbertheory.org/courses/MP274/smith.pdf (дата обращения: 21.05.2015).

12. Крепкий И. А. Песочные группы треугольных бинарных деревьев. http://www.pdmi.ras.ru/pre-print/2012/12-21.html (дата обращения: 21.05.2015).

13. Theory of Matroids/ Ed. by N. White. - Cambridge University Press, 1986. XVII. - 316 p. (Ser. Encyclopedia of Mathematics and its Application. Vol. 26).

14. Крепкий И. А. Склеивание графов и песочные группы//Записки научных семинаров ПОМИ. 2013. Т. 411. С. 119-124.

15. Krepkiy I. A. The Sandpile Groups of Chain-Cyclic Graphs//Записки научных семинаров ПОМИ. 2014. Т. 421. С. 94-112.


Дополнительные файлы

Для цитирования: Крепкий И.А. Зависимость между песочной группой графа и его матроидом. Информационно-управляющие системы. 2015;(3):23-28. https://doi.org/10.15217/issn1684-8853.2015.3.23

For citation: Krepkiy I.A. Relation between the Sandpile Group of a Graph and its Matroid. Information and Control Systems. 2015;(3):23-28. (In Russ.) https://doi.org/10.15217/issn1684-8853.2015.3.23

Просмотров: 28


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)