2026-07-25T14:19:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25090 2026-02-09T08:06:04Z ddc:004 open_access

Cat Herding Game Played on Infinite Trees Ashmore, Rylo Pinchinat, Sophie Pursuit-evasion games Cat Herding Cat number Infinite trees Monadic Second Order Logic Ordinals The game of Cat Herding is played on a graph between two players, the cat and the herder. The game setup consists of the cat choosing a starting vertex for their cat token. Then, both players alternate turns, beginning with the herder: they delete (any) one edge, called a cut, and the cat moves along a path to a new vertex. While this game has been studied on finite graph arenas regarding how optimally herder wins, we shift our attention to an infinite version of the game where the cat may now survive indefinitely. We show that cat winning positions in an infinite tree can be characterized by a second-order monadic statement, also amounting to having a complete infinite binary tree minor, or having uncountably many distinct rays. We take advantage of the logical characterization of cat winning positions to generalize a measure known as the cat number, to ordinals. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rylo Ashmore and Sophie Pinchinat 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.10 urn:nbn:de:0030-drops-250902 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode