American Institute of Mathematical Sciences

Advanced
September  2018, 38(9): 4305-4327. doi: 10.3934/dcds.2018188

Topological classification of $Ω$-stable flows on surfaces by means of effectively distinguishable multigraphs

Vladislav Kruglov , Dmitry Malyshev and  Olga Pochinka ,

HSE; Bolshaya Pecherskaya 25/12, Nizhniy Novgorod, 603155, Russia

* Corresponding author: Olga Pochinka

Received  May 2017 Revised  April 2018 Published  June 2018

Fund Project: Authors are grateful to participants of the seminar "Topological Methods in Dynamics" for fruitful discussions. The classification results (Sections 1–6 without Subsections 5.2, 5.3) were obtained with the support of the Russian Science Foundation (project 17-11-01041). The realisation results (Subsection 5.2, Section 7) were obtained as an output of the research project "Topology and Chaos in Dynamics of Systems, Foliations and Deformation of Lie Algebras (2018)" implemented as part of the Basic Research Program at the National Research University Higher School of Economics (HSE). The algorithmic results (Subsection 5.3, Section 8) were obtained with the support of Russian Foundation for Basic Research 16-31-60008-mol-a-dk and with LATNA laboratory, National Research University Higher School of Economics.

Structurally stable (rough) flows on surfaces have only finitely many singularities and finitely many closed orbits, all of which are hyperbolic, and they have no trajectories joining saddle points. The violation of the last property leads to $Ω$-stable flows on surfaces, which are not structurally stable. However, in the present paper we prove that a topological classification of such flows is also reduced to a combinatorial problem. Our complete topological invariant is a multigraph, and we present a polynomial-time algorithm for the distinction of such graphs up to an isomorphism. We also present a graph criterion for orientability of the ambient manifold and a graph-associated formula for its Euler characteristic. Additionally, we give polynomial-time algorithms for checking the orientability and calculating the characteristic.

Keywords: Ω-stable flow, topological invariant, multigraph, four-colour graph, polynomial-time, algorithms.
Mathematics Subject Classification: 37D05.
Citation: Vladislav Kruglov, Dmitry Malyshev, Olga Pochinka. Topological classification of $Ω$-stable flows on surfaces by means of effectively distinguishable multigraphs. Discrete and Continuous Dynamical Systems, 2018, 38 (9) : 4305-4327. doi: 10.3934/dcds.2018188
References:
[1]

V. E. Alekseev and V. A. Talanov, Graphs and Algorithms. Data structures. Models of Computing (in Russian), Nizhny Novgorod State University Press, Nizhny Novgorod, 2006.

[2]

A. A. Andronov and L. S. Pontryagin, Rough systems (in Russian), Doklady Akademii nauk SSSR, 14 (1937), 247-250. 

[3]

A. V. Bolsinov, S. V. Matveev and A. T. Fomenko, Topological classification of integrable Hamiltonian systems with two degrees of freedom. The list of systems of small complexity (in Russian), Uspekhi matematicheskikh nauk, 45 (1990), 49-77.  doi: 10.1070/RM1990v045n02ABEH002344.

[4]

Yu. G. Borisovich, N. M. Bliznyakov, Ya. A. Izrailevich and T. N. Fomenko, Introduction to Topology (in Russian), "Vyssh. Shkola", Moscow, 1980.

[5]

A. Cobham, The intrinsic computational difficulty of functions, Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Science, North-Holland, Amsterdam, (1964), 24-30. 

[6]

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco, 1979.

[7]

V. Grines, T. Medvedev and O. Pochinka, Dynamical Systems on 2- and 3-Manifolds, Springer International Publishing Switzerland, 2016.

[8]

E. Ya. Gurevich and E. D. Kurenkov, Energy function and topological classification of Morse-Smale flows on surfaces (in Russian), Zhurnal SVMO, 17 (2015), 15-26. 

[9]

D. König, Grafok es matrixok, Matematikai es Fizikai Lapok, 38 (1931), 116-119. 

