pith. sign in

arxiv: 2606.11558 · v2 · pith:W66UZPZNnew · submitted 2026-06-10 · 🧮 math.LO · math.CO

Measurable matchings in unbalanced graphs

Anton Bernshteyn , Matt Bowen , Felix Weilacher This is my paper

Pith reviewed 2026-07-02 22:39 UTC · model grok-4.3

classification 🧮 math.LO math.CO
keywords Borel matchingunbalanced graphdescriptive set theorymeasurable combinatoricsedge coloringparadoxical decompositionasymptotic separation index
0
0 comments X

The pith

In unbalanced bipartite Borel graphs, a Borel matching covers almost every vertex in the higher-degree part for any Borel probability measure.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that locally finite bipartite multigraphs with an unbalanced bipartition admit Borel matchings that saturate almost all vertices on the side with higher degrees, even when the measure is not invariant. This is achieved through a probabilistic construction that works for arbitrary Borel measures. The result strengthens previous theorems that required invariance and leads to new bounds on measurable edge chromatic numbers and decompositions of group actions. It also resolves a conjecture on independent complete sections in graphs with finite asymptotic separation index.

Core claim

When G is a Borel locally finite bipartite multigraph that is unbalanced with respect to a bipartition (A, B), meaning deg(x) > deg(y) for all x in A and y in B, and μ is a Borel probability measure on the vertex set, there is a Borel matching in G that covers μ-almost every vertex in A. The proof uses a novel probabilistic approach that does not rely on μ being G-invariant.

What carries the argument

The unbalanced degree condition on the bipartition (A, B), which guarantees that matchings can be chosen to cover side A preferentially, together with the probabilistic method for selecting the Borel matching without invariance assumptions.

If this is right

  • The measurable edge-chromatic number of every Borel multigraph with finite maximum degree Δ is at most floor(3Δ/2).
  • Paradoxical Borel group actions with finite asymptotic separation index admit paradoxical decompositions with Borel pieces.
  • Borel independent complete sections exist in Borel graphs of finite asymptotic separation index.
  • Under additional conditions, there exist Borel matchings covering every vertex in A.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The probabilistic method might extend to selection problems beyond matchings in descriptive combinatorics.
  • The removal of invariance could apply to other measurable matching or coloring results where measures are arbitrary rather than invariant.
  • These techniques may connect to questions about equidecompositions in actions that lack invariance assumptions.

Load-bearing premise

The multigraph is locally finite, bipartite, and unbalanced, meaning one side of the bipartition has strictly higher degree at every vertex than the other side.

What would settle it

A specific Borel locally finite bipartite unbalanced graph G together with a Borel probability measure μ such that every Borel matching leaves a positive μ-measure subset of A uncovered would disprove the claim.

read the original abstract

Let $G$ be a locally finite multigraph that is bipartite and "unbalanced," meaning that it has a nontrivial bipartition $(A,B)$ with $\mathrm{deg}(x) > \mathrm{deg}(y)$ for all $x \in A$ and $y \in B$. We explore matchings in such graphs through the lens of descriptive set theory. In particular, we show that when $G$ is Borel and $\mu$ is a Borel probability measure on its vertex set, there is a Borel matching in $G$ that covers $\mu$-almost every vertex in $A$. This was previously known only under the assumption that $\mu$ is $G$-invariant, which we eliminate using a novel probabilistic approach. We also describe various extra conditions that imply the existence of a Borel matching covering every vertex in $A$. Along the way, we confirm a conjecture of the first and third named authors concerning the existence of Borel independent complete sections in Borel graphs of finite asymptotic separation index. In addition to their intrinsic interest, our results have applications to various other topics, such as edge-colorings, balanced orientations, and equidecomposition theory for group actions. For example, we show that the measurable edge-chromatic number of every Borel multigraph with finite maximum degree $\Delta$ is at most $\lfloor\frac{3\Delta}{2}\rfloor$, matching Shannon's optimal bound for finite multigraphs. Another example is that paradoxical Borel group actions with finite asymptotic separation index admit paradoxical decompositions with Borel pieces. This refines a result of Marks and Unger.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that for a Borel locally finite bipartite multigraph G with an unbalanced bipartition (A,B) (deg(x) > deg(y) for all x in A, y in B), and any Borel probability measure μ on the vertex set, there exists a Borel matching covering μ-almost every vertex in A. This removes the prior G-invariance requirement on μ via a novel probabilistic construction. The paper also gives conditions guaranteeing a Borel matching covering all of A, confirms a conjecture on Borel independent complete sections in finite asymptotic separation index graphs, and derives applications including a measurable edge-chromatic number bound of floor(3Δ/2) for Borel multigraphs of max degree Δ and Borel paradoxical decompositions for group actions with finite ASI.

