Some Questions — Question 46

Definitions and mathematical statement

Let $R$ be a countable probability-measure-preserving Borel equivalence relation on a standard atomless probability space $(X,\mu)$. A graphing $\Phi=(\phi_i:A_i\to B_i)_{i\geq1}$ consists of measure-preserving partial Borel bijections with graphs in $R$, such that finite compositions of the maps and their inverses generate $R$ almost everywhere. Define \[ c(\Phi)=\sum_i\mu(A_i),\qquad \operatorname{cost}(R)=\inf_{\Psi\text{ generating }R}c(\Psi). \] Assume this infimum is finite, which is the nonvacuous approximation case.

Given an arbitrary graphing $\Phi$ of $R$ and a number $\varepsilon>0$, must there be measurable subsets $A_i'\subseteq A_i$ such that the restrictions $\phi_i|_{A_i'}$ still generate $R$ almost everywhere and \[ \sum_i\mu(A_i')\leq\operatorname{cost}(R)+\varepsilon? \] This is the subgraphing convention: one may discard portions or all of the existing partial bijections, but may not introduce new edges joining formerly nonadjacent points. If cost is expressed as half the integral of vertex degree, the same deletion interpretation applies to an undirected graphing without duplicated edges.

The infimum defining cost allows completely different generating graphings. The problem asks whether it can be approached inside each already supplied graphing. Merely exhibiting some inexpensive graphing therefore does not answer the question. Exact attainment is not required, and the retained subsets may depend on $\varepsilon$. Preserving the generated equivalence relation, rather than only keeping a subrelation, is essential.

Short English statement

Can every generating graphing be reduced, by deleting edges only, to one whose cost is arbitrarily close to the cost of its relation?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 1200046 (AMR-011-0046), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Abert - Some questions (pdf) (2010), Question 46. Original source indexed by AMR-011-0046. https://www.renyi.hu/~abert/questions.pdf.