BBBertalan Bodor

Bertalan Bodor

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Symmetries of graphs and structures that fail to interpret a finite thing

    by Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker

    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

    STRUCTURES WITH NOT TOO FAST UNLABELLED GROWTH

    by Bertalan Bodor

    Let S $\mathscr {S}$ script upper S be the class of all structures whose growth rate on orbits of subsets of size n $n$ n is not faster than 2 n p ( n ) $\frac {2^n}{p(n)}$ StartFraction 2 Superscript n Baseline Over p left parenthesis n right parenthesis EndFraction for any polynomial p $p$ p . In this article we give a complete classification of all structures in S $\mathscr {S}$ script upper S in terms of their automorphism groups. As a consequence of our classification we show that S $\mathscr {S}$ script upper S has only countably many structures up to bidefinability, all these structures are first-order interpretable in ( Q ; < ) $(\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 S $\mathscr {S}$ script upper S have finitely many first-order reduct up to interdefinability, thereby confirming Thomas’ conjecture for the class S $\mathscr {S}$ script upper S .

  • Taylor is prime

    by Bertalan Bodor, Gergő Gyenizse, Miklós Maróti, László Zádori

    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

    A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory

    by Manuel Bodirsky, Bertalan Bodor

    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

    by Manuel Bodirsky, Bertalan Bodor

    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

    CLASSIFICATION OF $\omega $ -CATEGORICAL MONADICALLY STABLE STRUCTURES

    by Bertalan Bodor

    A 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}$ .