Significance. If the central existence result holds, the work meaningfully extends measurable matching theory in descriptive set theory by handling arbitrary Borel measures rather than only invariant ones. The probabilistic method is a clear technical advance. Explicit credit is due for confirming the conjecture on independent complete sections and for the applications to edge-colorings (matching Shannon's finite bound) and equidecompositions, which refine prior results of Marks-Unger. These strengthen the paper's impact in measurable combinatorics.

minor comments (3)
  1. [§1] §1, paragraph after Definition 1.2: the statement that the probabilistic method 'eliminates' invariance could be rephrased to 'removes the need for' to avoid any ambiguity with the measure class.
  2. [§4] The proof of the main theorem in §4 relies on a sequence of auxiliary lemmas; adding a short roadmap paragraph at the start of §4 would improve readability without altering content.
  3. [§3] Notation for the auxiliary graph G' in the probabilistic construction (around Eq. (3.5)) is introduced without an explicit forward reference to its use in the measure construction; a single cross-reference would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report, detailed summary of our results, and recommendation to accept the manuscript. We are pleased that the central theorem, the probabilistic construction, the confirmation of the conjecture, and the applications were viewed favorably.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The central result establishes a Borel matching covering μ-almost every vertex in A for arbitrary Borel probability measures μ, via a novel probabilistic construction that removes the prior G-invariance requirement. This is presented as independent of fitted parameters or prior self-citations for the main theorem. The confirmation of the authors' own conjecture on Borel independent complete sections is an auxiliary result proved within the paper rather than invoked as an unverified premise. No equations or steps reduce by construction to inputs, self-definitions, or load-bearing self-citations; the argument supplies its own technical details under the stated hypotheses of local finiteness, bipartiteness, and the unbalanced degree condition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard descriptive set theory (Borel sets, measures, local finiteness) plus a new probabilistic construction; no free parameters or invented entities are indicated in the abstract.

axioms (1)
  • standard math Standard ZFC set theory with Borel sigma-algebra and probability measures on Polish spaces
    Invoked to define Borel graphs, Borel matchings, and Borel measures on the vertex set.

pith-pipeline@v0.9.1-grok · 5818 in / 1205 out tokens · 29544 ms · 2026-07-02T22:39:16.144226+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

152 extracted references · 23 canonical work pages · 5 internal anchors

  1. [1]

    Aharoni,M

    [ACK02] R. Aharoni,M. Chudnovsky, andA. Kotlov.Triangulated spheres and colored cliques, Discrete Comput. Geom.,28(2002), 223–229 (cit. on p

    2002

  2. [2]

    Alon.The linear arboricity of graphs, Isr

    [Alo88] N. Alon.The linear arboricity of graphs, Isr. J. Math.,62(1988), 311–325 (cit. on pp. 32,

    1988

  3. [3]

    Alon.Probabilistic methods in coloring and decomposition problems, Discrete Math.,127 (1994), 31–46 (cit

    [Alo94] N. Alon.Probabilistic methods in coloring and decomposition problems, Discrete Math.,127 (1994), 31–46 (cit. on p

    1994

  4. [4]

    [ABI86] N. Alon,L. Babai, andA. Itai.A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms,7(4) (1986), 567–583 (cit. on p

    1986

  5. [5]

    AlonandJ.H

    [AS16] N. AlonandJ.H. Spencer.The Probabilistic Method. 4th ed. John Wiley & Sons, 2016 (cit. on pp. 34, 35, 37,

    2016

  6. [6]

    [AE14] P. AraandR. Exel.Dynamical systems associated to separated graphs, graph algebras, and paradoxical decompositions, Adv. Math.,252(2014), 748–804 (cit. on p

    2014

  7. [7]

    Awerbuch,A.V

    [Awe+89] B. Awerbuch,A.V. Goldberg,M. Luby, andS.A. Plotkin.Network decomposition and locality in distributed computation, IEEE Symposium on Foundations of Computer Science (FOCS), (1989), 364–369 (cit. on p

    1989

  8. [8]

    BanachandA

    [BT24] S. BanachandA. Tarski.Sur la décomposition des ensembles de points en parties respec- tivement congruentes(French) [On the decomposition of point sets into respectively congruent parts], Fundam. Math.,6(1924), 244–277 (cit. on p

    1924

  9. [9]

    BarenboimandM

    [BE13] L. BarenboimandM. Elkin.Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. 2013 (cit. on p

    2013

  10. [10]

    Bartal.Probabilistic approximation of metric spaces and its algorithmic applications, IEEE Symposium on Foundations of Computer Science (FOCS), (1996), 184–193 (cit

    [Bar96] Y. Bartal.Probabilistic approximation of metric spaces and its algorithmic applications, IEEE Symposium on Foundations of Computer Science (FOCS), (1996), 184–193 (cit. on p

    1996

  11. [11]

    Beck.An algorithmic approach to the Lovász Local Lemma

    [Bec91] J. Beck.An algorithmic approach to the Lovász Local Lemma. I, Rand. Str. & Alg.,2(4) (1991), 343–365 (cit. on p

    1991

  12. [12]

    [Bel+25] S. Bell,T. Chu,O. Rodgers,G. Terlov, andA. Tserunyan.Heavy repulsion of clusters in Bernoulli percolation,https://arxiv.org/abs/2509.10631 (preprint), 2025 (cit. on p

    work page arXiv 2025

  13. [13]

    [BHT24a] F. Bencs,A. Hrušková, andL.M. Tóth.Factor-of-iid balanced orientation of non- amenable graphs, Eur. J. Comb.,115(2024), #103784 (cit. on p

    2024

  14. [14]

    [BHT24b] F. Bencs,A. Hrušková, andL.M. Tóth.Factor-of-iid Schreier decorations of lattices in Euclidean spaces, Discrete Math.,347(9) (2024), #114056 (cit. on pp. 3,

    2024

  15. [15]

    Bernshteyn.Measurable versions of the Lovász Local Lemma and measurable graph colorings, Adv

    [Ber19] A. Bernshteyn.Measurable versions of the Lovász Local Lemma and measurable graph colorings, Adv. Math.,353(2019) (cit. on pp. 23,

    2019

  16. [16]

    Bernshteyn.Local coloring problems on smooth graphs, Fund

    [Ber22] A. Bernshteyn.Local coloring problems on smooth graphs, Fund. Math.,256(2022), 333–339 (cit. on p

    2022

  17. [17]

    Bernshteyn.Distributed algorithms, the Lovász Local Lemma, and descriptive combina- torics, Invent

    [Ber23a] A. Bernshteyn.Distributed algorithms, the Lovász Local Lemma, and descriptive combina- torics, Invent. Math.,233(2023), 495–542 (cit. on pp. 5, 35, 38, 39, 45, 46,

    2023

  18. [18]

    Bernshteyn.Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms, Adv

    62 [Ber23b] A. Bernshteyn.Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms, Adv. Math.,415(2023), #108895 (cit. on p

    2023

  19. [19]

    BernshteynandA

    [BD25] A. BernshteynandA. Dhawan.Borel Vizing’s theorem for graphs of subexponential growth, Proc. Am. Math. Soc.,153(2025), 7–14 (cit. on pp. 6, 9,

    2025

  20. [20]

    BernshteynandF

    [BW25] A. BernshteynandF. Weilacher.Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index, Trans. Am. Math. Soc.,378(11) (2025), 8183–8221 (cit. on pp. 6–8, 33–36, 38, 39, 44–46,

    2025

  21. [21]

    Borel Local Lemma: arbitrary random variables and limited exponential growth

    [BY24] A. BernshteynandJ. Yu.Borel Local Lemma: arbitrary random variables and limited exponential growth, https://arxiv.org/abs/2412.11571 (preprint),

    work page internal anchor Pith review Pith/arXiv arXiv

  22. [22]

    BernshteynandJ

    [BY25] A. BernshteynandJ. Yu.Large-scale geometry of Borel graphs of polynomial growth, Adv. Math.,473(2025), #110290 (cit. on pp. 16,

    2025

  23. [23]

    BernshteynandJ

    [BY26] A. BernshteynandJ. Yu.Embedding Borel graphs into grids of asymptotically optimal dimension, Proc. Am. Math. Soc.,154(2026), 2669–2680 (cit. on p

    2026

  24. [24]

    BohmanandR

    [BH02] T. BohmanandR. Holzman.On a list coloring conjecture of Reed, J. Graph Theory,41 (2002), 106–109 (cit. on p

    2002

  25. [25]

    Bollobas,P

    [BES75] B. Bollobas,P. Erdős, andE. Szemerédi.On complete subgraphs of r-chromatic graphs, Discrete Math.,13(1975), 97–107 (cit. on p

    1975

  26. [26]

    Bowen,C.T

    [BCW24] M. Bowen,C.T. Conley, andF. Weilacher.Measurable regular subgraphs, https: //www.arxiv.org/abs/2408.09597 (preprint),

    work page arXiv

  27. [27]

    [Bow+25] M. Bowen,A. Girão,H. Jardón-Sánchez, andG. Terlov.Measurable one-ended spanning trees,https://arxiv.org/abs/2509.15000(preprint), 2025 (cit. on pp. 5,

    work page arXiv 2025

  28. [28]

    [BKS22] M. Bowen,G. Kun, andM. Sabok.Perfect matchings in hyperfinite graphings, https: //arxiv.org/abs/2106.01988(preprint), 2022 (cit. on pp. 3, 5,

    work page arXiv 2022

  29. [29]

    [BKS25] M. Bowen,G. Kun, andM. Sabok.The uniform Gardner conjecture and rounding Borel flows, Proc. Am. Math. Soc.,153(8) (2025), 3607–3618 (cit. on pp. 3,

    2025

  30. [30]

    [BPZ24] M. Bowen,A. Poulin, andJ. Zomback.One-ended spanning trees and definable combina- torics, Trans. Am. Math. Soc.,377(12) (2024), 8411–8431 (cit. on pp. 5,

    2024

  31. [31]

    BowenandF

    [BW23] M. BowenandF. Weilacher.Definable Kőnig Theorems, Proc. Am. Math. Soc.,151 (2023), 4991–4996 (cit. on pp. 6, 7, 28–30,

    2023

  32. [32]

    Brandt,Y.-J

    [Bra+22] S. Brandt,Y.-J. Chang,J. Grebík,C. Grunau,V. Rozhoň, andZ. Vidnyán- szky.Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics, Innovations in Theoretical Computer Science Conference (ITCS), (2022), 29:1–29:26. Full version:https://arxiv.org/abs/2106.02066(cit. on pp. 4, 18,

    work page arXiv 2022

  33. [33]

    Brandt,C

    [BGR20] S. Brandt,C. Grunau, andV. Rozhoň.Generalizing the sharp threshold phenomenon for the distributed complexity of the Lovász Local Lemma, ACM Symposium on Principles of Distributed Computing (PODC), (2020), 329–338. Full version:https://arxiv.org/abs/2006. 04625(cit. on p

    2020

  34. [34]

    [Bro41] R. L. Brooks.On colouring the nodes of a network, Math. Proc. Camb. Philos. Soc.,37(2) (1941), 194–197 (cit. on pp. 44,

    1941

  35. [35]

    ChangandS

    [CP19] Y.-J. ChangandS. Pettie.A time hierarchy theorem for the LOCAL model, SIAM J. Comput.,48(1) (2019), 33–69 (cit. on pp. 35,

    2019

  36. [36]

    [CTT25] R. Chen,G. Terlov, andA. Tserunyan.Nonamenable subforests of multi-ended quasi-pmp graphs,https://arxiv.org/abs/2211.07908(preprint), 2025 (cit. on p

    work page arXiv 2025

  37. [37]

    [CPS17] K.-M. Chung,S. Pettie, andH.-H. Su.Distributed algorithms for the Lovász Local Lemma and graph coloring, Distrib. Comput.,30(4) (2017), 261–280 (cit. on pp. 35, 39,

    2017

  38. [38]

    CieślaandM

    [CS22] T. CieślaandM. Sabok.Measurable Hall’s theorem for actions of abelian groups, J. Eur. Math. Soc.,24(2022), 2751–2773 (cit. on pp. 3,

    2022

  39. [39]

    Clemens,C.T

    63 [CCM16] J.D. Clemens,C.T. Conley, andB.D. Miller.The smooth ideal, Proc. London Math. Soc.,112(1) (2016), 57–80 (cit. on p

    2016

  40. [40]

    Conley,S

    [Con+20] C.T. Conley,S. Jackson,A.S. Marks,B. Seward, andR.D. Tucker-Drob. Hyperfiniteness and Borel combinatorics, J. Eur. Math. Soc.,22(3) (2020), 877–892 (cit. on pp. 43,

    2020

  41. [41]

    Conley,S

    [Con+23] C.T. Conley,S. Jackson,A.S. Marks,B. Seward, andR.D. Tucker-Drob.Borel asymptotic dimension and hyperfinite equivalence relations, Duke Math. J.,172(16) (2023), 3175–3226 (cit. on pp. 6, 7, 12–14, 28, 29, 48,

    2023

  42. [42]

    Conley,S.C

    [Con+18] C.T. Conley,S.C. Jackson,D. Kerr,A.S. Marks,B. Seward, andR.D. Tucker- Drob.Følner tilings for actions of amenable groups, Math. Ann.,371(2018), 663–683 (cit. on pp. 3, 5, 13, 14, 19, 57–59) [CK13] C.T. ConleyandA.S. Kechris.Measurable chromatic and independence numbers for ergodic graphs and group actions, Groups Geom. Dyn.,7(1) (2013), 127–180 ...

    2018

  43. [43]

    Conley,A.S

    [CMT16] C.T. Conley,A.S. Marks, andR.D. Tucker-Drob.Brooks’ theorem for measurable colorings, Forum Math. Sigma,4(2016), e16 (cit. on pp. 45,

    2016

  44. [44]

    ConleyandB.D

    [CM16] C.T. ConleyandB.D. Miller.A bound on measurable chromatic numbers of locally finite Borel graphs, Math. Res. Lett.,23(6) (2016), 1633–1644 (cit. on p

    2016

  45. [45]

    ConleyandB.D

    [CM17] C.T. ConleyandB.D. Miller.Measurable perfect matchings for acyclic locally countable Borel graphs, J. Symb. Log.,82(1) (2017), 258–271 (cit. on p

    2017

  46. [46]

    ConleyandO

    [CT21] C.T. ConleyandO. Tamuz.Unfriendly colorings of graphs with finite average degree, Proc. London Math. Soc.,122(2) (2021), 229–233 (cit. on p

    2021

  47. [47]

    Cranston.Graph Coloring Methods

    [Cra24] D.W. Cranston.Graph Coloring Methods. 2024.url: https://graphcoloringmethods. com/(cit. on p

    2024

  48. [48]

    [Csó+22] E. Csóka,Ł. Grabowski,A. Máthé,O. Pikhurko, andK. Tyros.Moser–Tardos Algorithm with small number of random bits,https://arxiv.org/abs/2203.05888 (preprint), 2022 (cit. on pp. 6, 23,

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  49. [49]

    [CLP16] E. Csóka,G. Lippner, andO. Pikhurko.Kőnig’s line coloring and Vizing’s theorems for graphings, Forum Math. Sigma,4(2016), e27 (cit. on p

    2016

  50. [50]

    Dhawan.Edge-coloring algorithms for bounded degree multigraphs, ACM-SIAM Symposium on Discrete Algorithms (SODA), (2024), 2120–2157

    [Dha24] A. Dhawan.Edge-coloring algorithms for bounded degree multigraphs, ACM-SIAM Symposium on Discrete Algorithms (SODA), (2024), 2120–2157. Full version:https://arxiv.org/abs/ 2307.06579(cit. on p

    work page arXiv 2024

  51. [51]

    Diestel.Graph Theory

    [Die25] R. Diestel.Graph Theory. 6th ed. Berlin, Heidelberg: Springer, 2025 (cit. on pp. 3, 20, 38, 44, 45,

    2025

  52. [52]

    DoughertyandM

    [DF94] R. DoughertyandM. Foreman.Banach–Tarski decompositions using sets with the property of Baire, J. Am. Math. Soc.,7(1) (1994), 75–124 (cit. on pp. 6,

    1994

  53. [53]

    Downarowicz,D

    [DHZ19] T. Downarowicz,D. Huczek, andG. Zhang.Tilings of amenable groups, J. Reine Angew. Math.,747(2019), 277–298 (cit. on p

    2019

  54. [54]

    DownarowiczandG

    [DZ23] T. DownarowiczandG. Zhang.Symbolic extensions of amenable group actions and the comparison property, Mem. Am. Math. Soc.,281(2023) (cit. on pp. 13, 14, 57–59) [EL10] G. ElekandG. Lippner.Borel oracles. An analytical approach to constant-time algorithms, Proc. Am. Math. Soc.,138(8) (2010), 2939–2947 (cit. on p

    2023

  55. [55]

    ErdősandL

    [EL75] P. ErdősandL. Lovász.Problems and results on3-chromatic hypergraphs and some related questions, Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai, (1975). Ed. byA. Hajnal, R. Rado, andV.T. Sós, 609–627 (cit. on p

    1975

  56. [56]

    Erdős,A.L

    [ERT79] P. Erdős,A.L. Rubin, andH. Taylor.Choosability in graphs, Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI, (1979), 125–157 (cit. on p

    1979

  57. [57]

    Fellows.Transversals of vertex partitions in graphs, SIAM J

    [Fel90] M. Fellows.Transversals of vertex partitions in graphs, SIAM J. Discrete Math.,3(1990), 206–215 (cit. on pp. 32,

    1990

  58. [58]

    Sublogarithmic Distributed Algorithms for Lov\'asz Local lemma, and the Complexity Hierarchy

    [FG17] M. FischerandM. Ghaffari.Sublogarithmic distributed algorithms for Lovász Local Lemma, and the complexity hierarchy, International Symposium on DIStributed Computing (DISC),91 (2017), 18:1–18:16. Full version:https://arxiv.org/abs/1705.04840(cit. on pp. 28, 35,

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  59. [59]

    Fournier.Un théorème général de coloration(French) [A general coloring theorem]

    [Fou78] J.-C. Fournier.Un théorème général de coloration(French) [A general coloring theorem]. 1978 (cit. on p

    1978

  60. [60]

    Geschke.Weak Borel chromatic numbers, Math

    64 [Ges11] S. Geschke.Weak Borel chromatic numbers, Math. Log. Q.,57(1) (2011), 5–13 (cit. on p

    2011

  61. [61]

    GhaffariandC

    [GG24] M. GhaffariandC. Grunau.Near-optimal deterministic network decomposition and ruling set, and improved MIS, IEEE Symposium on Foundations of Computer Science (FOCS), (2024), 2148–2179. Full version:https://arxiv.org/abs/2410.19516(cit. on p

    work page arXiv 2024

  62. [62]

    Ghaffari,D

    [GHK18] M. Ghaffari,D. Harris, andF. Kuhn.On derandomizing local distributed algorithms, IEEE Symposium on Foundations of Computer Science (FOCS), (2018), 662–673. Full version: https://arxiv.org/abs/1711.02194(cit. on p

    work page arXiv 2018

  63. [63]

    Ghaffari,J

    [Gha+20] M. Ghaffari,J. Hirvonen,F. Kuhn,Y. Maus,J. Suomela, andJ. Uitto.Improved distributed degree splitting and edge coloring, Distrib. Comput.,33(2020), 293–310 (cit. on p

    2020

  64. [64]

    Deterministic Distributed Edge-Coloring with Fewer Colors

    [Gha+18] M. Ghaffari,F. Kuhn,Y. Maus, andJ. Uitto.Deterministic distributed edge-coloring with fewer colors, ACM SIGACT Symposium on Theory of Computing, (2018), 418–430. Full version:https://arxiv.org/abs/1711.05469(cit. on pp. 9,

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  65. [65]

    Distributed Degree Splitting, Edge Coloring, and Orientations

    [GS17] M. GhaffariandH.-H. Su.Distributed degree splitting, edge coloring, and orientations, ACM-SIAM Symposium on Discrete Algorithms (SODA), (2017), 2505–2523. Full version: https://arxiv.org/abs/1608.03220(cit. on p

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  66. [66]

    Goldberg,S

    [GPS88] A. Goldberg,S. Plotkin, andG. Shannon.Parallel symmetry-breaking in sparse graphs, SIAM J. Discrete Math.,1(4) (1988), 434–446 (cit. on p

    1988

  67. [67]

    Grabowski,A

    [GMP17] L. Grabowski,A. Máthé, andO. Pikhurko.Measurable circle squaring, Ann. Math., 185(2) (2017), 671–710 (cit. on p

    2017

  68. [68]

    Grebík.Measurable Vizing’s theorem, Forum Math

    [Gre25] J. Grebík.Measurable Vizing’s theorem, Forum Math. Sigma,13(2025), e32 (cit. on pp. 5, 9,

    2025

  69. [69]

    GrebíkandO

    [GP20] J. GrebíkandO. Pikhurko.Measurable versions of Vizing’s theorem, Adv. Math.,374(18) (2020), #107378 (cit. on p

    2020

  70. [70]

    GrebíkandV

    [GR23] J. GrebíkandV. Rozhoň.Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics, Adv. Math.,431(2023), #109241 (cit. on pp. 3,

    2023

  71. [71]

    GrebíkandZ

    [GV25] J. GrebíkandZ. Vidnyánszky.From descriptive to distributed, https://arxiv.org/abs/ 2502.15347(preprint), 2025 (cit. on pp. 25, 45,

    work page arXiv 2025

  72. [72]

    Gromov.Geometric group theory, Vol

    [Gro93] M. Gromov.Geometric group theory, Vol. 2: Asymptotic invariants of infinite groups. Ed. by A. NibloandM.A. Roller. Cambridge: Cambridge Univ. Press, 1993 (cit. on p

    1993

  73. [73]

    Hall Jr.Distinct representatives of subsets, Bull

    [Hal48] M. Hall Jr.Distinct representatives of subsets, Bull. Am. Math. Soc.,54(10) (1948), 922–926 (cit. on p

    1948

  74. [74]

    Hall.On representatives of subsets, J

    [Hal35] P. Hall.On representatives of subsets, J. London Math. Soc.,10(1) (1935), 26–30 (cit. on p

    1935

  75. [75]

    Hausdorff.Bemerkung über den Inhalt von Punktmengen(German) [A remark on the content of point sets], Math

    [Hau14] F. Hausdorff.Bemerkung über den Inhalt von Punktmengen(German) [A remark on the content of point sets], Math. Ann.,75(3) (1914), 428–434 (cit. on p

    1914

  76. [76]

    Haxell.A condition for matchability in hypergraphs, Graphs Comb.,11(1995), 245–248 (cit

    [Hax95] P. Haxell.A condition for matchability in hypergraphs, Graphs Comb.,11(1995), 245–248 (cit. on p

    1995

  77. [77]

    Haxell.A note on vertex list colouring, Comb

    [Hax01] P. Haxell.A note on vertex list colouring, Comb. Probab. Comput.,10(2001), 345–348 (cit. on pp. 32,

    2001

  78. [78]

    Hutchcroft.Non-uniqueness and mean-field criticality for percolation on nonunimodular transitive graphs, J

    [Hut20] T. Hutchcroft.Non-uniqueness and mean-field criticality for percolation on nonunimodular transitive graphs, J. Am. Math. Soc.,33(4) (2020), 1101–1165 (cit. on p

    2020

  79. [79]

    IyerandF

    [IS25] S. IyerandF. Shinko.Asymptotic dimension and hyperfiniteness of generic Cantor actions, Groups Geom. Dyn., (2025), published online first (cit. on p

    2025

  80. [80]

    Juschenko.Amenability of Discrete Groups by Examples

    [Jus22] K. Juschenko.Amenability of Discrete Groups by Examples. Providence, RI: American Mathematical Society, 2022 (cit. on p

    2022

Showing first 80 references.