Spectral Theory for Borel PMP Graphs

Alexander Tenenbaum; Cecelia Higgins; Pieter Spaas

REVIEW 1 major objections 3 minor 8 references

Spectral Theory for Borel PMP Graphs

T0 review · 1 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Spectral invariants of graphings govern approximate measurable bipartiteness, chromatic number, and a measurable matching condition.

desk verdict Strong spectral toolbox for graphing combinatorics, but Theorem E/7.8 is false as stated — K4 kills the atomic case. read the letter →

arxiv 2602.05185 v2 pith:U26JOPWF submitted 2026-02-05 math.LO math.COmath.OAmath.SP

Cecelia Higgins , Pieter Spaas , Alexander Tenenbaum This is my paper · ORCID

classification math.LOmath.COmath.OAmath.SP MSC 05C5003E1537A2005C1505C70

keywords BorelpmpgraphsgraphingsspectralgraphtheoryapproximatemeasurablechromaticnumberbipartitenessTutteconditionperfectmatchingslocal-globalconvergence

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper's central claim is that the spectra of the adjacency and Laplacian operators of a bounded-degree Borel pmp graph — a 'graphing', i.e., a Borel graph on a probability space whose edge relation preserves the measure — determine its measurable combinatorics. It proves a spectral characterization of approximate measurable bipartiteness (the property of being 2-colorable on arbitrarily large measurable subsets): bipartiteness forces the adjacency spectrum to be symmetric about 0, and, with regularity, ergodicity, and a spectral gap, the presence of the negative maximum degree in the spectrum forces approximate bipartiteness. It then transplants classical finite-graph eigenvalue bounds to this setting, showing the approximate measurable chromatic number is at most the floor of the largest adjacency eigenvalue plus one, and at least one minus the ratio of the largest to smallest eigenvalues. It also proves the optimal bound 2n+1 for graphs generated by n bounded-to-one measure-preserving functions, and gives a spectral inequality on the Laplacian that implies a measurable version of Tutte's perfect-matching condition. If these results are right, spectral theory becomes a systematic toolkit for constructing measurable colorings and matchings in descriptive combinatorics.

What carries the argument

The adjacency operator T_G defined by (T_G f)(x) = sum_{y~x} f(y) on L^2(X), and the Laplacian L_G = D_G - T_G. The mass transport principle for measure-preserving equivalence relations makes these operators bounded and self-adjoint and yields the estimate that the graph's average degree is at most the maximum spectral value M(T_G). The spectral gap assumption — the top eigenvalue d of a regular graph is an isolated point of the spectrum — is what forces approximate eigenfunctions for -d to have approximately constant absolute value, so their sign can define a measurable bipartition. A backwards list-coloring argument converts a controlled exhaustive sequence of low-degree sets into (M+1)-co

What would settle it

Test the open case the paper flags: build an ergodic d-regular Borel pmp graph without spectral gap (for example the Schreier graph of a non-strongly-ergodic measure-preserving action) and check whether -d is in the adjacency spectrum while the graph fails to be approximately measurable bipartite. A yes would refute the possibility that the converse of Theorem A holds without the spectral-gap assumption; the paper reports no such example is known.

Watch

Extended reading notes

Core claim

The paper establishes that for a bounded-degree Borel pmp graph G, the adjacency operator T_G and the Laplacian L_G are bounded self-adjoint operators whose spectra carry combinatorial meaning. Specifically, approximate measurable bipartiteness implies that the spectrum of T_G is symmetric about 0, and — under ergodicity, d-regularity, and a spectral gap — the converse holds: if -d is in the spectrum, then G is approximately measurably bipartite. The approximate measurable chromatic number satisfies chi_ap_mu(G) <= floor(M(T_G)) + 1 and chi_ap_mu(G) >= ceil(1 - M(T_G)/m(T_G)). A pmp graph generated by n bounded-to-one Borel functions satisfies chi_ap_mu(G) <= 2n + 1. For ergodic regular G, t

Load-bearing premise

