AnnalsofMathematics00(XXXX),1–40 http://dx.doi.org/10.4007/annals.XXXX.00.0.0000 Measurable circle squaring By L(cid:32) ukasz Grabowski, Andra´s Ma´the´, and Oleg Pikhurko 6 1 0 Abstract 2 p LaczkovichprovedthatifboundedsubsetsAandBofRkhavethesame e non-zero Lebesgue measure and the upper box dimension of the boundary S of each set is less than k, then there is a partition of A into finitely many 2 parts that can be translated to form a partition of B. Here we show that it can be additionally required that each part is both Baire and Lebesgue ] G measurable. As special cases, this gives measurable and translation-only M versions of Tarski’s circle squaring and Hilbert’s third problem. . h t a m 1. Introduction [ We call two sets A,B ⊆ Rk equidecomposable and denote this as A ∼ B 4 v if there are a partition A = A1 ∪ ... ∪ An (into finitely many parts) and 2 isometriesγ ,...,γ ofRk such that theimages of the parts γ (A ),...,γ (A ) 1 n 1 1 n n 2 partition B. In other words, we can cut A into finitely many pieces and 1 6 rearrange them to form the set B. When this can be done is a very basic 0 question that one can ask about two sets and, as Dubins, Hirsch, and Karush . 1 [6, Page 239] write, “variants of the problems studied here already occur in 0 Euclid”. We refer the reader to various surveys and expositions of this area 5 1 ([8, 9, 11, 19, 20, 21, 39]) as well as the excellent book by Tomkowicz and : v Wagon [38]. i X The version that is closest to our everyday intuition (e.g. via puzzles like r “Tangram”, “Pentomino”, or “Eternity”) is perhaps the dissection congruence a inR2 wherethepieceshavetobepolygonalandtheirboundarycanbeignored when taking partitions. A well-known example from elementary mathematics is finding the area of a triangle by dissecting it into a rectangle. In fact, as L(cid:32).G.waspartiallysupportedbyEPSRCgrantEP/K012045/1andbyFondationsSciences Math´ematiques de Paris during the programme Marches Al´eatoires et G´eom´etrie Asympto- tique des Groupes atInstitutHenri-Poincar´e. A.M.waspartiallysupportedbyaLevehulme Trust Early Career Fellowship and by the Hungarian National Research, Development and InnovationOffice–NKFIH,104178. O.P.waspartiallysupportedbyERCgrant306493and EPSRC grant EP/K012045/1. 1 2 L(cid:32).GRABOWSKI,A.MA´THE´,andO.PIKHURKO it was discovered around 1832 independently by Bolyai and Gerwien, any two polygons of the same area are congruent by dissections. (Apparently, Wallace provedthisresultalreadyin1807; see[38, Pages34–35]forahistoricalaccount and further references.) The equidecomposition problem for polygons is also completely resolved: a result of Tarski [34] (see e.g. [38, Theorem 3.9]) gives that any two polygons of the same area are equidecomposable. Banach and Tarski [3] proved that, in dimensions 3 or higher, any two bounded sets with non-empty interior are equidecomposable; in particular, we get the famous Banach-Tarski Paradox that a ball can be doubled. On the otherhand,asitwasalsoshownin[3]byusingtheearlierresultsofBanach[2], a ball in Rk cannot be doubled for k = 1,2. This prompted von Neumann [27] toinvestigatewhat makes thecasesk = 1,2 differentusing thegroup-theoretic point of view, which started the study of amenable groups. Around that time, Tarski [35] asked if the disk and square in R2 of the sameareaareequidecomposable,whichbecameknownasTarski’s circle squar- ing. Von Neumann [27] showed that circle squaring is possible if arbitrary measure-preserving affine transformations are allowed. On the other hand, some negative evidence was provided by Dubins, Hirsch, and Karush [6] who showed that a circle and a square are not scissor congruent (when the pieces arerestrictedtobetopologicaldisksandtheirboundarycanbeignored)andby Gardner[7]whoprovedthatcircle-squaringisimpossibleifweusealocallydis- cretesubgroupofisometriesofR2. However, thedeeppaperofLaczkovich[15] showed that the answer to Tarski’s question is affirmative. In fact, his main result(comingfromthepapers[15,16,17])ismuchmoregeneralandstronger. In order to state it, we need some definitions. We call two sets A,B ⊆ Rk equivalent (and denote this by A ∼Tr B) if they are equidecomposable using translations, that is, there are partitions A = A ∪...∪A andB = B ∪...∪B ,andvectorsv ,...,v ∈ Rk suchthat 1 m 1 m 1 m B = A +v for each i ∈ {1,...,m}. Let λ = λ denote the Lebesgue measure i i i k on Rk. The box (or grid, or upper Minkowski) dimension of X ⊆ Rk is Ä ä logλ {x ∈ Rk : dist(x,X) (cid:54) ε} dim(cid:50)(X) := k−liminf , ε→0+ logε wheredist(x,X)meanse.g.theL∞-distancefromthepointxtothesetX. Let ∂X denote the topological boundary of X. It is easy to show that if A ⊆ Rk satisfies dim(cid:50)(∂A) < k, then A is Lebesgue measurable and, furthermore, λ(A) > 0 if and only if A has non-empty interior. With these observations, the result of Laczkovich can be formulated as follows. Theorem 1.1 (Laczkovich [15, 16, 17]). Let k (cid:62) 1 and let A,B ⊆ Rk be bounded sets with non-empty interior such that λ(A) = λ(B), dim(cid:50)(∂A) < k, and dim(cid:50)(∂B) < k. Then A and B are equivalent. MEASURABLE CIRCLE SQUARING 3 Theorem 1.1 applies to circle squaring since the boundary of each of these setshasboxdimension 1. Asnoted in[16], theinequalitydim(cid:50)(∂A) < k holds if A ⊆ Rk is a convex bounded set or if A ⊆ R2 has connected boundary of finite linear measure; thus Theorem 1.1 applies to such sets as well. Notethattheconditionthatλ(A) = λ(B)isnecessaryinTheorem1.1. In- deed, thegroupoftranslationsofRk isamenable(sinceitisanAbeliangroup) and therefore the Lebesgue measure on Rk can be extended to a translation- invariantfinitelyadditivemeasuredefinedonallsubsets(andsoequivalentsets which are measurable must necessarily have the same measure); see e.g. [38, Chapter 12] for a detailed discussion. Laczkovich [18] showed that one cannot replace the box dimension with the Hausdorff dimension in Theorem 1.1; see also [22] for further examples of non-equivalent sets. The proof of Theorem 1.1 by Laczkovich directly relies on the Axiom of Choice in a crucial way. Thus the pieces that he obtains need not be mea- surable. Laczkovich [15, Section 10] writes: “The problem whether or not the circle can be squared with measurable pieces seems to be the most interesting.” This problem remained open until now, although some modifications of it were resolved. Henle and Wagon (see [38, Theorem 9.3]) showed that, for any ε > 0, one can square a circle with Borel pieces if one is allowed to use similarities of the plane with scaling factor between 1−ε and 1+ε. Pieces can be made even more regular if some larger class of maps can be used (such as arbitrarysimilaritiesoraffinemaps), seee.g.[11,31,32,33]. Also, ifcountably many pieces are allowed, then a simple measure exhaustion argument shows that, up to a nullset, one can square a circle with measurable pieces (see [3, Theorem 41] or [38, Theorem 11.26]); the error nullset can be then eliminated by e.g. applying Theorem 1.1. Theauthorsofthispaperprovein[10]thateverytwoboundedmeasurable sets A,B ⊆ Rk, k (cid:62) 3, with non-empty interior and of the same measure are equidecomposable with Lebesgue measurable pieces. In particular, this gives a measurable version of Hilbert’s third problem (as asked by Wagon [40, Ques- tion 3.14]): one can split a regular tetrahedron into finitely many measurable pieces and rearrange them into a cube. These results rely on the spectral gap property of the natural action of SO(k) on the (k−1)-dimensional sphere in Rk for k (cid:62) 3 and do not apply when k (cid:54) 2. Also, the equidecompositions obtained in [10] cannot be confined to use translations only. Herewefillapartofthisgap. Namely,ourmainmainresult(Theorem1.2) shows that it can be additionally required in Theorem 1.1 that all pieces are Lebesgue measurable. In fact, Theorem 1.2 gives pieces that are also Baire measurable (or Baire for short), that is, each one is the symmetric difference of a Borel set and a meagre set. The study of equidecompositions with Baire sets was largely 4 L(cid:32).GRABOWSKI,A.MA´THE´,andO.PIKHURKO motivatedbyMarczewski’s problem from1930whetherRk admitsanon-trivial isometry-invariant finitely additive Borel measure that vanishes on bounded meagre sets. It is not hard to show that the answer is positive for k (cid:54) 2, see e.g.[38,Corollary13.3]. However,theproblemfork (cid:62) 3remainedopenforover 60 years until it was resolved in the negative by Dougherty and Foreman [4, 5] who proved in particular that any two bounded Baire sets A,B ⊆ Rk with non-empty interior are equidecomposable with Baire measurable pieces (and thus a ball can be doubled with Baire pieces). A short and elegant proof of a more general result was recently given by Marks and Unger [26] (see also [12]). However, as noted in [26, Page 406], the problem whether circle squaring is possible with Baire measurable parts remained open. Also, the results in [4, 5, 26] do not apply to the translation equidecomposability ∼Tr, even in higher dimensions. Here we resolve these questions in the affirmative, under the assumptions of Theorem 1.1: Theorem 1.2. Let k (cid:62) 1 and let A,B ⊆ Rk be bounded sets with non- empty interior such that λ(A) = λ(B), dim(cid:50)(∂A) < k, and dim(cid:50)(∂B) < k. Then A T∼r B with parts that are both Baire and Lebesgue measurable. In addition to implying measurable translation-only versions of Tarski’s circlesquaring,Hilbert’sthirdproblem,andWallace-Bolyai-Gerwien’stheorem (a question of Laczkovich [15, Page 114]), Theorem 1.2 also disproves the following conjecture of Gardner [8, Conjecture 5] for all k (cid:62) 2. Conjecture 1.3. Let P be a polytope and K a convex body in Rk. If P and K are equidecomposable with Lebesgue measurable pieces under the isome- tries from an amenable group, then P and K are equidecomposable with convex pieces under the same isometries. Indeed, for example, let P be a cube and K be a ball of the same volume. It is not hard to show directly that K and P are not equidecomposable with convex pieces, even under the groups of all isometries of Rk for k (cid:62) 2. Since Theorem 1.2 uses only translations (that form an amenable group), Conjec- ture 1.3 is false. This paper is organised as follows. In Section 2 we reduce the problem to the torus Tk := Rk/Zk and state a sufficient condition for measurable equiva- lenceinTheorem2.2. WealsodescribetherehowTheorem1.2canbededuced from Theorem 2.2, using some results of Laczkovich [16]. The main bulk of this paper consists of the proof of Theorem 2.2 in Sections 4 and 5. These sections are dedicated to respectively Lebesgue and Baire measurability (while some common definitions and auxiliary results are collected in Section 3). We organised the presentation so that Sections 4 and 5 can essentially be read independently of each other. Section 6 contains some concluding remarks. MEASURABLE CIRCLE SQUARING 5 In order to avoid ambiguities, a closed (resp. half-open) interval will al- ways mean an interval of integers (resp. reals); thus, for example, [m,n] := {m,m+1,...,n} ⊆ Z while [a,b) := {x ∈ R : a (cid:54) x < b}. Also, we denote [n] := {1,...,n} and N := {0,1,2,...}. 2. Sufficient condition for measurable equivalence The k-dimensional torus Tk is the quotient of the Abelian group (Rk,+) by the subgroup (Zk,+). We identify Tk with the real cube [0,1)k, endowed with the addition of vectors modulo 1. ByscalingtheboundedsetsA,B ⊆ Rk bythesamefactorandtranslating them, we can assume that they are subsets of [0,1)k. Note that if A,B ⊆ [0,1)k are (measurably) equivalent with translations taken modulo 1, then they are (measurably) equivalent in Rk as well using at most 2k times as many translations. (In fact, if each of A,B has diameter less than 1/2 with respect totheL∞-distance, thenwedonotneedtoincreasethenumberoftranslations at all.) So we work inside the torus from now on. Supposethatwehavefixedsomevectorsx ,...,x ∈ Tk thatarefree,that 1 d is,nonon-trivialintegercombinationofthemisthezeroelementof(Tk,+)(or, equivalently, x ,...,x ,e ,...,e , when viewed as vectors in Rk, are linearly 1 d 1 k independent over the rationals, where e ,...,e are the standard basis vectors 1 k of Rk). When reading the following definitions (many of which implicitly depend on x ,...,x ), the reader is advised to keep in mind the following connection 1 d to Theorems 1.1 and 1.2: we fix some large integer M and try to establish the equivalence A ∼Tr B by translating only by vectors from the set ¶ © (1) V := n x + ... +n x : n ∈ Zd, (cid:107)n(cid:107) (cid:54) M . M 1 1 d d ∞ Thus, if we are successful, then the total number of pieces is at most |V | = M (2M +1)d. By a coset of u ∈ Tk we will mean the coset taken with respect to the subgroup of (Tk,+) generated by x ,...,x , that is, the set {u+(cid:80)d n x : 1 d j=1 j j n ∈ Zd} ⊆ Tk. For X ⊆ Tk, we define ¶ © X := n ∈ Zd : u+n x + ... +n x ∈ X . u 1 1 d d Informally speaking, X ⊆ Zd records which elements of the coset of u ∈ Tk u are in X. If, for every u ∈ Tk, we have a bijection M : A → B such that u u u (2) (cid:107)M (n)−n(cid:107) (cid:54) M, for all n ∈ A , u ∞ u then Theorem 1.1 follows. Indeed, using the Axiom of Choice select a set U ⊆ Tk that intersects each coset in precisely one element. Now, each a ∈ A 6 L(cid:32).GRABOWSKI,A.MA´THE´,andO.PIKHURKO can be uniquely written as u + (cid:80)d n x with u ∈ U and n ∈ Zd; if we j=1 j j assign a to the piece which is translated by the vector (cid:80)d (m −n )x where j=1 j j j m := M (n), then we get the desired equivalence A ∼Tr B. This reduction u was used by Laczkovich [15, 16, 17]; of course, the main challenge he faced was establishing the existence of the bijections M as in (2). Here, in order u to prove Theorem 1.2, we will additionally need that the family (M ) is u u∈Tk consistent for different choices of u and gives measurable parts. By an n-cube Q ⊆ Zd we mean the product of d intervals in Z of size n, i.e.Q = (cid:81)d [n ,n +n−1]forsome(n ,...,n ) ∈ Zd. Ifnisanintegerpower j=1 j j 1 d of 2, we will call the cube Q binary. Given a function Φ : {2i : i ∈ N} → R and a real δ (cid:62) 0, a set X ⊆ Zd is called Φ-uniform (of density δ) if, for every i ∈ N and 2i-cube Q ⊆ Zd, we have that (cid:12) (cid:12) (3) (cid:12)|X ∩Q|−δ|Q|(cid:12) (cid:54) Φ(2i). (cid:12) (cid:12) In other words, this definition says that the discrepancy with respect to binary cubes between the counting measure of X and the measure of constant density δ is upper bounded by Φ. A set Y ⊆ Tk is called Φ-uniform (of density δ with respect to x ,...,x ) if Y is Φ-uniform of density δ for every u ∈ Tk. 1 d u These notions are of interest to us because of the following sufficient condition for A ∼Tr B that directly follows from Theorems 1.1 and 1.2 in Laczkovich [17]. Theorem 2.1 (Laczkovich [17]). Let k,d (cid:62) 1 be integers, let δ > 0, let x ,...,x ∈ Tk be free, let a function Φ : {2i : i ∈ N} → R satisfy 1 d (cid:88)∞ Φ(2i) (4) < ∞, 2(d−1)i i=0 and let sets A,B ⊆ Tk be Φ-uniform of density δ with respect to x ,...,x . 1 d ThenA T∼r B, usingtranslationsthatareintegercombinationsofthevectorsx . j Roughlyspeaking, thecondition(4)statesthatthediscrepancyofA and u B with respect to any 2i-cube Q decays noticeably faster than the size of the u boundary of Q as i → ∞. On the other hand, if a bijection M as in (2) u exists, then the difference between the number of elements in A and B that u u are inside any n-cube Q is trivially at most (2M +1)d ·2d·nd−1 = O(nd−1). Theorems 1.1 and 1.5 in [17] discuss to which degree the above conditions are best possible. Inthispaperweestablishthefollowingsufficientconditionformeasurable equivalence. MEASURABLE CIRCLE SQUARING 7 Theorem 2.2. Let k (cid:62) 1 and d (cid:62) 2 be integers, let δ > 0, let x ,...,x ∈ 1 d Tk be free, and let a function Ψ : {2i : i ∈ N} → R satisfy (cid:88)∞ Ψ(2i) (5) < ∞. 2(d−2)i i=0 Define Φ : {2i : i ∈ N} → R by Φ(2i) := 2i·Ψ(2i) for i ∈ N. (1) If Lebesgue measurable sets A,B ⊆ Tk are Ψ-uniform of density δ with respect to every (d−1)-tuple of distinct vectors from {x ,...,x }, then 1 d A T∼r B, where all pieces are Lebesgue measurable and are translated by integer combinations of the vectors x . j (2) If Baire sets A,B ⊆ Tk are Φ-uniform of density δ with respect to x ,...,x , then A T∼r B, where all pieces are Baire and are translated 1 d by integer combinations of the vectors x . j Remark 2.3. In the notation of Theorem 2.2, if X ⊆ Tk is Ψ-uniform with respect to any d−1 vectors from {x ,...,x }, then X is Φ-uniform with 1 d respect to x ,...,x . (Indeed, we can trivially represent any d-dimensional 2i- 1 d cubeinZd asthedisjointunionof2i copiesofthe(d−1)-dimensional2i-cube.) Thus the uniformity assumption of Part 1 is stronger than that of Part 2 (or of Theorem 2.1). We do not know if the Φ-uniformity alone is sufficient in Part 1. The following result of Laczkovich [16] shows how to pick vectors that satisfy Theorem 2.1. Since it is not explicitly stated in [16], we briefly sketch its proof. Lemma 2.4 (Laczkovich [16]). Let an integer k (cid:62) 1 and a set X ⊆ Tk satisfy dim(cid:50)(∂X) < k. Then there is d(X) such that, for every d (cid:62) d(X), if we select uniformly distributed independent random vectors x ,...,x ∈ Tk 1 d then with probability 1 there is C = C(X;x ,...,x ) such that X is Φ-uniform 1 d of density λ(X) with respect to x ,...,x , where Φ(2i) := C·2(d−2)i for i ∈ N. 1 d Sketch of Proof. By a box in Tk we mean a product of k sub-intervals of [0,1). Let d (cid:62) 1 be arbitrary and let x ,...,x ∈ Tk be random. By applying 1 d the Erd˝os-Tur´an-Koksma inequality, one can show that, with probability 1, there is C(cid:48) = C(cid:48)(x ,...,x ) such that, for every box Y ⊆ Tk, u ∈ Tk, and 1 d N-cube Q ⊆ Zd, we have that (cid:12) (cid:12) (6) (cid:12)|Y ∩Q|−λ(Y)|Q|(cid:12) (cid:54) Υ(N) := C(cid:48)logk+d+1N, (cid:12) u (cid:12) see [16, Lemma 2]. In other words, boxes have very small discrepancy with respect to arbitrary cubes. (In particular, each box is Υ-uniform.) So, assumethat(6) holdsandthatx ,...,x arefree. Fixarealα ∈ (0,1] 1 d satisfyingdim(cid:50)(∂X) < k−α. AresultofNiederreiterandWills[28,Kollorar4] implies that the set X is Ψ-uniform (with respect to x ,...,x ) for some Ψ(N) 1 d 8 L(cid:32).GRABOWSKI,A.MA´THE´,andO.PIKHURKO Figure 1. i) Circle ∂X and ε-regular grid; ii) boxes in B; iii) boxes in I that grows as O(Υ(N)α/kNd−αd/k) as N → ∞. In particular, we can satisfy Lemma 2.4 by letting d(X) be any integer such that αd(X)/k > 2. We refer the reader to [16, Page 62] for further details. Let us also outline the ideas behind [28, Kollorar 4] in order to show how the box dimension of ∂X comes into play. The definition of α implies that the measure of points within L∞-distance ε from the boundary of X is at most εα for all small ε > 0. Let N be large and let ε := (cid:98)(Nd/Υ(N))1/k(cid:99)−1. Partition Tk into a grid of boxes which is ε-regular, meaning that side lengths are all equal to ε. Let B consist of those boxes that intersect ∂X. By the definition of α, we have that |B| (cid:54) εα/εk. Next, iteratively merge any two boxes in the interior of X if they have the same projection on the first k −1 coordinates and share a (k−1)-dimensional face. Let I be the set of the final boxes in the interior of X. Figure 1 illustrates the special case when X is a disk. The size of I is at most ε−k+1 (the number of possible projections) plus |B| (as each box in B can “prevent” at most one merging). Pick any u ∈ Tk and an N-cube Q ⊆ Zd. We take the dual point of view wherewefixQ(cid:48) := {u+(cid:80)d n x : n ∈ Q} ⊆ Tk andmeasureitsdiscrepancy j=1 j j with respect to boxes. Namely, we have by (6) that D(cid:48)(Y) (cid:54) Υ(N) for every (cid:12) (cid:12) box Y ⊆ Tk, where we define D(cid:48)(Y) := (cid:12)|Q(cid:48) ∩Y|−λ(Y)Nd(cid:12). This implies (cid:12) (cid:12) that D(cid:48)(X) (cid:54) (cid:88) D(cid:48)(Y)+ (cid:88) D(cid:48)(Y ∩X) (cid:54) |I|·Υ(N)+|B|(εkNd+Υ(N)), Y∈I Y∈B giving the stated upper bound after routine simplifications. (cid:3) Thus Lemma 2.4 shows that the uniformity assumption of Part 2 of The- orem 2.2 can be satisfied if the sets A are B are as in Theorem 1.2. The lemma alsosufficesforPart1ofTheorem2.2,thusleadingtotheproofofTheorem1.2 as follows. MEASURABLE CIRCLE SQUARING 9 Proof of Theorem 1.2. Observe that the assumption dim(cid:50)(∂X) < k im- plies that X ⊆ Tk is both Baire and Lebesgue measurable. For example, let us argue that X is Baire. Every set is the union of its interior (an open set) and a subset of its boundary. So it is enough to show that ∂X is nowhere dense. Take any ball U ⊆ Tk of radius r > 0. As ε → 0, the ε-neighbourhood of ∂X has measure at most εα for some constant α > 0. This is strictly smaller than ((r −ε)/r)kλ(U), the volume of the ball U(cid:48) concentric to U of radius r −ε, so at least one point x ∈ U(cid:48) is uncovered. The open ball of radius ε around x lies entirely inside U and avoids ∂X. Thus ∂X is nowhere dense, as desired. Therefore, the sets A and B in Theorem 1.2 are both Baire and Lebesgue measurable. Next, let us show that we can satisfy the uniformity assumption of Part 1 of Theorem 2.2. Let d := max(d(A),d(B)) + 1, where d(X) is the function provided by Lemma 2.4. Fix free vectors x ,...,x ∈ Tk such that every (d−1)-tuple of 1 d them satisfies the conclusion of Lemma 2.4 for both A and B. Such vectors exist since the desired properties hold with probability 1 if we sample the vectors x independently. Let C < ∞ be the maximum, over all choices of j X ∈ {A,B} and integers 1 (cid:54) i < ... < i (cid:54) d, of the corresponding 1 d−1 constantsC(X;x ,...,x ). ThentheassumptionsofPart1ofTheorem2.2 i1 id−1 hold with Ψ(2i) := C ·2(d−3)i (and the same function works with Part 2). Theorem 2.2 implies that A and B are equivalent with Baire (resp. Lebes- gue) measurable pieces. Allowing empty pieces, let this be witnessed respec- tively by partitions A = ∪ A(cid:48) and A = ∪ A(cid:48)(cid:48) for some finite V ⊆ Tk, v∈V v v∈V v where the pieces A(cid:48) and A(cid:48)(cid:48) are translated by v. These equidecompositions v v canbe“merged”asfollows. TakeanullsetX ⊆ Tk suchthatTk\X ismeagre; the existence of X follows from e.g. [29, Theorem 1.6]. We can additionally assume that X is invariant under all translations from V. (For example, take the union of all translates of X by integer combinations of the vectors from V; it is still a nullset since we take countably many translates.) Now, we combine the Baire partition of A restricted to X with the Lebesgue partition restricted to Tk\X. Specifically, let A := (A(cid:48) ∩X)∪(A(cid:48)(cid:48)\X) for v ∈ V. Clearly, these v v v sets partition A while, by the invariance of X, the corresponding translates A +v, for v ∈ V, partition B. Also, each part A is both Baire and Lebesgue v v measurable. This proves Theorem 1.2. (cid:3) 3. Some common definitions and results Our proofs of Parts 1 and 2 of Theorem 2.2 proceed somewhat differently. This section collects some definitions and auxiliary results that are common to both parts. Here, let measurable mean Baire or Lebesgue measurable, de- pending on which σ-algebra we are interested in. 10 L(cid:32).GRABOWSKI,A.MA´THE´,andO.PIKHURKO Sincewewillstudyequidecompositionsfromgraph-theoreticpointofview, we find it convenient to adopt some notions of graph theory to our purposes as follows. By a bipartite graph we mean a triple G = (V ,V ,E), where V and V 1 2 1 2 are (finite or infinite) vertex sets and E ⊆ V × V is a set of edges. (Note 1 2 that E consists of ordered pairs to avoid ambiguities when V and V are not 1 2 disjoint.) The subgraph induced by sets X and X is 1 2 Ä ä (7) G[X ,X ] := V ∩X , V ∩X , E ∩(X ×X ) . 1 2 1 1 2 2 1 2 A matching in G is a subset M of E which gives a partial injection from V to 1 V (that is, if (a,b) and (a(cid:48),b(cid:48)) are distinct pairs in M then a (cid:54)= a(cid:48) and b (cid:54)= b(cid:48)). 2 Infact, wewillidentifyamatchingwiththecorrespondingpartialinjection. In particular, the sets of matched points in V and V can be respectively denoted 1 2 by M−1(V ) and M(V ). A matching M is perfect if it is a bijection from 2 1 V to V (that is, if M(V ) = V and M−1(V ) = V ). For a set X lying in 1 2 1 2 2 1 one part of G, let its neighbourhood Γ(X) consist of those vertices in the other part that are connected by at least one edge to X. (In the functional notation, we have Γ(X) = E(X) for X ⊆ A and Γ(X) = E−1(X) for X ⊆ B.) If G is locally finite (that is, every degree |Γ({x})| is finite), then Rado’s theorem [30] states that G has a perfect matching if and only if (8) |Γ(X)| (cid:62) |X|, for every finite subset X of A or B. Note that if V ∩V = ∅ then we get the standard notions of graph theory with 1 2 respect to the corresponding undirected graph on V ∪V . 1 2 Thus, anequidecompositionbetweenA,B ⊆ Tk wherealltranslationsare restricted to the set V that was defined in (1) is nothing else than a perfect M matching in the bipartite graph (9) G := (A,B,E), where E consists of all pairs (a,b) ∈ A×B with b−a ∈ V . M Assume from now on that both A and B are measurable (which will be the case in all applications). Then, each of the vertex parts of the graph G is additionallyendowedwiththeσ-algebraofmeasurablesets;objectsofthistype appear in orbit equivalence [13], limits of sparse graphs [24], and other areas. A matching M in G is called measurable if the set {a ∈ A : M(a)−a = v} is measurable for each v ∈ V . M Also, we will consider the subgraphs of G induced by cosets, viewing these as graphs on subsets of Zd. Namely, for u ∈ Tk, consider the bipartite graph G := (A ,B ,E ), where u u u u ¶ © E := (a,b) ∈ A ×B : (cid:107)a−b(cid:107) (cid:54) M . u u u ∞