PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

On definable matchings in o-minimal bipartite graphs

Volume 264 / 2024

Jana Maříková Fundamenta Mathematicae 264 (2024), 85-102 MSC: Primary 03C64; Secondary 05C63 DOI: 10.4064/fm230801-12-12 Published online: 12 February 2024


We consider bipartite graphs definable in o-minimal structures, in which the edge relation $G$ is a finite union of graphs of certain measure-preserving maps.

We establish the existence of definable matchings with few short augmenting paths. Under the additional assumptions of $G\subseteq [0,1]^n$ and 2-regularity, this yields the existence of definable matchings covering all vertices outside of a set of arbitrarily small positive measure (Lebesgue measure of the standard part). As an application we obtain an approximate 2-cancellation result for the semigroup of definable subsets of $[0,1]^n$ modulo an equivalence relation induced by measure-preserving maps.


  • Jana MaříkováKurt Gödel Research Center for Mathematical Logic
    Universität Wien
    1090 Wien, Austria

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image