The load-bearing premise is that, for a d-regular ergodic pmp graph, the top spectral value d is an isolated point of the spectrum (spectral gap); only under this assumption can approximate eigenfunctions for -d be shown to have approximately constant absolute value, which the converse of the bipartiteness characterization requires.

Editorial extensions

If this is right

For ergodic d-regular pmp graphs with spectral gap, approximate measurable bipartiteness is equivalent to -d belonging to the adjacency spectrum, hence equivalent to symmetry of the spectrum.
The upper bound chi_ap_mu(G) <= floor(M(T_G)) + 1 improves the degree-plus-one bound and, for (a,b)-biregular graphs, improves quadratically on the measurable Brooks bound (though such graphs are trivially 2-colorable).
The lower bound chi_ap_mu(G) >= ceil(1 - M(T_G)/m(T_G)) is the measurable analogue of a classical spectral lower bound and holds for all bounded-degree pmp graphs, extending earlier regular-case results.
A pmp graph generated by n bounded-to-one Borel functions has approximate measurable chromatic number at most 2n+1, matching the sharp bound for finite graphs and settling a measurable variant of a long-standing question in the field.
When 2m_L >= M_L, the strict measurable Tutte condition holds; for bipartite graphs this yields strict expansion for independent sets, which combined with known results gives measurable perfect matchings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The spectral-gap hypothesis in the bipartiteness converse is load-bearing: without it, approximately invariant sets can create approximate eigenfunctions at -d whose signs oscillate, so a counterexample would most plausibly come from a non-strongly-ergodic action; the authors explicitly leave this open.
The Wilf- and Hoffman-type bounds frame the approximate measurable chromatic number as a function of the spectral interval [m(T_G), M(T_G)]; a natural test is whether this function is sharp among local-global limits of expander graphs.
If a measurable analogue of the classical Tutte theorem (strict expansion implies perfect matching) is ever established, the paper's Theorem E would become a purely spectral sufficient condition for measurable perfect matchings in non-bipartite graphs.
The local-global continuity result is a computational tool: spectra of limit graphings can be obtained as pointwise limits of finite spectra, allowing construction of graphings with prescribed spectra and combinatorial behavior, such as the interval [-2,2] for irrational rotation.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is mostly good and worth engaging, but you should know upfront that the matchings theorem, Theorem 7.8, is false as stated. Let G be K4 on four points with uniform measure. It is ergodic, 3-regular, and on L2_0 its Laplacian has mL=ML=4, so 2mL≥ML holds. Take A={v}. Then G↾(X\A) is K3, a single odd component, and ν_A(O_A)=µ(A), so no c<1 satisfies ν_A(O_A)≤cµ(A). The strict measurable Tutte condition fails. The error is in the atomic reduction: [BH05, Theorem 2.3] gives a perfect matching, but a perfect matching only implies Tutte with c=1, not the strict c<1 the authors define. The same obstruction works for every finite connected even-order graph with uniform atoms. So the theorem needs a non-atomic hypothesis, or the strict condition needs to be rethought.

Now the credit, because there is real substance here. Theorem A (spectral characterization of approximate bipartiteness) is a genuine adaptation, and the authors are honest that the converse needs ergodicity, regularity, and spectral gap — they flag the gap assumption as open, which is fine. Theorems B and D, the Wilf and Hoffman bounds for graphings, look new and the proofs check out: the recursive degree argument, the block-spectral inequality, and the limiting argument in Theorem 6.8 are coherent. Theorem C, the 2n+1 bound for pmp graphs generated by n bounded-to-one functions, is a nice non-spectral result and settles the approximate measurable version of that question. Section 8 on local-global continuity of the spectrum is a serviceable toolbox result with clean examples. The citation pattern is standard; no fitting or circularity.

Soft spots beyond the false theorem: the spectral-gap hypothesis in Theorem A is load-bearing and acknowledged; that is a limitation, not a flaw. The strict measurable Tutte condition is not yet connected to actual perfect matchings, which the authors also acknowledge in Remark 7.11. That is an open direction, not a defect. But the atomic counterexample is a defect, and it is in a headline theorem.