[10]

V. E. Kruglov, D. S. Malyshev and O. V. Pochinka, Multicolour graph as a complete topological invariant for $Ω$-stable flows without periodic trajectories on surfaces (in Russian), Matematicheskiy Sbornik, 209 (2018), 100-126.  doi: 10.4213/sm8797.

[11]

V. E. Kruglov, T. M. Mitryakova and O. V. Pochinka, About types of cells of $Ω$ -stable flows without periodic trajectories on surfaces (in Russian), Dinamicheskie sistemy, 5 (2015), 43-49. 

[12]

E. A. Leontovich and A. G. Mayer, About trajectories determining qualitative structure of sphere partition into trajectories (in Russian), Doklady Akademii Nauk SSSR, 14 (1937), 251-257. 

[13]

E. A. Leontovich and A. G. Mayer, About scheme determining topological structure of partition into trajectories (in Russian), Doklady Akademii Nauk SSSR, 103 (1955), 557-560. 

[14]

A. G. Mayer, Rough transformations of a circle (in Russian), Uchionye zapiski GGU. Gor'kiy, publikatsii. GGU, 12 (1939), 215-229. 

[15]

G. Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, (1980), 225-235.  doi: 10.1145/800141.804670.

[16]

D. Neumann and T. O'Brien, Global structure of continuous flows on 2-manifolds, J. DifF. Eq., 22 (1976), 89-110.  doi: 10.1016/0022-0396(76)90006-1.

[17]

A. A. Oshemkov and V. V. Sharko, About classification of Morse-Smale flows on 2-manifolds (in Russian), Matematicheskiy sbornik, 189 (1998), 93-140.  doi: 10.1070/SM1998v189n08ABEH000341.

[18]

J. Palis, On the $C^1$ omega-stability conjecture, Publ. Math. Inst. Hautes Études Sci., 66 (1988), 211-215. 

[19]

J. Palis and W. De Melo, Geometric Theory Of Dynamical Systems: An Introduction, Transl. from the Portuguese by A. K. Manning, New York, Heidelberg, Berlin, Springer-Verlag, 1982.

[20]

M. Peixoto, Structural stability on two-dimensional manifolds, Topology, 1 (1962), 101-120.  doi: 10.1016/0040-9383(65)90018-2.

[21]

M. Peixoto, Structural stability on two-dimensional manifolds (a further remarks), Topology, 2 (1963), 179-180.  doi: 10.1016/0040-9383(63)90032-6.

[22]

M. Peixoto, On the Classification of Flows on Two-Manifolds, Dynamical systems Proc. Symp. held at the Univ. of Bahia, Salvador, Brasil, 1971.

[23]

C. Pugh and M. Shub, The $Ω$-stability theorem for flows, Inven. Math., 11 (1970), 150-158.  doi: 10.1007/BF01404608.

[24]

C. Robinson, Dynamical Systems: Stability, Symbolic Dynamics, and Chaos, CRC Press, Boca Raton, Ann Arbor, London, Tokyo, 1995.

[25]

S. Smale, Differentiable dynamical systems, Bull. Amer. Soc., 73 (1967), 747-817.  doi: 10.1090/S0002-9904-1967-11798-1.

show all references

References:
[1]

V. E. Alekseev and V. A. Talanov, Graphs and Algorithms. Data structures. Models of Computing (in Russian), Nizhny Novgorod State University Press, Nizhny Novgorod, 2006.

[2]

A. A. Andronov and L. S. Pontryagin, Rough systems (in Russian), Doklady Akademii nauk SSSR, 14 (1937), 247-250. 

[3]

A. V. Bolsinov, S. V. Matveev and A. T. Fomenko, Topological classification of integrable Hamiltonian systems with two degrees of freedom. The list of systems of small complexity (in Russian), Uspekhi matematicheskikh nauk, 45 (1990), 49-77.  doi: 10.1070/RM1990v045n02ABEH002344.

[4]

