@misc{barbieri2025automorphismgroupstronglyirreducible,title={The automorphism group of a strongly irreducible subshift on a group},author={Barbieri, Sebastián and Carrasco-Vargas, Nicanor and Rivera-Burgos, Paola},year={2025},eprint={2501.14463},archiveprefix={arXiv},primaryclass={math.DS},url={https://arxiv.org/abs/2501.14463},}
Effective dynamical systems beyond dimension zero and factors of SFTs
Sebastián Barbieri, Nicanor Carrasco-Vargas, and Cristóbal Rojas
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={2025},volume={45},number={5},pages={1329–1369}}
On a Rice theorem for dynamical properties of SFTs on groups
@article{carrascovargas2024rice,title={On a Rice theorem for dynamical properties of SFTs on groups},doi={https://doi.org/10.1007/s00013-025-02125-x},journal={Archiv der Mathematik},author={Carrasco-Vargas, Nicanor},year={2025},volume={124},issue={6},number={591-603},archiveprefix={arXiv},}
2024
On the complexity of the Eulerian path problem for infinite graphs
Nicanor Carrasco-Vargas, Valentino Delle Rose, and Cristóbal Rojas
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}}
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'}}
Translation-like actions by $\mathbb{Z}$, the subgroup membership problem, and Medvedev degrees of effective subshifts
@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},}
2023
Infinite Eulerian paths are computable on graphs with vertices of infinite degree
@misc{carrascovargas2023characterization,title={Infinite Eulerian paths 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.}}
@phdthesis{thesis,title={Subshifts on groups and computable analysis},author={Carrasco-Vargas, Nicanor},year={2024},school={Pontifical Catholic University of Chile},type={PhD Thesis},}