My recommendation: send this to peer review, but with a referee who checks the atomic case of 7.8 carefully. The correct fix is likely to restrict Theorem E to non-atomic spaces and to say explicitly that the finite analog gives equality, not strict inequality. After that revision, the rest of the paper deserves publication. As it stands, I would not cite Theorem E, and I would be cautious citing the paper until the statement is corrected.

Referee Report

1 major / 3 minor

Summary. The paper develops a spectral theory for bounded-degree Borel probability-measure-preserving (pmp) graphs. It defines the adjacency and Laplacian operators on L^2(X), establishes basic spectral properties, and proves several descriptive-combinatorial consequences: a spectral characterization of approximate measurable bipartiteness under ergodicity and spectral gap (Theorem A); a Wilf-type upper bound chi_ap <= floor(M(T_G))+1 (Theorem B); an upper bound chi_ap <= 2n+1 for pmp graphs generated by n bounded-to-one functions (Theorem C); a Hoffman-type lower bound chi_ap >= ceil(1 - M(T_G)/m(T_G)) (Theorem D); a Brouwer--Haemers-type sufficient condition for a newly introduced 'strict measurable Tutte condition' (Theorem E); and a continuity result for the spectrum under local-global convergence. The proofs are largely careful and self-contained, using approximate eigenfunctions, mass transport, and block-decomposition arguments.

Significance. If the central results were correct as stated, the paper would make a valuable contribution by importing spectral graph theory into descriptive combinatorics and providing quantitative bounds for approximate measurable chromatic numbers. Theorems A, B, C, and D appear technically sound and give genuine new tools; the local-global continuity result is also a useful addition. However, Theorem E is false as stated, and since it is one of the five advertised main theorems, the paper cannot be accepted in its current form. The counterexample is simple and localized, so a revision that restricts or reformulates the statement may salvage the paper's contribution.

major comments (1)

[§7, Theorem 7.8] Theorem 7.8 is false as stated. Let X be a four-point space with uniform atomic measure, and let G be the complete graph K4. Then G is a connected, hence ergodic, 3-regular Borel pmp graph. The Laplacian eigenvalues are 0,4,4,4, so on L2_0(X) we have m_L = M_L = 4 and 2m_L >= M_L holds. Take A = {v}. Then G ↾ (X\A) is K3, a single odd component of size 3, so O_A = X\A, and ν_A(O_A) = (1/3)·μ(X\{v}) = 1/4 = μ(A). Thus no c < 1 satisfies ν_A(O_A) ≤ c μ(A), and the strict measurable Tutte condition fails. The error is in the atomic reduction in the proof: the cited [BH05, Theorem 2.3] yields a perfect matching, which corresponds to Tutte's condition with c = 1, not to the strict inequality c < 1 required by Definition 7.5. The theorem statement needs a non-atomicity assumption, or the strict measurable Tutte condition must be weakened, and the abstract and downstream remarks (e.g., Lemma 7.

minor comments (3)

[§7, Definition 7.5] The paper should explicitly discuss why the strict measurable Tutte condition is not the literal measurable analogue of the classical Tutte condition: even for finite graphs with perfect matchings, strict inequality c < 1 fails in general. This would help readers see the issue in the atomic proof.
[§1, Abstract and Introduction] The abstract and introduction state Theorem E without any non-atomic or finiteness caveat. In light of the counterexample, the advertised statement should be revised to match a corrected theorem.
[§5.2, paragraph after Theorem 5.7] There is a typo: 'chromatics number' should be 'chromatic number'. Minor, but worth fixing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper derives new spectral characterizations and bounds from classical theorems and standard operator theory, with no fitted parameters or self-citation chains bearing the main results.

full rationale

