TY - CPAPER TI - Going deep and going wide : Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth AU - Adler, Isolde AU - Fluck, Eva AU - Seppelt, Tim AU - Spitzer, Gian Luca PY - 2026 SP - 33:1–33:48 PB - Otto-Friedrich-Universität CY - Bamberg UR - https://fis.uni-bamberg.de/handle/uniba/115964 LA - eng AB - We study the expressive power of first-order logic with counting quantifiers, especially the k-variable and quantifier-rank-q fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same k-variable and quantifier-rank-q sentences if and only if they are homomorphism indistinguishable over the class of graphs admitting a k-pebble forest cover of depth q. After reproving this result using elementary means, we provide a graph-theoretic analysis of this graph class. This allows us to separate it from the intersection of the class of all graphs of treewidth at most k−1 and the class of all graphs of treedepth at most q, provided that q is sufficiently larger than k. We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations. We do this by showing that the graph classes of all graphs of treedepth at most q and of graphs admitting a k-pebble forest cover of depth q are homomorphism distinguishing closed, as conjectured by Roberson~(2022). In order to prove Roberson's conjecture for the class of graphs admitting a k-pebble forest cover of depth q we characterise the class in terms of a monotone Cops-and-Robber game.The crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is monotone.To that end, we show how to transform Cop's winning strategy into a pre-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pre-tree-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument. KW - Logic in Computer Science KW - Discrete Mathematics KW - Combinatorics ER - TY - CPAPER TI - Going deep and going wide : Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth AU - Adler, Isolde AU - Fluck, Eva AU - Seppelt, Tim AU - Spitzer, Gian Luca PY - 2026 VL - 22 IS - 2 SP - 33:1–33:48 PB - Erlangen SN - 1860-5974 DO - 10.46298/lmcs-22(2:33)2026 UR - https://fis.uni-bamberg.de/handle/uniba/115889 LA - eng AB - We study the expressive power of first-order logic with counting quantifiers, especially the k-variable and quantifier-rank-q fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same k-variable and quantifier-rank-q sentences if and only if they are homomorphism indistinguishable over the class of graphs admitting a k-pebble forest cover of depth q. After reproving this result using elementary means, we provide a graph-theoretic analysis of this graph class. This allows us to separate it from the intersection of the class of all graphs of treewidth at most k−1 and the class of all graphs of treedepth at most q, provided that q is sufficiently larger than k. We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations. We do this by showing that the graph classes of all graphs of treedepth at most q and of graphs admitting a k-pebble forest cover of depth q are homomorphism distinguishing closed, as conjectured by Roberson~(2022). In order to prove Roberson's conjecture for the class of graphs admitting a k-pebble forest cover of depth q we characterise the class in terms of a monotone Cops-and-Robber game.The crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is monotone.To that end, we show how to transform Cop's winning strategy into a pre-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pre-tree-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument. KW - Logic in Computer Science KW - Discrete Mathematics KW - Combinatorics ER - TY - CPAPER TI - Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth AU - Adler, Isolde AU - Fluck, Eva PY - 2026 SP - 1-18 PB - Otto-Friedrich-Universität CY - Bamberg UR - https://fis.uni-bamberg.de/handle/uniba/115222 LA - eng AB - We study a variation of the cops and robber game characterising treewidth, where in each play at most q cops can be placed in order to catch the robber, where q is a parameter of the game. We prove that if k cops have a winning strategy in this game, then k cops have a monotone winning strategy. As a corollary we obtain a new characterisation of bounded depth treewidth, and we give a positive answer to an open question by Fluck, Seppelt and Spitzer (2024), thus showing that graph classes of bounded depth treewidth are homomorphism distinguishing closed. Our proof of monotonicity substantially reorganises a winning strategy by first transforming it into a pre-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first ‘cleaning up’ procedure along the pre-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of cop placements simultaneously across all branches of the decomposition via a vertex exchange argument. We believe this can be useful in future research. KW - tree decompositions KW - treewidth KW - treedepth KW - cops-and-robber game KW - monotonicity KW - homomorphism distinguishing closure ER - TY - CPAPER TI - BTW 2025 Early Career Researcher Workshop : Message from the Chairs AU - Das, Debasree AU - Nicklas, Daniela AU - Adler, Isolde PY - 2026 SP - 391-392 PB - Otto-Friedrich-Universität CY - Bamberg UR - https://fis.uni-bamberg.de/handle/uniba/114466 LA - eng AB - - KW - - ER - TY - CPAPER TI - BTW 2025 Early Career Researcher Workshop : Message from the Chairs AU - Das, Debasree AU - Nicklas, Daniela AU - Adler, Isolde PY - 2025 T2 - Datenbanksysteme für Business, Technologie und Web - Workshopband (BTW 2025) SP - 391-392 CY - Bonn DO - 10.18420/BTW2025-144 UR - https://fis.uni-bamberg.de/handle/uniba/108756 LA - eng AB - - KW - - ER - TY - CPAPER TI - Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth AU - Adler, Isolde AU - Fluck, Eva PY - 2024 SP - 1-18 PB - arXiv CY - Ithaca, NY DO - 10.48550/arXiv.2402.09139 UR - https://fis.uni-bamberg.de/handle/uniba/107795 LA - eng AB - We study a variation of the cops and robber game characterising treewidth, where in each play at most q cops can be placed in order to catch the robber, where q is a parameter of the game. We prove that if k cops have a winning strategy in this game, then k cops have a monotone winning strategy. As a corollary we obtain a new characterisation of bounded depth treewidth, and we give a positive answer to an open question by Fluck, Seppelt and Spitzer (2024), thus showing that graph classes of bounded depth treewidth are homomorphism distinguishing closed. Our proof of monotonicity substantially reorganises a winning strategy by first transforming it into a pre-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first ‘cleaning up’ procedure along the pre-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of cop placements simultaneously across all branches of the decomposition via a vertex exchange argument. We believe this can be useful in future research. KW - tree decompositions KW - treewidth KW - treedepth KW - cops-and-robber game KW - monotonicity KW - homomorphism distinguishing closure ER - TY - JOUR TI - On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing AU - Adler, Isolde AU - Köhler, Noleen AU - Peng, Pan PY - 2024 JO - SIAM journal on computing : a publication of the Society for Industrial and Applied Mathematics VL - 53 IS - 4 SP - 825-883 PB - SIAM CY - Philadelphia, Pa. SN - 1095-7111 DO - 10.1137/23M1556253 UR - https://fis.uni-bamberg.de/handle/uniba/97085 LA - eng ER - TY - GEN TI - On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing AU - Adler, Isolde AU - Köhler, Noleen AU - Peng, Pan PY - 2023 SP - 1-69 PB - Otto-Friedrich-Universität CY - Bamberg UR - https://fis.uni-bamberg.de/handle/uniba/91019 LA - eng AB - We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix ∃∗∀∗ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix ∀∗∃∗ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by an FO formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then use our class of FO definable bounded-degree expanders to answer a long-standing open problem for proximity-oblivious testers (POTs). POTs are a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SICOMP 2011] show that the graph properties that are constant-query proximity-oblivious testable in the bounded-degree model are precisely the properties that can be expressed as a generalised subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. We give a negative answer by showing that our property is a GSF property which is propagating. Hence in particular, our property does not admit a POT. For this result we establish a new connection between FO properties and GSF-local properties via neighbourhood profiles. KW - Graph property testing KW - first-order logic KW - proximity-oblivious testing KW - locality KW - lower bound ER - TY - JOUR TI - An explicit construction of graphs of bounded degree that are far from being Hamiltonian AU - Adler, Isolde AU - Köhler, Noleen PY - 2023 SP - 1-19 PB - Otto-Friedrich-Universität CY - Bamberg UR - https://fis.uni-bamberg.de/handle/uniba/91022 LA - eng AB - Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. In this paper we study graphs of bounded degree that are \emph{far} from being Hamiltonian, where a graph G on n vertices is \emph{far} from being Hamiltonian, if modifying a constant fraction of n edges is necessary to make G Hamiltonian. We give an explicit deterministic construction of a class of graphs of bounded degree that are locally Hamiltonian, but (globally) far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph. More precisely, we obtain graphs which differ in Θ(n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of o(n) vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with two-sided error) requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010). This is proved via a randomised construction of hard instances. In contrast, our construction is deterministic. So far only very few deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties that are testable in the bounded-degree model. KW - Computer Science - Discrete Mathematics KW - Computer Science - Computational Complexity KW - Computer Science - Data Structures and Algorithms,G.2.2 ER - TY - GEN TI - On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing AU - Adler, Isolde AU - Köhler, Noleen AU - Peng, Pan PY - 2023 SP - 1-69 PB - arXiv CY - Online DO - 10.48550/arxiv.2304.03810 UR - https://fis.uni-bamberg.de/handle/uniba/90093 LA - eng AB - We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix ∃∗∀∗ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix ∀∗∃∗ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by an FO formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then use our class of FO definable bounded-degree expanders to answer a long-standing open problem for proximity-oblivious testers (POTs). POTs are a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SICOMP 2011] show that the graph properties that are constant-query proximity-oblivious testable in the bounded-degree model are precisely the properties that can be expressed as a generalised subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. We give a negative answer by showing that our property is a GSF property which is propagating. Hence in particular, our property does not admit a POT. For this result we establish a new connection between FO properties and GSF-local properties via neighbourhood profiles. KW - Graph property testing KW - first-order logic KW - proximity-oblivious testing KW - locality KW - lower bound ER - TY - JOUR TI - Faster Property Testers in a Variation of the Bounded Degree Model AU - Adler, Isolde AU - Fahey, Polly PY - 2023 JO - ACM Transactions on Computational Logic : TOCL VL - 24 IS - 3 SP - 1-24 PB - Association for Computing Machinery (ACM) CY - New York SN - 1529-3785 DO - 10.1145/3584948 UR - https://fis.uni-bamberg.de/handle/uniba/90091 LA - eng ER - TY - JOUR TI - Vapnik–Chervonenkis dimension and density on Johnson and Hamming graphs AU - Adler, Isolde AU - Benediktsson, Bjarki Geir AU - Macpherson, Dugald PY - 2022 JO - Discrete applied mathematics : the journal of combinatorial algorithms, informatics and computational sciences VL - 312 SP - 29-44 PB - Elsevier CY - Amsterdam SN - 0166-218X DO - 10.1016/j.dam.2021.09.017 UR - https://fis.uni-bamberg.de/handle/uniba/90094 LA - eng ER -