Thomas’s question on Borel unfriendly partitions
Let be a locally finite Borel graph on a standard Borel space . Does there always exist a Borel coloring such that, for every , the number of neighbors of having color different from is at least the number of neighbors having color ? Equivalently, does every locally finite Borel graph admit a Borel unfriendly partition?
References
Primary source
Additional references
- Unfriendly partitions of locally finite Borel graphs — arXiv — José de Jesús Pelayo-Gómez
Progress summary
A September 2026 preprint claims to disprove the universal existence statement with a locally finite Borel graph having no unfriendly coloring, but the counterexample has not been verified.
Thomas’s question asks whether every locally finite Borel graph admits a Borel unfriendly partition.
Known results
- Every bounded-degree Borel graph of subexponential growth has a Borel unfriendly coloring.
- Measure-preserving Borel graphs with finite cost have almost-everywhere unfriendly colorings.
- Before 2026, the general question was open, even for bounded-degree graphs.
September 2026 counterexample claim; Community submission (unverified)
On September 10, 2026, José de Jesús Pelayo-Gómez’s preprint Unfriendly partitions of locally finite Borel graphs claimed a counterexample: an unbounded-degree, hyperfinite, bipartite, one-ended graph with no Borel unfriendly coloring. It also claims positive results for maximum degree at most under additional structural conditions. A submission dated September 12, 2026 argues for the same negative conclusion via an treeing, an odd-degree forest, and a finite-fibre blow-up, but this argument is unverified.
Current status (as of September 2026): The universal question is claimed to have a negative answer, but the counterexample and the accompanying community argument remain unverified; restricted positive cases do not settle the remaining problem.
Sources
- ar5iv.labs.arxiv.org
- arxiv.org
- arxiv.org
- openproblemgarden.org
- unsolvedmath.com
- semanticscholar.org
- mathoverflow.net
- researchgate.net
- math.cmu.edu
- home.agh.edu.pl
- arxiv.org
- ar5iv.labs.arxiv.org
- export.arxiv.org
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- math.berkeley.edu
- math.stackexchange.com
- logic.math.caltech.edu
- nbn-resolving.org
- quantamagazine.org
- arxiv.org
- arxiv.org
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- quantamagazine.org
- mathstodon.xyz
Solutions 1
ProofBorel Unfriendly Partitions of Locally Finite Graphs: A Parity Obstruction and Finite-Fibre Blow-Up CounterexampleSee full solution
We present a complete proof architecture for a negative answer to the Borel unfriendly-partition problem. Starting from the tail-equivalence relation E₀ on the space of binary sequences with infinitely many 1s, we construct a closed, locally finite, one-ended treeing whose edges are generated by a coordinate-flip parent map. A parity argument rules out Borel proper 2-colourings. We then modify the tree to an odd-degree forest and perform a finite-fibre blow-up with carefully chosen odd multiplicities. The blow-up has the rigidity property that every unfriendly colouring is fibrewise constant and induces a proper colouring of the underlying forest. Hence a Borel unfriendly colouring of the blow-up would yield a forbidden Borel proper colouring of the E₀ treeing. The construction therefore gives a locally finite Borel graph with no Borel unfriendly partition.