3 papers
cs.LO2026
Model checking in finite fields and finite groups
Samuel Braunfeld
We prove the following results. 1. First order model checking is fixed-parameter tractable on the class of finite fields, as a corollary of results of Ax on the theory of (pseudo)f…
math.CO2025
On first-order transductions of classes of graphs
Samuel Braunfeld, Jaroslav NeÅ¡etÅil, Patrice Ossona de Mendez +1
We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether o…
cs.DM2024
Decomposition horizons and a characterization of stable hereditary classes of graphs
Samuel Braunfeld, Jaroslav NeÅ¡etÅil, Patrice Ossona de Mendez +1
The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the…