Yu. G. Borisovich, N. M. Bliznyakov, Ya. A. Izrailevich and T. N. Fomenko, Introduction to Topology (in Russian), "Vyssh. Shkola", Moscow, 1980.

[5]

A. Cobham, The intrinsic computational difficulty of functions, Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Science, North-Holland, Amsterdam, (1964), 24-30. 

[6]

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco, 1979.

[7]

V. Grines, T. Medvedev and O. Pochinka, Dynamical Systems on 2- and 3-Manifolds, Springer International Publishing Switzerland, 2016.

[8]

E. Ya. Gurevich and E. D. Kurenkov, Energy function and topological classification of Morse-Smale flows on surfaces (in Russian), Zhurnal SVMO, 17 (2015), 15-26. 

[9]

D. König, Grafok es matrixok, Matematikai es Fizikai Lapok, 38 (1931), 116-119. 

[10]

V. E. Kruglov, D. S. Malyshev and O. V. Pochinka, Multicolour graph as a complete topological invariant for $Ω$-stable flows without periodic trajectories on surfaces (in Russian), Matematicheskiy Sbornik, 209 (2018), 100-126.  doi: 10.4213/sm8797.

[11]

V. E. Kruglov, T. M. Mitryakova and O. V. Pochinka, About types of cells of $Ω$ -stable flows without periodic trajectories on surfaces (in Russian), Dinamicheskie sistemy, 5 (2015), 43-49. 

[12]

E. A. Leontovich and A. G. Mayer, About trajectories determining qualitative structure of sphere partition into trajectories (in Russian), Doklady Akademii Nauk SSSR, 14 (1937), 251-257. 

[13]

E. A. Leontovich and A. G. Mayer, About scheme determining topological structure of partition into trajectories (in Russian), Doklady Akademii Nauk SSSR, 103 (1955), 557-560. 

[14]

A. G. Mayer, Rough transformations of a circle (in Russian), Uchionye zapiski GGU. Gor'kiy, publikatsii. GGU, 12 (1939), 215-229. 

[15]

G. Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, (1980), 225-235.  doi: 10.1145/800141.804670.

[16]

D. Neumann and T. O'Brien, Global structure of continuous flows on 2-manifolds, J. DifF. Eq., 22 (1976), 89-110.  doi: 10.1016/0022-0396(76)90006-1.

[17]

A. A. Oshemkov and V. V. Sharko, About classification of Morse-Smale flows on 2-manifolds (in Russian), Matematicheskiy sbornik, 189 (1998), 93-140.  doi: 10.1070/SM1998v189n08ABEH000341.

[18]

J. Palis, On the $C^1$ omega-stability conjecture, Publ. Math. Inst. Hautes Études Sci., 66 (1988), 211-215. 

[19]

J. Palis and W. De Melo, Geometric Theory Of Dynamical Systems: An Introduction, Transl. from the Portuguese by A. K. Manning, New York, Heidelberg, Berlin, Springer-Verlag, 1982.

[20]

M. Peixoto, Structural stability on two-dimensional manifolds, Topology, 1 (1962), 101-120.  doi: 10.1016/0040-9383(65)90018-2.

[21]

M. Peixoto, Structural stability on two-dimensional manifolds (a further remarks), Topology, 2 (1963), 179-180.  doi: 10.1016/0040-9383(63)90032-6.

[22]

M. Peixoto, On the Classification of Flows on Two-Manifolds, Dynamical systems Proc. Symp. held at the Univ. of Bahia, Salvador, Brasil, 1971.

[23]

C. Pugh and M. Shub, The $Ω$-stability theorem for flows, Inven. Math., 11 (1970), 150-158.  doi: 10.1007/BF01404608.

[24]

C. Robinson, Dynamical Systems: Stability, Symbolic Dynamics, and Chaos, CRC Press, Boca Raton, Ann Arbor, London, Tokyo, 1995.

[25]

S. Smale, Differentiable dynamical systems, Bull. Amer. Soc., 73 (1967), 747-817.  doi: 10.1090/S0002-9904-1967-11798-1.

