@inproceedings{adler2026_115964,
  title = {Going deep and going wide : Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth},
  author = {Adler, Isolde and Fluck, Eva and Seppelt, Tim and Spitzer, Gian Luca},
  year = {2026},
  pages = {33:1–33:48},
  publisher = {Otto-Friedrich-Universität},
  address = {Bamberg},
  urn = {urn:nbn:de:bvb:473-irb-115964x},
  url = {https://fis.uni-bamberg.de/handle/uniba/115964},
  language = {eng},
  abstract = {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.},
  keywords = {Logic in Computer Science, Discrete Mathematics, Combinatorics}
}

@inproceedings{adler2026_115889,
  title = {Going deep and going wide : Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth},
  author = {Adler, Isolde and Fluck, Eva and Seppelt, Tim and Spitzer, Gian Luca},
  year = {2026},
  volume = {22},
  number = {2},
  pages = {33:1–33:48},
  publisher = {Erlangen},
  issn = {1860-5974},
  doi = {10.46298/lmcs-22(2:33)2026},
  url = {https://fis.uni-bamberg.de/handle/uniba/115889},
  language = {eng},
  abstract = {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.},
  keywords = {Logic in Computer Science, Discrete Mathematics, Combinatorics}
}

@inproceedings{adler2026_115222,
  title = {Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth},
  author = {Adler, Isolde and Fluck, Eva},
  year = {2026},
  pages = {1-18},
  publisher = {Otto-Friedrich-Universität},
  address = {Bamberg},
  urn = {urn:nbn:de:bvb:473-irb-115222x},
  url = {https://fis.uni-bamberg.de/handle/uniba/115222},
  language = {eng},
  abstract = {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.},
  keywords = {tree decompositions, treewidth, treedepth, cops-and-robber game, monotonicity, homomorphism distinguishing closure}
}

@inproceedings{das2026_114466,
  title = {BTW 2025 Early Career Researcher Workshop : Message from the Chairs},
  author = {Das, Debasree and Nicklas, Daniela and Adler, Isolde},
  year = {2026},
  pages = {391-392},
  publisher = {Otto-Friedrich-Universität},
  address = {Bamberg},
  urn = {urn:nbn:de:bvb:473-irb-114466x},
  url = {https://fis.uni-bamberg.de/handle/uniba/114466},
  language = {eng},
  abstract = {-},
  keywords = {-}
}

@inproceedings{das2025_108756,
  title = {BTW 2025 Early Career Researcher Workshop : Message from the Chairs},
  author = {Das, Debasree and Nicklas, Daniela and Adler, Isolde},
  year = {2025},
  booktitle = {Datenbanksysteme für Business, Technologie und Web - Workshopband (BTW 2025)},
  pages = {391-392},
  address = {Bonn},
  doi = {10.18420/BTW2025-144},
  url = {https://fis.uni-bamberg.de/handle/uniba/108756},
  language = {eng},
  abstract = {-},
  keywords = {-}
}

@inproceedings{adler2024_107795,
  title = {Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth},
  author = {Adler, Isolde and Fluck, Eva},
  year = {2024},
  pages = {1-18},
  publisher = {arXiv},
  address = {Ithaca, NY},
  doi = {10.48550/arXiv.2402.09139},
  url = {https://fis.uni-bamberg.de/handle/uniba/107795},
  language = {eng},
  abstract = {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.},
  keywords = {tree decompositions, treewidth, treedepth, cops-and-robber game, monotonicity, homomorphism distinguishing closure}
}

@article{adler2024_97085,
  title = {On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing},
  author = {Adler, Isolde and Köhler, Noleen and Peng, Pan},
  year = {2024},
  journal = {SIAM journal on computing : a publication of the Society for Industrial and Applied Mathematics},
  volume = {53},
  number = {4},
  pages = {825-883},
  publisher = {SIAM},
  address = {Philadelphia, Pa.},
  issn = {1095-7111},
  doi = {10.1137/23M1556253},
  url = {https://fis.uni-bamberg.de/handle/uniba/97085},
  language = {eng}
}

@misc{adler2023_91019,
  title = {On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing},
  author = {Adler, Isolde and Köhler, Noleen and Peng, Pan},
  year = {2023},
  pages = {1-69},
  publisher = {Otto-Friedrich-Universität},
  address = {Bamberg},
  urn = {urn:nbn:de:bvb:473-irb-910192},
  url = {https://fis.uni-bamberg.de/handle/uniba/91019},
  language = {eng},
  abstract = {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.},
  keywords = {Graph property testing, first-order logic, proximity-oblivious testing, locality, lower bound}
}

@article{adler2023_91022,
  title = {An explicit construction of graphs of bounded degree that are far from being Hamiltonian},
  author = {Adler, Isolde and Köhler, Noleen},
  year = {2023},
  pages = {1-19},
  publisher = {Otto-Friedrich-Universität},
  address = {Bamberg},
  urn = {urn:nbn:de:bvb:473-irb-910220},
  url = {https://fis.uni-bamberg.de/handle/uniba/91022},
  language = {eng},
  abstract = {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.},
  keywords = {Computer Science - Discrete Mathematics, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms,G.2.2}
}

@misc{adler2023_90093,
  title = {On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing},
  author = {Adler, Isolde and Köhler, Noleen and Peng, Pan},
  year = {2023},
  pages = {1-69},
  publisher = {arXiv},
  address = {Online},
  doi = {10.48550/arxiv.2304.03810},
  url = {https://fis.uni-bamberg.de/handle/uniba/90093},
  language = {eng},
  abstract = {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.},
  keywords = {Graph property testing, first-order logic, proximity-oblivious testing, locality, lower bound}
}

@article{adler2023_90091,
  title = {Faster Property Testers in a Variation of the Bounded Degree Model},
  author = {Adler, Isolde and Fahey, Polly},
  year = {2023},
  journal = {ACM Transactions on Computational Logic : TOCL},
  volume = {24},
  number = {3},
  pages = {1-24},
  publisher = {Association for Computing Machinery (ACM)},
  address = {New York},
  issn = {1529-3785},
  doi = {10.1145/3584948},
  url = {https://fis.uni-bamberg.de/handle/uniba/90091},
  language = {eng}
}

@article{adler2022_90097,
  title = {An explicit construction of graphs of bounded degree that are far from being Hamiltonian},
  author = {Adler, Isolde and Köhler, Noleen},
  year = {2022},
  journal = {Discrete mathematics and theoretical computer science : DMTCS},
  volume = {24},
  number = {1},
  pages = {1-19},
  publisher = {LORIA},
  address = {Nancy},
  issn = {1365-8050},
  doi = {10.46298/dmtcs.7109},
  url = {https://fis.uni-bamberg.de/handle/uniba/90097},
  language = {eng},
  abstract = {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.},
  keywords = {Computer Science - Discrete Mathematics, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms,G.2.2}
}

@article{adler2022_90094,
  title = {Vapnik–Chervonenkis dimension and density on Johnson and Hamming graphs},
  author = {Adler, Isolde and Benediktsson, Bjarki Geir and Macpherson, Dugald},
  year = {2022},
  journal = {Discrete applied mathematics : the journal of combinatorial algorithms, informatics and computational sciences},
  volume = {312},
  pages = {29-44},
  publisher = {Elsevier},
  address = {Amsterdam},
  issn = {0166-218X},
  doi = {10.1016/j.dam.2021.09.017},
  url = {https://fis.uni-bamberg.de/handle/uniba/90094},
  language = {eng}
}

