WorksMathematics
A counterexample to the subgraphings approximate the cost problem
Abstract
We prove that for every , the free group on generators admits a finite generating set such that the Schreier graphing of the Bernoulli action of with respect to does not admit spanning subgraphings that would approximate the cost of the action. In particular, this gives an example of a graphing that spans a treeable countable pmp equivalence relation, but does not admit a spanning subtreeing.
Introduction
An important numerical invariant of probability measure preserving countable Borel equivalence relations (pmp CBERs), introduced by Levitt [17] and subsequently developed into a far-reaching theory by Gaboriau [9, 8] (see, e.g., [2, 7, 13, 16, 15, 22]), is the notion of cost. On a high-level, cost measures how difficult it is to realize a given pmp CBER as connectivity components of a measurable graph relation (also known as graphing) in terms of its average degree.
The main motivation for our work stems from problems about global behavior of cost. For instance, how difficult it is to compute a cost of a given pmp action, or is it possible to approximate the cost of a countable pmp equivalence relation induced by a graphing by erasing edges. In this paper, we describe an example that gives a negative answer to the latter problem, that we will refer to as the subgraphings approximate the cost problem, and that has been formally stated in [10 Subgraphings vs Cost Problem, Question 2.68] and [1 Question 46]. Before stating our main result, we formally introduce the main concepts.
A graphing on a standard probability space is a triplet , where is a locally countable Borel graph on that satisfies the mass transport principle with respect to , see [18 Chapter 18]. We write for the connectedness equivalence relation on induced by , it follows that is a pmp CBER. Given a pmp CBER on a standard probability space , we define to be the set of all graphings on such that up to -null sets. In the special case, when , we write simply instead of .
A prominent family of graphings are the so-called Schreier graphings of pmp actions: we say that an action of a countable group on a standard probability space is a probability measure preserving (pmp) action if for every measurable set and , where . Additionally, we say that the action is (almost everywhere) free if the stabilizer of -almost every point is trivial.
We denote by the orbit equivalence relation induced by , it follows that is a pmp CBER. We set .
For a free pmp action and a finite set , we define
to be the Schreier graphing of with respect to . For this definition, we do not require to be a generating set. Observe that generates if and only if .
For a graphing , we define its cost as
A cost of a pmp CBER is then defined as
and a cost of an action is defined as . Given a graphing , we define the subgraphing cost
Note that we always have , and the subgraphings approximate the cost problem asks whether we have equality for all graphings . If generate , then we write simply instead of .
The main focus of this paper is on the free group
that is freely generated by for . It follows from Gaboriau’s theorem about treeings [8 Théorème IV.1] that for any free pmp action . Our main result is the following.
Theorem 1. Let , be the Bernoulli action and . Then there is a finite set of generators of size such that
In particular, if , then .
Let be a pmp CBER on a standard probability space . We say that is treeable, if there is an acyclic graphing on such that holds almost everywhere. The following is a direct consequence of Theorem 1 and [8 Théorème IV.1].
Corollary 1. There exists a graphing such that is treeable and there is no that is an almost everywhere acyclic subgraphing of such that .
The following is a direct consequence of the case of Theorem 1 (see § 6).
Corollary 2. Assume that is a finitely generated group. Let , be the Bernoulli action and . Then there is a graphing such that
Remark 1. In contrast, recently Recke and the second author have shown [11 Theorem 1.5] that Schreier graphs of the Bernoulli actions of co-compact lattices in connected higher rank semisimple real Lie groups with property (T) have the sparse unique infinite cluster property for any finite set of generators. The same conclusion can be derived for Schreier graphs of the Bernoulli actions of products of free groups with at least two factors on the same number of generators , for , by a combination of [6 Theorem 1] and [11 Corollary 9.4]. It follows that the subgraphings approximate the cost problem has a positive answer for these Schreier graphings.
Another application concerns the so-called free uniform spanning forest (FUSF). Let be an infinite connected locally finite graph, and let be an increasing exhaustion of by finite sets such that each induced subgraph is connected. Let be the law of a uniformly chosen spanning tree of , viewed as a probability measure on by declaring all edges outside absent. The measures converge weakly to a probability measure on . This limit is independent of the exhaustion and is invariant under every automorphism of ; see [4 Section 5], and it is called the FUSF of .
Pete and Timár [21 Theorem 1.2] showed that connectivity of the FUSF can depend on the generating set. They constructed a virtually free group with two finite generating sets such that the FUSF of one Cayley graph is connected almost surely, whereas that of the other has infinitely many components almost surely. This answered negatively Question 10.50 of [19]. Combining our main result with the recent theorem that the FUSF is a factor of iid [20 Theorem 1.1], we obtain the analogous result for free groups.
Theorem 2. Let . Then there are two generating sets and of such that if we write for , then is connected almost surely and has infinitely many connectivity components almost surely.
Proof. Let be the standard generating set for . It follows that is concentrated on the standard Cayley graph of , hence it is connected almost surely.
Let be the generating set from Theorem 1 for . By [20 Theorem 1.1], is a -invariant factor of iid. Equivalently, it can be realized as a measurable acyclic subgraphing on the Bernoulli probability space. As , we have that as otherwise we have
by Gaboriau’s theorem [8 Théorème IV.1]. In particular, is disconnected with positive probability, hence almost surely as it is ergodic. Finally, by [12 Theorem 1.3], the FUSF of a Cayley graph is almost surely either connected or has infinitely many connected components. □
Outline of the proof of Theorem 1
We only focus on the case , as the general case follows directly from Corollary 2. Write . Given , the generating set is of the form for some reduced word with the following combinatorial properties: (A) large collections of prefixes of freely generate a free subgroup of (see, Lemma 3),
(B) for any fixed , if we consider the graph on with edge set
then any path from to in must pass through a -edge with the property that almost all (depending on ) of its prefixes that are followed by letter belong to (see, Lemma 2).
The word is constructed by a simple randomized process, namely, it is of the form
where the parameter as and are picked uniformly at random.
The above properties are used to derive a result that goes seemingly in the opposite direction than Theorem 1. To be more precise, we show that if is a measurable set such that
then as the parameter defining the length of goes to infinity (see, Theorem 4).
On a high-level, the argument uses (B) to gradually enlarge by “filling in” the small amount of missing -edges in selected -edges that eventually produces a positive fraction of -edges whose prefixes are completely contained in (see, Lemma 4). If were small, then this concentration of on a positive fraction of -edges would contradict an entropy inequality for a restriction of the Bernoulli action to a free subgroup of (see, § 4). Here, it is important that the rank of this free group goes to as , which is where (A) is used.
Finally, Theorem 1 is a direct corollary of Theorem 4. For example, a lower bound on the measure of -edges that are used in a spanning subgraphing can be drawn by taking a union with and replacing every -edge in by a -edge . This preserves connectedness, and the measure of -edges remains the same as the measure of -edges in . The lower bound is then derived from Theorem 4, see § 6. A similar argument can be applied to and .
AI Disclosure
An interesting candidate for a counterexample to the subgraphings approximate the cost problem was suggested by GPT-5.6 in August 2026, upon the authors’ inquiry about a construction related to the question of the complexity of finite cost (see § 7). While neither the authors nor GPT 5.6 were able to prove anything about the group, the newly released GPT 6 showed, interestingly, that the candidate either fails the fixed price conjecture or is a counterexample to the subgraphings approximate the cost problem. Then, upon seeing the new OpenAI counterexample to the fixed price conjecture we used extensively the LLM to find a group (it was ) that satisfies the above theorem. After several1 rounds of drastic simplifications of the arguments, it turned out that the same result is true for the free group, which is what we decided to include. LLM was not used in the actual writing of this text, only in corrections.
Acknowledgments:
We are very grateful to Márton Borbényi, Edward Hou, Gábor Pete for the conversations and suggestions on the topic of the paper.
JG was supported by an ERC CZ grant LL2608 funded by the Czech Ministry of Education, Youth and Sports from the ERC CZ Program. BB and VZ were supported by the ERC COG grant Define (No. 101231345). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency.
Positive words in F
As discussed in § 1.1, the generating set in Theorem 1 is always of the form for some reduced word ; now we describe how to construct them. We use a simple random construction ensuring that overlaps between the word and its translated copies are small. This implies, among other things, that there is a large collection of prefixes of that freely generate a free subgroup of .
Definition 1 (Positive words in ). Let and be positive integers. An -positive word is a word of the form
where for every , such that
(a) the collection
consists of pairwise distinct sequences, where the indices are always understood ,
(b) we have
Given , we write for the reduced word given by (1). We start by showing that a uniform sequence in defines a positive word with high probability. Throughout the paper we use the natural logarithm.
Lemma 1. Let and be positive integers such that , and endow with the uniform measure. Then
Proof. Let be sampled uniformly from and fix . The probability that is equal to . Indeed, we may without loss of generality assume that and
Then it follows that the choices of fully determine , where , as . The union bound gives
which gives an upper bound on the probability that (a) fails. To bound the probability of failure in (b), we apply Chebyshev’s inequality. Define the random variable and note that and . Then we have
and the claim follows. □
Let be an -positive word for some . Set and define
for every . For , let
The following is the main combinatorial observation. We state it for the left-shift action of on itself, but later we will apply it to the (orbits of the) Bernoulli shift of .
We fix some terminology that is used throughout. Recall that a path in a graph is an injective sequence of vertices, where consecutive vertices form an edge.
Lemma 2. Let and be positive integers, be an -positive word given by some , and . Define a graph on with an edge set
and suppose that is a path in . Then there are and such that
and
Proof. Let be the left Cayley graph of with respect to the generating set . We start with the following observation.
Claim 1. Let and suppose that
Then .
Proof. Let be minimal such that for some . By (1), we have that if is such that and for some , then and
By (5), there is such that . This can only happen, by (2), if . Consequently , which implies that as desired. □
We consider a quotient graph of that is obtained by gluing together vertices of the form for every and for . Formally, let be the set of equivalence classes of the equivalence relation on that is generated by the relation
For , we denote by the corresponding element in that contains . We define the edge relation as
and think of each edge to have a label of the form , where .
For , define to be an increasing enumeration of the set
We denote by the graph distance in .
Claim 2. The graph is acyclic, does not contain loops and the label of each edge is uniquely determined. Additionally, , where is a path in that connects and for every . In particular, for every .
Proof. The first assertion follows from the fact that is acyclic and is a quotient of with the property that the restriction of to each , for , is connected. The additional parts follow directly from these properties of and the definition. □
Given a path in , we define to be the reverse of , and if is another path in such that , then we define to be the shortest path from to . Note that is well defined by Claim 2, and that it can be equivalently defined as
where is maximal such that for every . In particular, .
Suppose for a contradiction that (4) does not hold for any . This is equivalent to either being 0 or at least for every . We prove that there is an such that
Once we have that, the proof is finished as contradicts the assumption that is a positive integer.
Define
and write for those indices such that . Set and note that for every . As , we have that . We show that setting works as required.
For , define to be the path in that connects and from Claim 2. Note that by our assumption, we have that .
For , define and set to be the shortest path in from to . Note that is uniquely determined by Claim 2.
We show by induction on , that (a) , (b) for .
Note that this will yield (7), and hence prove the lemma. If , then (a) and (b) follow as and holds for every . The inductive step is trivial if as and . Hence we are left with the case , where .
Claim 3. The largest initial segment on which and coincide has size at most .
Proof. Let and be consecutive vertices in both and . Set if and otherwise. Similarly, set if and otherwise.
By the uniqueness of the labels in , Claim 2, and the definition of and , there are indices and such that
Note that this implies that
for some . Indeed, otherwise we get the relation which is not satisfied in .
Suppose for a contradiction that the initial segment on which and coincide has size strictly more than . By the previous paragraph and the uniqueness of labels in , we conclude that
Hence, by Claim 1, we have . As is a path and , we must have , , and . This implies that and that is a contradiction. □
By the definition, we have , and by the inductive assumption (b), we have that the largest initial segment where and coincide has size at least . By Claim 3, we conclude that . The description of in (6) implies directly that the inductive assumptions (a) and (b) hold for , hence finishing the proof of Lemma 2. □
Next, we show that a sufficiently spaced collection of initial segments of an -positive word from freely generates a free group. Write , where . Set and for every . Define
Note that by (b), we have that .
Lemma 3. The elements of the set freely generate a free subgroup of .
Proof. Wlog, we may assume . Set , and for define
Observe that each contains at least occurrences of . We say that a letter is in the middle of the word if there are at least other letters to the left and to the right of it. We claim that freely generate a free group. Note that once we have that, the proof is done as they generate the same subgroup as the elements of that has the same size.
Let be a reduced word in the alphabet , where for every . Suppose for a contradiction that . Consider the cancellation process that turns into . There must be a first time in this process, when one of the letters in the middle of some of the words is canceled. Fix such an index . As it is the first time in the process, we may assume without loss of generality that the cancellation came from .
Note that we must have as otherwise no cancellation in occurs at all. This implies that , and condition (a) in the definition of an -positive word guarantees that at most letters in are canceled in .
Entropy inequality in free groups
Let and be a free group on generators. We state the entropy inequality (or equivalently the non-negativity of the -invariant) of Bowen [5], see also [3], for the Bernoulli shift . To that end, recall that the entropy of a random variable with values in a finite set is defined as
where we use the natural logarithm and set . Now suppose that is defined on , and set for every and . The entropy inequality then reads as follows:
where is the joint random variable of and .
Theorem 3. Let , be a free group on generators and be measurable sets such that and for every and . Then
Proof. Set and . We may assume that as the claim is trivial otherwise. Define the random variable with values in by
Observe that .
We claim that for each fixed , we have that
Indeed, write and for . As for every , we have
where in all of the sums, we only consider non-zero probabilities. By concavity of , we have that
for . Finally, as , we get from the same inequality that
as and by the definition. This gives (10).
Summing (10) for and using the entropy inequality (9), we conclude that
which is equivalent to
The claim follows by noting that as .
Relative cost of Sch() with respect to -edges
We deduce Theorem 1 from the following result, which concerns an opposite question. Namely, suppose that we commit to a graphing . How many -edges do we need to add to to produce an element of ?
The graphings that we consider are of the form , where is an -positive word. We show that for certain choices of the parameters and , the measure of the set of -edges that have to be added to turn into an element of goes to as .
Theorem 4. Let be the Bernoulli action , , and and be positive integers such that
Then for every -positive word we have that if
for some measurable sets , then for every .
We start with an application of Lemma 2 to the Bernoulli action. Recall the set from (8).
Lemma 4. Let , and be positive integers, be a -positive word and be a measurable subset of such that
and . Then there is a measurable set such that and
Proof. Let be a sequence of measurable subsets of such that (a) for every , we have , (b) for -almost every , we have .
Consider the following process that starts with and inductively creates a sequence of measurable sets for such that by the following rule. If is such that
then we add and for every to . Note that
for every by (a).
Set . Observe that for each , we have
Indeed, define a map that sends to some such that
and
This can be done by using the Lusin-Novikov uniformization theorem. The claim follows from the fact that such a map is at most -to-1, and its range falls into . Consequently, we obtain that
holds for every .
We claim that . Let be in the free part and such that there is a path , where and , in
from to . We claim that , where . Indeed, suppose for a contradiction that . As is also a path in that connects and , we have that there is such that
by Lemma 2. Let be such that and
Such an index exists by (b) and the fact that . This is a contradiction as by construction.
By the previous paragraph, there is a maximal index such that . Set . By (12), we have
which yields, when combined with (13),
as desired. □
Before turning to the proof of Theorem 4 let us make an easy, folklore observation.
Lemma 5. Let be countable groups, be the Bernoulli action , and be the action obtained by restricting to . Then is isomorphic to the Bernoulli action of .
Proof. Choose a collection of right coset representatives of . The map defined by
is a -equivariant measure preserving bijection. Since is a non-atomic standard measure space, it is isomorphic modulo null sets to . Applying this isomorphism in each -coordinate gives the desired isomorphism. □
Proof of Theorem 4. Let and be positive integers that satisfy
and be a -positive word. Suppose that there are measurable sets such that
We show that for .
We only handle the case , as is completely analogous. Suppose for a contradiction that . By Lemma 4, there are measurable sets and such that , and for every and .
Write for the free group that is freely generated by . As is a subgroup of , we may consider the restriction of to , that we denote as . It follows from Lemma 5 that is isomorphic to the Bernoulli shift and satisfy the assumptions of Theorem 3 with . Consequently, . Finally, note that
where the first inequality is by the definition in (8) and the second inequality follows from the assumption (11). This gives the claim. □
Proof of Theorem 1
In this section we prove our main result.
Proof of Theorem 1. The claim is trivial for as , so we may assume that . Let and be positive integers such that
By Lemma 1, there is such that is an -positive word and is an -positive word. Indeed, the probability that is an -positive word and is an -positive word is at least as . Observe that both and satisfy the assumptions of Theorem 4 for . We show that setting and works as required.
The fact that generates is clear. Let be such that . Set
Define and observe that
Indeed, we have that
is a path in for every . By Theorem 4 and the fact that , we conclude that .
Similarly, define . We claim that
Indeed, we have that
is a path in for every . By Theorem 4 and the fact that , we conclude that .
Finally, define , and observe that
By Theorem 4, we conclude that . Consequently, we have that
As was arbitrary, we get that as desired.
Finally, let us deduce Corollary 2.
Proof of Corollary 2. Let be the cost of the equivalence relation given by restricting to the action and let be any of its spanning subgraphings. Note that by free-product additivity (see, [8]) . Define , where is the graphing provided by Theorem 1 with . Then, since we used a free product, any spanning subgraphing of must span a.e. and component internally. In particular, using Lemma 5 and our main theorem, its cost is at least .
Open problems
Let us reiterate the question from Kechris-Miller [14] about the complexity of cost, which was the original motivation behind this paper.
Problem 1. Is there a Borel family of pmp CBERs such that the set is analytic complete?
The results of this paper and Remark 1 motivate the following problem.
Problem 2. Characterize the countable groups , for which the subgraphings approximate cost problem has a positive answer. What if we only consider Schreier graphings of the Bernoulli action?
Note that the answer is positive when is amenable: indeed, then its actions are measure hyperfinite. From a hyperfinite decomposition of a graphing one can define a spanning subtreeing of , which in turn must realize the cost of the equivalence relation.
Eötvös Loránd University, Institute of Mathematics, Pázmány Péter stny. 1/C, 1117 Budapest, Hungary
Email address: [email protected]
Charles University, Computer Science Institute, Malostranské nám. 25 118 00 Praha 1, Czechia
Email address: [email protected]
Eötvös Loránd University, Institute of Mathematics, Pázmány Péter stny. 1/C, 1117 Budapest, Hungary
Email address: [email protected]
References
- [1]Miklós Abért. Some questions. https://www.renyi.hu/~abert/research/questions.pdf, 2010. Problem list, November 2, 2010.
- [2]Miklós Abért and Nikolay Nikolov. Rank gradient, cost of groups and the rank versus Heegaard genus problem. Journal of the European Mathematical Society, 14(5):1657–1677, 2012.arxiv.org/abs/math/0701361
- [3]Ágnes Backhausz and Balázs Szegedy. On large-girth regular graphs and random processes on trees. Random Structures & Algorithms, 53(3):389–416, 2018.
- [4]Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm. Uniform spanning forests. The Annals of Probability, 29(1):1–65, 2001.DOI
- [5]Lewis Bowen. The ergodic theory of free group actions: entropy and the f-invariant. Groups, Geometry, and Dynamics, 4(3):419–432, 2010.arxiv.org/abs/0902.0174
- [6]Matteo D’Achille, Jan Grebík, Ali Khezeli, Konstantin Recke, and Amanda Wilkens. Vanishing uniqueness thresholds in Voronoi percolation on products. arXiv:2511.23317, 2025.arxiv.org/abs/2511.23317
- [7]Mikołaj Frączyk, Sam Mellick, and Amanda Wilkens. Poisson-voronoi tessellations and fixed price in higher rank. to appear Ann. of Math., 2026.
- [8]Damien Gaboriau. Coût des relations d’équivalence et des groupes. Invent. Math., 139(1):41–98, 2000.DOI
- [9]Damien Gaboriau. Orbit equivalence and measured group theory. Proceedings of the International Congress of Mathematicians Hyderabad, 2010.arxiv.org/abs/1009.0132
- [10]Damien Gaboriau. Around the orbit equivalence theory, measure equivalence, cost and ℓ² Betti numbers. https://perso.ens-lyon.fr/gaboriau/Travaux-Publi/ME-Cost-L2-Lectures/ME-Cost-L2-Lectures.pdf, 2025. Lecture notes, version of October 3, 2025.
- [11]Jan Grebík and Konstantin Recke. Poisson-Voronoi percolation in higher rank. arXiv:2504.02435, 2025.arxiv.org/abs/2504.02435
- [12]Tom Hutchcroft and Asaf Nachmias. Indistinguishability of trees in uniform spanning forests. Probability Theory and Related Fields, 168(1–2):113–152, 2017.
- [13]Tom Hutchcroft and Gábor Pete. Kazhdan groups have cost 1. Inventiones mathematicae, 221:873–891, 2020.arxiv.org/abs/1810.11015
- [14]Alexander S. Kechris and Benjamin D. Miller. Topics in Orbit Equivalence, volume 1852 of Lecture Notes in Mathematics. Springer Berlin, Heidelberg, 2004.
- [15]Ali Khezeli. Products of infinite countable groups have fixed price one. arXiv preprint arXiv:2509.08325, 2025.arxiv.org/abs/2509.08325
- [16]François Le Maître. The number of topological generators for full groups of ergodic equivalence relations. Inventiones mathematicae, 198(2):261–268, 2014.DOI
- [17]Gilbert Levitt. On the cost of generating an equivalence relation. Ergodic Theory Dynam. Systems, 15(6):1173–1181, 1995.DOI
- [18]László Lovász. Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012.
- [19]Russell Lyons and Yuval Peres. Probability on Trees and Networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016.
- [20]OpenAI. The free uniform spanning forest is a factor of IID. OpenAI Math Release preprint OAI:The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026, 2026.
- [21]Gábor Pete and Ádám Timár. The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set. The Annals of Probability, 50(6):2218–2243, 2022.arxiv.org/abs/2006.06387
- [22]Raz Slutsky. A product-neighbourhood criterion for fixed price one. arXiv preprint arXiv:2607.20273, 2026.arxiv.org/abs/2607.20273