2024

1. 

   On the complexity of the Eulerian path problem for infinite graphs

   Nicanor Carrasco-Vargas, Valentino Delle Rose, and Cristóbal Rojas

   2024

   Abs arXiv Bib

   We revisit the problem of algorithmically deciding whether a given infinite connected graph has an Eulerian path, namely, a path that uses every edge exactly once. It has been recently observed that this problem is $D_3^0$-complete for graphs that have a computable description, whereas it is $\Pi_2^0$-complete for graphs that have a highly computable description, and that this same bound holds for the class of automatic graphs. A closely related problem consists of determining the number of ends of a graph, namely, the maximum number of distinct infinite connected components the graph can be separated into after removing a finite set of edges. The complexity of this problem for highly computable graphs is known to be $\Pi_2^0$-complete as well. The connection between these two problems lies in that only graphs with one or two ends can have Eulerian paths. In this paper we are interested in understanding the complexity of the infinite Eulerian path problem in the setting where the input graphs are known to have the right number of ends. We find that in this setting the problem becomes strictly easier, and that its exact difficulty varies according to whether the graphs have one or two ends, and to whether the Eulerian path we are looking for is one-way or bi-infinite. For example, we find that deciding existence of a bi-infinite Eulerian path for one-ended graphs is only $\Pi_1^0$-complete if the graphs are highly computable, and that the same problem becomes decidable for automatic graphs. Our results are based on a detailed computability analysis of what we call the Separation Problem, which we believe to be of independent interest. For instance, as a side application, we observe that K\"onig's infinity lemma, well known to be non-effective in general, becomes effective if we restrict to graphs with finitely many ends.

   @misc{carrascovargas2024complexityeulerianpathproblem,
     title = {On the complexity of the Eulerian path problem for infinite graphs},
     author = {Carrasco-Vargas, Nicanor and Rose, Valentino Delle and Rojas, Cristóbal},
     year = {2024},
     doi = {https://doi.org/10.48550/arXiv.2409.03113},
     url = {https://arxiv.org/abs/2409.03113}
   }

2. 

   Translation-like actions by $\mathbb{Z}$, the subgroup membership problem, and Medvedev degrees of effective subshifts

   Nicanor Carrasco-Vargas

   Groups, Geometry, and Dynamics, 2024

   Abs arXiv Bib PDF Website

   We show that every infinite, locally finite, and connected graph admits a translation-like action by $\mathbb{Z}$, and that this action can be taken to be transitive exactly when the graph has either one or two ends. The actions constructed satisfy $d(v,v\ast 1)\leq 3$ for every vertex $v$. This strengthens a theorem by Brandon Seward. We also study the effective computability of translation-like actions on groups and graphs. We prove that every finitely generated infinite group with decidable word problem admits a translation-like action by $\mathbb{Z}$ which is computable and satisfies an extra condition which we call decidable orbit membership problem. As a nontrivial application of our results, we prove that for every finitely generated infinite group with decidable word problem, effective subshifts attain all $\Pi_1^0$​ Medvedev degrees. This extends a classification proved by Joseph Miller for $\mathbb{Z}^d,d\geq 1$.

   @article{carrascovargas2023geometric,
     title = {Translation-like actions by $\mathbb{Z}$, the subgroup membership problem, and Medvedev degrees of effective subshifts},
     author = {Carrasco-Vargas, Nicanor},
     journal = {Groups, Geometry, and Dynamics},
     year = {2024},
     pages = {published online first},
     doi = {DOI 10.4171/GGD/817},
     url = {https://ems.press/journals/ggd/articles/14298058},
   }

3. 

   Effective dynamical systems beyond dimension zero and factors of SFTs

   Sebastián Barbieri, Nicanor Carrasco-Vargas, and Cristóbal Rojas

   Ergodic Theory and Dynamical Systems, 2024

   Abs arXiv Bib PDF Website

   Using tools from computable analysis we develop a notion of effectiveness for general dynamical systems as those group actions on arbitrary spaces that contain a computable representative in their topological conjugacy class. Most natural systems one can think of are effective in this sense, including some group rotations, affine actions on the torus and finitely presented algebraic actions. We show that for finitely generated and recursively presented groups, every effective dynamical system is the topological factor of a computable action on an effectively closed subset of the Cantor space. We then apply this result to extend the simulation results available in the literature beyond zero-dimensional spaces. In particular, we show that for a large class of groups, many of these natural actions are topological factors of subshifts of finite type.

   @article{BARBIERI_CARRASCO-VARGAS_ROJAS_2024,
     title = {Effective dynamical systems beyond dimension zero and factors of SFTs},
     doi = {10.1017/etds.2024.79},
     journal = {Ergodic Theory and Dynamical Systems},
     author = {Barbieri, Sebastián and Carrasco-Vargas, Nicanor and Rojas, Cristóbal},
     year = {2024},
     url = {https://www.cambridge.org/core/journals/ergodic-theory-and-dynamical-systems/article/effective-dynamical-systems-beyond-dimension-zero-and-factors-of-sfts/F64D571FCEDD8528C3EC0640C76FFA9F},
     pages = {1–41}
   }

4. 

   On a Rice theorem for dynamical properties of SFTs on groups

   Nicanor Carrasco-Vargas

   2024

   Abs arXiv Bib Poster

   Let G be a group with undecidable domino problem (such as $\mathbb{Z}^2$). We prove the undecidability of all nontrivial dynamical properties for sofic G-subshifts, that such a result fails for SFTs, and an undecidability result for dynamical properties of G-SFTs similar to the Adian-Rabin theorem. For G amenable we prove that topological entropy is not computable from presentations of SFTs, and a more general result for dynamical invariants taking values in partially ordered sets.

   @misc{carrascovargas2024rice,
     title = {On a Rice theorem for dynamical properties of SFTs on groups},
     author = {Carrasco-Vargas, Nicanor},
     year = {2024},
     archiveprefix = {arXiv},
   }

5. 

   Medvedev degrees of subshifts on groups

   Sebastián Barbieri, and Nicanor Carrasco-Vargas

   2024

   Abs arXiv Bib

   The Medvedev degree of a subshift is a dynamical invariant of computable origin that can be used to compare the complexity of subshifts that contain only uncomputable configurations. We develop theory to describe how these degrees can be transferred from one group to another through algebraic and geometric relations, such as quotients, subgroups, translation-like actions and quasi-isometries. We use the aforementioned tools to study the possible values taken by this invariant on subshifts of finite type on some finitely generated groups. We obtain a full classification for some classes, such as virtually polycyclic groups and branch groups with decidable word problem. We also show that all groups which are quasi-isometric to the hyperbolic plane admit SFTs with nonzero Medvedev degree. Furthermore, we provide a classification of the degrees of sofic subshifts for several classes of groups.

   @misc{barbieri2024medvedev,
     title = {Medvedev degrees of subshifts on groups},
     author = {Barbieri, Sebastián and Carrasco-Vargas, Nicanor},
     year = {2024},
     primaryclass = {id='math.DS' full_name='Dynamical Systems' is_active=True alt_name=None in_archive='math' is_general=False description='Dynamics of differential equations and flows, mechanics, classical few-body problems, iterations, complex dynamics, delayed differential equations'}
   }

2023

1. 

   Infinite Eulerian trails are computable on graphs with vertices of infinite degree

   Nicanor Carrasco-Vargas

   2023

   Accepted in Computability.

   Abs arXiv Bib PDF

   The Erdős, Grünwald and Weiszfeld theorem provides a characterization of infinite graphs which are Eulerian. That is, infinite graphs which admit infinite Eulerian trails. In this article we complement this theorem with a characterization of those finite trails that can be extended to infinite Eulerian trails. This allows us to prove an effective version of the Erdős, Grünwald and Weiszfeld theorem for a class of graphs that includes non locally finite ones, generalizing a theorem of D.Bean.

   @misc{carrascovargas2023characterization,
     title = {Infinite Eulerian trails are computable on graphs with vertices of infinite degree},
     author = {Carrasco-Vargas, Nicanor},
     year = {2023},
     archiveprefix = {arXiv},
     primaryclass = {math.CO},
     url = {https://arxiv.org/abs/2303.14820},
     note = {Accepted in Computability.}
   }

1. 

   Subshifts on groups and computable analysis

   Nicanor Carrasco-Vargas

   2024

   PhD thesis, https://repositorio.uc.cl/handle/11534/88339

   Abs Bib PDF Website

   Subshifts are a fundamental class of topological dynamical systems. The study of subshifts on groups different from $\mathbb{Z}$, such as $\mathbb{Z}^d$, $d\geq 2$, has been a subject of intense research in recent years. These investigations have unveiled aremarkable connection between dynamics and recursion theory. That is, different questions about the dynamics of these systems have been answered in recursion-theoretical terms. In this work we further explore this connection. We use the framework of computable analysis to explore the class of effective dynamical systems on metric spaces, and relate these systems to subshifts of finite type (SFTs) on groups. We prove that every effective dynamical system on a general metric space is the topological factor of an effective dynamical system with topological dimension zero. We combine this result with existing simulation results to obtain new examples of systems that are factors of SFTsWe also study a conjugacy invariant for subshifts on groups called Medvedev degree. This invariant is a complexity measure of algorithmic nature. We develop the basic theory of these degrees for subshifts on arbitrary finitely generated groups. Using these tools we are able to classify the values that this invariant attains for SFTs and other classes of subshifts on several groups. Furthermore, we establish a connection between these degrees and the distribution of isolated points in the space of all subshifts. Motivated by the study of Medvedev degrees of subshifts, we also consider translation-like actions of groups on graphs. We prove that every connected, locally finite, and infinite graph admits a translation by $\mathbb{Z}$, and that this action can be chosen transitive exactly when the graph has one or two ends. This generalizes a result of Seward about translation-like action of $\mathbb{Z}$ on finitely generated groups. Our proof is constructive, and allows us to prove that under natural hypotheses, translation-like actions by $\mathbb{Z}$ on groups and graphs can be effectively computed.

   @phdthesis{thesis,
     title = {Subshifts on groups and computable analysis},
     author = {Carrasco-Vargas, Nicanor},
     year = {2024},
     school = {Pontifical Catholic University of Chile},
     type = {PhD Thesis},
     note = {PhD thesis, https://repositorio.uc.cl/handle/11534/88339},
     url = {https://repositorio.uc.cl/handle/11534/88339},
   }