Bertalan Bodor
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Bertalan Bodor has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Manuel Bodirsky
Institut für Algebra, TU Dresden, Dresden, Germany
2 shared publications - Antoine Mottet
Hamburg University of Technology, Am Schwarzenberg-Campus 1, 21073 Harburg, Germany
1 shared publication - Gergő Gyenizse
University of Szeged
1 shared publication - Libor Barto
Charles University, Faculty of Mathematics and Physics, Ke Karlovu 3, 121 16 Praha 2 Czech Republic
1 shared publication - László Zádori
University of Szeged
1 shared publication - Marcin Kozik
Jagiellonian University, Gołębia 24, 31-007 Kraków, Poland
1 shared publication
Latest Publications
- 29 October 2026
- Published by World Scientific Pub Co Pte Ltd in Journal of Mathematical Logic
Symmetries of graphs and structures that fail to interpret a finite thing
In this paper, we investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters or orbits, every finite structure. Our results generalize several theorems from the literature and yield further algebraic invariance properties that must be satisfied in every such graph. Algebraic properties of this kind are tightly connected to the tractability of constraint satisfaction problems, and we obtain new such properties even for infinite countably categorical graphs. We balance these positive results by showing the existence of a countably categorical hypergraph that fails to interpret some finite structure, while still lacking some of the most essential algebraic invariance properties known to hold for finite structures.
- 29 October 2026
- Published by World Scientific Pub Co Pte Ltd in Journal of Mathematical Logic
Symmetries of graphs and structures that fail to interpret a finite thing
In this paper, we investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters or orbits, every finite structure. Our results generalize several theorems from the literature and yield further algebraic invariance properties that must be satisfied in every such graph. Algebraic properties of this kind are tightly connected to the tractability of constraint satisfaction problems, and we obtain new such properties even for infinite countably categorical graphs. We balance these positive results by showing the existence of a countably categorical hypergraph that fails to interpret some finite structure, while still lacking some of the most essential algebraic invariance properties known to hold for finite structures.
- Open Access
- 31 July 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-52
STRUCTURES WITH NOT TOO FAST UNLABELLED GROWTH
Let $\mathscr {S}$ script upper S be the class of all structures whose growth rate on orbits of subsets of size $n$ n is not faster than $\frac {2^n}{p(n)}$ StartFraction 2 Superscript n Baseline Over p left parenthesis n right parenthesis EndFraction for any polynomial $p$ p . In this article we give a complete classification of all structures in $\mathscr {S}$ script upper S in terms of their automorphism groups. As a consequence of our classification we show that $\mathscr {S}$ script upper S has only countably many structures up to bidefinability, all these structures are first-order interpretable in $(\mathbb {Q};<)$ left parenthesis double struck upper Q semicolon less than right parenthesis and they are interdefinable with a finitely bounded homogeneous structure. Furthermore, we also show that all structures in $\mathscr {S}$ script upper S have finitely many first-order reduct up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathscr {S}$ script upper S .- 31 July 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-52
Open AccessSTRUCTURES WITH NOT TOO FAST UNLABELLED GROWTH
Let $\mathscr {S}$ script upper S be the class of all structures whose growth rate on orbits of subsets of size $n$ n is not faster than $\frac {2^n}{p(n)}$ StartFraction 2 Superscript n Baseline Over p left parenthesis n right parenthesis EndFraction for any polynomial $p$ p . In this article we give a complete classification of all structures in $\mathscr {S}$ script upper S in terms of their automorphism groups. As a consequence of our classification we show that $\mathscr {S}$ script upper S has only countably many structures up to bidefinability, all these structures are first-order interpretable in $(\mathbb {Q};<)$ left parenthesis double struck upper Q semicolon less than right parenthesis and they are interdefinable with a finitely bounded homogeneous structure. Furthermore, we also show that all structures in $\mathscr {S}$ script upper S have finitely many first-order reduct up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathscr {S}$ script upper S . - 19 July 2024
- Published by World Scientific Pub Co Pte Ltd in International Journal of Algebra and Computation
- Vol. 34 (06) , 857-879
Taylor is prime
We study the Taylor varieties and obtain new characterizations of them via compatible reflexive digraphs. Based on our findings, we prove that in the lattice of interpretability types of varieties, the filter of the types of all Taylor varieties is prime.
- 19 July 2024
- Published by World Scientific Pub Co Pte Ltd in International Journal of Algebra and Computation
- Vol. 34 (06) , 857-879
Taylor is prime
We study the Taylor varieties and obtain new characterizations of them via compatible reflexive digraphs. Based on our findings, we prove that in the lattice of interpretability types of varieties, the filter of the types of all Taylor varieties is prime.
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 16 (2) , 1-39
A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Constraint satisfaction problems (CSPs) for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complexity dichotomy, P versus NP-complete. A powerful method to obtain polynomial-time tractability results for such CSPs is a certain reduction to polynomial-time tractable finite-domain CSPs defined over k -types, for a sufficiently large k . We give sufficient conditions when this method can be applied and apply these conditions to obtain a new complexity dichotomy for CSPs of first-order expansions of the basic relations of the well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion.
- 10 June 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 16 (2) , 1-39
Open AccessA Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Constraint satisfaction problems (CSPs) for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complexity dichotomy, P versus NP-complete. A powerful method to obtain polynomial-time tractability results for such CSPs is a certain reduction to polynomial-time tractable finite-domain CSPs defined over k -types, for a sufficiently large k . We give sufficient conditions when this method can be applied and apply these conditions to obtain a new complexity dichotomy for CSPs of first-order expansions of the basic relations of the well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion.
- Open Access
A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Constraint satisfaction problems (CSPs) for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complexity dichotomy, P versus NP-complete. A powerful method to obtain polynomial-time tractability results for such CSPs is a certain reduction to polynomial-time tractable finite-domain CSPs defined over k-types, for a sufficiently large k. We give sufficient conditions when this method can be applied and illustrate how to use the general results to prove a new complexity dichotomy for first-order expansions of the basic relations of the well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion.
Open AccessA Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Constraint satisfaction problems (CSPs) for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complexity dichotomy, P versus NP-complete. A powerful method to obtain polynomial-time tractability results for such CSPs is a certain reduction to polynomial-time tractable finite-domain CSPs defined over k-types, for a sufficiently large k. We give sufficient conditions when this method can be applied and illustrate how to use the general results to prove a new complexity dichotomy for first-order expansions of the basic relations of the well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion.
- Open Access
- 19 September 2023
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 89 (2) , 460-495
CLASSIFICATION OF $\omega $ -CATEGORICAL MONADICALLY STABLE STRUCTURESA first-order structure $\mathfrak {A}$ is called monadically stable iff every expansion of $\mathfrak {A}$ by unary predicates is stable. In this paper we give a classification of the class $\mathcal {M}$ of $\omega $ -categorical monadically stable structure in terms of their automorphism groups. We prove in turn that $\mathcal {M}$ is the smallest class of structures which contains the one-element pure set, is closed under isomorphisms, and is closed under taking finite disjoint unions, infinite copies, and finite index first-order reducts. Using our classification we show that every structure in $\mathcal {M}$ is first-order interdefinable with a finitely bounded homogeneous structure. We also prove that every structure in $\mathcal {M}$ has finitely many reducts up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathcal {M}$ .- 19 September 2023
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 89 (2) , 460-495
Open AccessCLASSIFICATION OF $\omega $ -CATEGORICAL MONADICALLY STABLE STRUCTURESA first-order structure $\mathfrak {A}$ is called monadically stable iff every expansion of $\mathfrak {A}$ by unary predicates is stable. In this paper we give a classification of the class $\mathcal {M}$ of $\omega $ -categorical monadically stable structure in terms of their automorphism groups. We prove in turn that $\mathcal {M}$ is the smallest class of structures which contains the one-element pure set, is closed under isomorphisms, and is closed under taking finite disjoint unions, infinite copies, and finite index first-order reducts. Using our classification we show that every structure in $\mathcal {M}$ is first-order interdefinable with a finitely bounded homogeneous structure. We also prove that every structure in $\mathcal {M}$ has finitely many reducts up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathcal {M}$ .