The central claims are genuine implications rather than repackaged definitions. Theorem A is proved from the classical symmetry characterization and approximate eigenfunction arguments; the spectral-gap assumption is stated explicitly and the authors note in Remark 4.13 that removing it is open, so it is a real hypothesis rather than a hidden circular input. Theorems B, C, and D adapt Wilf's and Hoffman's theorems and the list-coloring lemma without fitting any spectral quantity to the conclusion. Theorem E introduces the strict measurable Tutte condition as a new definition and then proves that a spectral inequality analogous to the Brouwer–Haemers condition implies it; the proof relies on the external classical theorem [BH05], not on a self-citation. The atomic reduction in Theorem 7.8 may be a correctness concern—as an external K4 counterexample suggests that a perfect matching only gives the c=1 version of Tutte, not the strict c<1 condition—but that would be a logical-strength flaw, not circularity, because the conclusion is not definitionally equivalent to the spectral input. Section 8's continuity result is imported from external work [Tho20, FHL+21] and is not used to justify the paper's own main theorems. No parameter is fitted and later renamed as a prediction, and no load-bearing self-citation occurs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No empirically fitted constants appear. The s in Theorem 5.5 and c in Theorem 7.8 are proof-local scalars, not fit to data, and the spectral-gap epsilon is a hypothesis, not a fitted value. The only new object is the strict measurable Tutte condition, which is a mathematical definition rather than a postulated entity. The paper's assumptions are the standard pmp, bounded-degree, ergodicity, and spectral-gap hypotheses.

assumptions (6)

domain assumption Mass transport principle for pmp equivalence relations (Prop. 2.10), together with the pmp property of the graph.
Used throughout to convert sums over neighbors into integrals (Cor. 2.13, 2.14) and to equate average in-degree and out-degree in the proof of Theorem 5.7.
standard math Standard spectral theory of bounded self-adjoint operators on Hilbert space, including approximate-eigenfunction characterization and isolation of eigenvalues (Lemma 2.2, Prop. 2.3).
Foundation for all spectral arguments in Sections 3-7.
standard math Classical finite-graph spectral theorems: Wilf's bound, Hoffman's bound, and the Brouwer-Haemers Laplacian matching condition.
Theorems B, D, and E are measurable analogues of these classical results and rely on their statements as motivation and in the atomic reduction of Theorem 7.8.
standard math Borel list-coloring and Borel chromatic number facts from KST99 (Prop. 4.6) and the adapted list-coloring proposition (Prop. 5.1).
Used in Lemma 5.2 and in the proof of Theorem 5.5 to turn degree bounds into colorings.
standard math Local-global convergence machinery: first-order definability of the spectral distance and continuity results from Thornton (Tho20) and Farah et al. (FHL+21).
Theorem 8.1 and Corollary 8.2 depend on these cited results.
standard math Standard Borel space and non-atomic measure tools, including Lemma 2.8 and existence of measurable subsets of prescribed measure in Lemma 7.6.
Needed for approximate arguments and for constructing subsets in the measurable Tutte proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Spectral Theory for Borel PMP Graphs." pith.science (2026). https://pith.science/paper/U26JOPWF

@misc{pith2026260205185,
  author       = {Pith},
  title        = {Pith review of: Spectral Theory for Borel PMP Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U26JOPWF}},
  note         = {Machine review of arXiv:2602.05185}
}

abstract

We initiate a systematic study of spectral theory for bounded-degree Borel pmp graphs. Specifically, we study spectral properties of the associated adjacency and Laplacian operators. We start with proving a spectral characterization of approximate measurable bipartiteness. Next, we adapt classical theorems of Wilf and Hoffman to give novel upper and lower bounds on the approximate measurable chromatic number. Using similar techniques, we then show that the approximate measurable chromatic number of a pmp graph generated by $n$ bounded-to-one functions is at most $2n + 1$. Next, concerning matchings, we introduce a measurable version of Tutte's condition and show that a spectral assumption analogous to the one from a classical theorem of Brouwer and Haemers implies this measurable Tutte condition. Finally, we show that the spectrum is continuous under local-global convergence.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

8 extracted references · 6 linked inside Pith

[1]

Abért and G