Figure 1.  The case when $U_\mathfrak c$ is homeomorphic to a Möbius band
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  $\phi^t$ and $\Upsilon_{\phi^t}$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The cases of the consistent (leftward) and the inconsistent (rightward) orientation of boundary's connecting component of some $\mathcal E$-region
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  A polygonal region
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  An example of the flow $f^t$ together with the polygonal regions
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  An example of $f^t$ and its four-colour graph
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Two flows from $G$ and their equipped graphs
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Two examples of flows from $G$ differing only by orientation of the limit cycle between $\mathcal M$ and $\mathcal A$ and their equipped graphs
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Two examples of flow from $G$ without $\mathcal A$- and $\mathcal M$-regions differing only by orientation of the limit cycle and their equipped graphs
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  $f^t$, $\Gamma_{\mathcal M}$ and $\Gamma^*_{{\mathcal M}}$
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas. A new proof of the four-colour theorem. Electronic Research Announcements, 1996, 2: 17-25.

[2]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132
[3]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[4]

Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057
[5]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[6]

Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427
[7]

Victor Magron, Marcelo Forets, Didier Henrion. Semidefinite approximations of invariant measures for polynomial systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6745-6770. doi: 10.3934/dcdsb.2019165
[8]

Alexey Gorshkov. Stable invariant manifolds with application to control problems. Mathematical Control and Related Fields, 2021  doi: 10.3934/mcrf.2021040
[9]

Gemma Huguet, Rafael de la Llave, Yannick Sire. Computation of whiskered invariant tori and their associated manifolds: New fast algorithms. Discrete and Continuous Dynamical Systems, 2012, 32 (4) : 1309-1353. doi: 10.3934/dcds.2012.32.1309
[10]

Pengyu Yan, Shi Qiang Liu, Cheng-Hu Yang, Mahmoud Masoud. A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking. Journal of Industrial and Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040
[11]

Matthias Erbar, Dominik Forkert, Jan Maas, Delio Mugnolo. Gradient flow formulation of diffusion equations in the Wasserstein space over a Metric graph. Networks and Heterogeneous Media, 2022  doi: 10.3934/nhm.2022023
[12]

César J. Niche. Topological entropy of a magnetic flow and the growth of the number of trajectories. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 577-580. doi: 10.3934/dcds.2004.11.577
[13]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial and Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253
[14]

Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2943-2970. doi: 10.3934/jimo.2020102
[15]

Isaac A. García, Jaume Giné. Non-algebraic invariant curves for polynomial planar vector fields. Discrete and Continuous Dynamical Systems, 2004, 10 (3) : 755-768. doi: 10.3934/dcds.2004.10.755
[16]

Jingxian Sun, Shouchuan Hu. Flow-invariant sets and critical point theory. Discrete and Continuous Dynamical Systems, 2003, 9 (2) : 483-496. doi: 10.3934/dcds.2003.9.483
[17]

Ursula Hamenstädt. Dynamics of the Teichmüller flow on compact invariant sets. Journal of Modern Dynamics, 2010, 4 (2) : 393-418. doi: 10.3934/jmd.2010.4.393
[18]

Francois Ledrappier and Omri Sarig. Invariant measures for the horocycle flow on periodic hyperbolic surfaces. Electronic Research Announcements, 2005, 11: 89-94.

[19]

Dengfeng Sun, Issam S. Strub, Alexandre M. Bayen. Comparison of the performance of four Eulerian network flow models for strategic air traffic management. Networks and Heterogeneous Media, 2007, 2 (4) : 569-595. doi: 10.3934/nhm.2007.2.569
[20]

Santanu Sarkar, Subhamoy Maitra. Further results on implicit factoring in polynomial time. Advances in Mathematics of Communications, 2009, 3 (2) : 205-217. doi: 10.3934/amc.2009.3.205

2021 Impact Factor: 1.588

Tools

Metrics

  • PDF downloads (210)
  • HTML views (140)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy