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

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

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.

Citation: Vladislav Kruglov, Dmitry Malyshev, Olga Pochinka. Topological classification of $Ω$-stable flows on surfaces by means of effectively distinguishable multigraphs. Discrete & Continuous Dynamical Systems - A, 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. Google Scholar

[2]

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

[3]

A. V. BolsinovS. 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.  Google Scholar

[4]

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

[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.   Google Scholar

[6]

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

[7]

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

[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.   Google Scholar

[9]

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

[10]

V. E. KruglovD. 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.  Google Scholar

[11]

V. E. KruglovT. 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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[14]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.  Google Scholar

[20]

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

[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.  Google Scholar

[22]

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

[23]

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

[24]

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

[25]

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

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. Google Scholar

[2]

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

[3]

A. V. BolsinovS. 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.  Google Scholar

[4]

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

[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.   Google Scholar

[6]

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

[7]

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

[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.   Google Scholar

[9]

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

[10]

V. E. KruglovD. 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.  Google Scholar

[11]

V. E. KruglovT. 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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[14]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.  Google Scholar

[20]

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

[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.  Google Scholar

[22]

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

[23]

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

[24]

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

[25]

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

Figure 1.  The case when $U_\mathfrak c$ is homeomorphic to a Möbius band
Figure 2.  $\phi^t$ and $\Upsilon_{\phi^t}$
Figure 3.  The cases of the consistent (leftward) and the inconsistent (rightward) orientation of boundary's connecting component of some $\mathcal E$-region
Figure 4.  A polygonal region
Figure 5.  An example of the flow $f^t$ together with the polygonal regions
Figure 6.  An example of $f^t$ and its four-colour graph
Figure 7.  Two flows from $G$ and their equipped graphs
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 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 10.  $f^t$, $\Gamma_{\mathcal M}$ and $\Gamma^*_{{\mathcal M}}$
[1]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[2]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[3]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010

[4]

Tian Ma, Shouhong Wang. Topological phase transition III: Solar surface eruptions and sunspots. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020350

[5]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[6]

Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137

[7]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336

[8]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[9]

Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318

[10]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[11]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[12]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[13]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[14]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (102)
  • HTML views (135)
  • Cited by (2)

[Back to Top]