[AE11] M. Abért and G. Elek,The space of actions, partition metric and combinatorial rigidity,https:// arxiv.org/abs/1108.2147(2011). [AT20] M. Abért and L. M. Tóth,Uniform rank gradient, cost, and local-global convergence, Trans. Amer. Math. Soc.373(2020), no. 4, 2311–2329. [BCR24] S. Bell, T. Chu, and O. Rodgers,Oscillating and non-summable Radon-Nikody...

arXiv 2011
[7]

Pikhurko,Borel combinatorics of locally finite graphs, Surveys in Combinatorics 2021 (K

[Pik21] O. Pikhurko,Borel combinatorics of locally finite graphs, Surveys in Combinatorics 2021 (K. K. Dabrowski, M. Gadouleau, N. Georgiou, M. Johnson, G. B. Mertzios, and D. Paulusma, eds.), London Mathematical Society Lecture Note Series, vol. 470, Cambridge University Press, 2021, pp. 267–320. [Pou24] A. Poulin,Elasticity of free type III actions of f...

arXiv 2021
[1324]

Feldman and C

[FM77] J. Feldman and C. C. Moore,Ergodic equivalence relations, cohomology, and von Neumann algebras. I, Trans. Amer. Math. Soc.234(1977), no. 2, 289–324. [GV25] J. Grebík and Z. Vidnyánszky,Ramsey, expanders, and Borel chromatic numbers, J. Math. Logic (to appear) (2025). [Hae95] W. H. Haemers,Interlacing eigenvalues and graphs, Linear Alg. Appl.226-228...

1977
[2010]

Kastner and C

[KL23] A. Kastner and C. R. Lyons,Baire-measurable matchings in non-amenable graphs,https://arxiv. org/abs/2310.20047(2023). [KM04] A. S. Kechris and B. D. Miller, Topics in Orbit Equivalence, Lecture Notes in Mathematics, vol. 1852, Springer,

arXiv 2023
[2012]

Bowen, G

[BKS22] M. Bowen, G. Kun, and M. Sabok,Perfect matchings in hyperfinite graphings,https://arxiv.org/ pdf/2106.01988(2022). [BPZ24] M. Bowen, A. Poulin, and J. Zomback,One-ended spanning trees and definable combinatorics, Trans. Amer. Math. Soc.377(2024), no. 12, 8411–8431. [BR11] B. Bollobás and O. Riordan,Sparse graphs: metrics and random models, Random ...

arXiv 2022
[2020]

[KST99] A. S. Kechris, S. Solecki, and S. Todorčević,Borel chromatic numbers, Adv. Math.141(1999), no. 1, 1–44. [KT08] A. S. Kechris and T. Tsankov,Amenable actions and almost invariant sets, Proc. Amer. Math. Soc. 136(2008), no. 2, 687–697. [KT19] G. Kun and A. Thom,Inapproximability of actions and Kazhdan’s property (T),https://arxiv.org/ abs/1901.03963...

arXiv 1999
[2024]

[Mil08] B. D. Miller,Measurable chromatic numbers, J. Symb. Logic73(2008), no. 4, 1139–1157. [Moh82] B. Mohar,The spectrum of an infinite graph, Linear Algebra Appl.48(1982), 245–256. [MP21] C. Meehan and K. Palamourdas,Borel chromatic numbers of graphs of commuting functions, Fund. Math.253(2021), 219–237. [MW89] B. Mohar and W. Woess,A survey on spectra...

2008
[2025]

Thornton,Factor maps for automorphism groups via Cayley diagrams,https://arxiv.org/abs/ 2011.14604(2020)

[Tho20] R. Thornton,Factor maps for automorphism groups via Cayley diagrams,https://arxiv.org/abs/ 2011.14604(2020). [Tho22] ,Orienting Borel graphs, Proc. Amer. Math. Soc.150(2022), no. 4, 1779–1793. [Tho24] ,Factor of iid colorings of trees,https://arxiv.org/abs/2402.02575(2024). [Tim19] Á Timár,One-ended spanning trees in amenable unimodular graphs, El...

arXiv 2011

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Abért and G

[AE11] M. Abért and G. Elek,The space of actions, partition metric and combinatorial rigidity,https:// arxiv.org/abs/1108.2147(2011). [AT20] M. Abért and L. M. Tóth,Uniform rank gradient, cost, and local-global convergence, Trans. Amer. Math. Soc.373(2020), no. 4, 2311–2329. [BCR24] S. Bell, T. Chu, and O. Rodgers,Oscillating and non-summable Radon-Nikody...

arXiv 2011

[2] [7]

Pikhurko,Borel combinatorics of locally finite graphs, Surveys in Combinatorics 2021 (K

[Pik21] O. Pikhurko,Borel combinatorics of locally finite graphs, Surveys in Combinatorics 2021 (K. K. Dabrowski, M. Gadouleau, N. Georgiou, M. Johnson, G. B. Mertzios, and D. Paulusma, eds.), London Mathematical Society Lecture Note Series, vol. 470, Cambridge University Press, 2021, pp. 267–320. [Pou24] A. Poulin,Elasticity of free type III actions of f...

arXiv 2021

[3] [1324]

Feldman and C

[FM77] J. Feldman and C. C. Moore,Ergodic equivalence relations, cohomology, and von Neumann algebras. I, Trans. Amer. Math. Soc.234(1977), no. 2, 289–324. [GV25] J. Grebík and Z. Vidnyánszky,Ramsey, expanders, and Borel chromatic numbers, J. Math. Logic (to appear) (2025). [Hae95] W. H. Haemers,Interlacing eigenvalues and graphs, Linear Alg. Appl.226-228...

1977

[4] [2010]

Kastner and C

[KL23] A. Kastner and C. R. Lyons,Baire-measurable matchings in non-amenable graphs,https://arxiv. org/abs/2310.20047(2023). [KM04] A. S. Kechris and B. D. Miller, Topics in Orbit Equivalence, Lecture Notes in Mathematics, vol. 1852, Springer,

arXiv 2023

[5] [2012]

Bowen, G

[BKS22] M. Bowen, G. Kun, and M. Sabok,Perfect matchings in hyperfinite graphings,https://arxiv.org/ pdf/2106.01988(2022). [BPZ24] M. Bowen, A. Poulin, and J. Zomback,One-ended spanning trees and definable combinatorics, Trans. Amer. Math. Soc.377(2024), no. 12, 8411–8431. [BR11] B. Bollobás and O. Riordan,Sparse graphs: metrics and random models, Random ...

arXiv 2022

[6] [2020]

[KST99] A. S. Kechris, S. Solecki, and S. Todorčević,Borel chromatic numbers, Adv. Math.141(1999), no. 1, 1–44. [KT08] A. S. Kechris and T. Tsankov,Amenable actions and almost invariant sets, Proc. Amer. Math. Soc. 136(2008), no. 2, 687–697. [KT19] G. Kun and A. Thom,Inapproximability of actions and Kazhdan’s property (T),https://arxiv.org/ abs/1901.03963...

arXiv 1999

[7] [2024]

[Mil08] B. D. Miller,Measurable chromatic numbers, J. Symb. Logic73(2008), no. 4, 1139–1157. [Moh82] B. Mohar,The spectrum of an infinite graph, Linear Algebra Appl.48(1982), 245–256. [MP21] C. Meehan and K. Palamourdas,Borel chromatic numbers of graphs of commuting functions, Fund. Math.253(2021), 219–237. [MW89] B. Mohar and W. Woess,A survey on spectra...

2008

[8] [2025]

Thornton,Factor maps for automorphism groups via Cayley diagrams,https://arxiv.org/abs/ 2011.14604(2020)

[Tho20] R. Thornton,Factor maps for automorphism groups via Cayley diagrams,https://arxiv.org/abs/ 2011.14604(2020). [Tho22] ,Orienting Borel graphs, Proc. Amer. Math. Soc.150(2022), no. 4, 1779–1793. [Tho24] ,Factor of iid colorings of trees,https://arxiv.org/abs/2402.02575(2024). [Tim19] Á Timár,One-ended spanning trees in amenable unimodular graphs, El...

arXiv 2011