ONE-ENDED SPANNING TREES AND DEFINABLE COMBINATORICS MATT BOWEN ANTOINE POULIN AND JENNA ZOMBACK Abstract. Let X be a Polish space with Borel probability measure andGa locally

2025-05-02 0 0 1.19MB 18 页 10玖币
侵权投诉
ONE-ENDED SPANNING TREES AND DEFINABLE COMBINATORICS
MATT BOWEN, ANTOINE POULIN, AND JENNA ZOMBACK
Abstract.
Let (
X, τ
) be a Polish space with Borel probability measure
µ,
and
G
a locally
finite one-ended Borel graph on
X.
We show that
G
admits a Borel one-ended spanning tree
generically. If
G
is induced by a free Borel action of an amenable (resp., polynomial growth)
group then we show the same result
µ
-a.e. (resp., everywhere). Our results generalize recent
work of Tim´ar, as well as of Conley, Gaboriau, Marks, and Tucker-Drob, who proved this in
the probability measure preserving setting. We apply our theorem to find Borel orientations
in even degree graphs and measurable and Baire measurable perfect matchings in regular
bipartite graphs, refining theorems that were previously only known to hold for measure
preserving graphs. In particular, we prove that bipartite one-ended
d
-regular Borel graphs
admit Baire measurable perfect matchings.
Contents
1. Introduction ........................................................... 2
1.1. Future work............................................................. 3
2. Preliminaries........................................................... 4
2.1. Connected toasts and one-ended spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Full sets................................................................. 5
2.3. The Radon–Nikodym cocycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Existence of connected toasts ........................................ 7
3.1. Connected toasts generically . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2. Connected toasts a.e. in group actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3. Connected toasts and polynomial growth groups . . . . . . . . . . . . . . . . . . . . . . . . . 11
4. Combinatorial applications ............................................ 14
4.1. Borel orientations........................................................ 14
4.2. Perfect matchings generically . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3. Perfect matchings a.e..................................................... 17
References................................................................. 17
Date: October 27, 2022.
1
arXiv:2210.14300v1 [math.CO] 25 Oct 2022
2 MATT BOWEN, ANTOINE POULIN, AND JENNA ZOMBACK
1. Introduction
In this paper we are concerned with determining which hyperfinite Borel graphs admit Borel
one-ended spanning trees and with applications of these objects to definable combinatorics.
Recall that a
Borel graph
on a Polish space (
X, τ
) is a graph whose vertex set
V
(
G
) is
X
and whose edge set
E
(
G
) is a Borel subset of
X2.
A Borel graph is
hyperfinite
if it can
be written as an increasing union of component finite Borel graphs. A connected graph
G
is
one-ended
if for every finite
F⊂V
(
G
) the induced subgraph on
V
(
G
)
−F
has exactly
one infinite connected component, and a non-connected graph is one-ended if each of its
connected components is. Such graphs arise naturally in various contexts, such as actions of
amenable groups, and characterizing the combinatorial properties of such graphs has been a
major focus of descriptive graph theory since its inception in the work of Kechris, Pestov.
amd Todorcevic [
KST99
]. See [
Lov12
,
KM16
,
Pik20
] for surveys and introductions to this
topic.
In the special case of probability measure preserving (pmp) graphs (also refered to as
graphings
in the literature), the existence of finitely-ended spanning trees has been well
studied and frequently applied. In the pmp context, a Borel graph is a.e. hyperfinite if and
only if it admits a Borel a.e. spanning tree with at most two ends [
Ada90
,
BLPS01
]. Recently,
Tim´ar [
Tim19
] and independently Conley, Gaboriau, Marks, and Tucker-Drob[
CGMTD
],
refined this to show that the spanning tree can be chosen to have the same number of
ends as the original component. This latter fact already has a number of applications
in probability theory, measurable equidecompositions, and measurable combinatorics; see
[BKS,Tim21b,Tim21a].
Outside of the pmp setting it is no longer true that hyperfinite graphs admit spanning trees
with at most two ends, for example, the Schreier graph of the boundary action of
F2
. The
so-called tail equivalence relation was shown to be hyperfinite by Dougherty, Jackson, and
Kechris in [
DJK94
], and Marquis and Sabok proved hyperfiniteness for boundary actions of
hyperbolic groups in [
MS20
]. Since the constructions of one-ended spanning trees in [
Tim19
]
and [
CGMTD
] both rely on the existence of at most two-ended spanning trees, the methods
from these papers can not be easily adapted to other circumstances. In the present paper we
show that the issue of not having a two-ended spanning tree can typically be overcome. We
give more direct constructions of one-ended spanning trees in most of the natural settings
where hyperfiniteness is guaranteed.
Our main result is the following:
Theorem 1.1.
Let
X
be a Polish space equipped with a Borel probability measure
µ
. Any
locally finite one-ended Borel graph Gon Xadmits a Borel one-ended spanning tree:
(i) on an invariant comeagre set.
(ii)
on an invariant
µ
-conull set if
G
is induced by a free Borel action of an amenable
group.
(iii) everywhere if Gis induced by a free Borel action of a polynomial growth group.
In fact, in each case of Theorem 1.1 we not only construct one-ended spanning trees
but
connected toasts
(particular strong witnesses to hyperfiniteness, precisely defined in
Definition 2.2 and originally introduced by the first author, Kun, and Sabok in [
BKS
]), whose
existence is potentially stronger; see Theorems 3.3,3.5 and 3.16.
As a consequence of Theorem 1.1, we are able to quickly deduce new results on definable
matchings and balanced orientations that were previously known only to hold for pmp graphs.
ONE-ENDED SPANNING TREES AND DEFINABLE COMBINATORICS 3
For example, we prove the following Baire measurable analogue of the main result of [
BKS
].
Here and in the rest of the paper, by
generically
we mean on a G-invariant comeagre Borel
set.
Theorem 1.2.
Any bipartite one-ended
d
-regular Borel graph has a Borel perfect matching
generically.
Previously, the only general classes of bipartite Borel graphs that were known to admit Borel
perfect matchings generically were acyclic or of exponential growth (see the work of Conley
and Miller [
CM17
, Theorem B] and Marks and Unger [
MU16
, Theorem 1.3] respectively).
Moreover, it is known that neither the one-ended assumption nor the
d
-regular assumption
can be dropped from 1.2 due to ergodicity obstructions, even when such graphs admit Borel
fractional perfect matchings (see the work of Conley and Kechris [
CK13
, Section 6] and [
BKS
,
Example 3.1] respectively).
We also show that connected toasts are enough to find
Borel balanced orientations
(i.e. Borel orientations of the edges of a graph so that the in-degree of each vertex is equal to
its outdegree) of even-degree graphs, refining and generalizing [BKS, Corollary 3.7].
Theorem 1.3.
Every even-degree Borel graph that admits a connected toast also admits a
Borel balanced orientation. In particular, every one-ended even-degree Borel graph admits a
Borel balanced orientation generically, and every free Borel action of a superlinear growth
amenable (resp., polynomial growth) group admits a Borel balanced orientation a.e. (resp.,
everywhere).
Again, the irrational rotation graph and its variants show that this result fails for two-ended
graphs. Theorem 1.3 also extends some cases of recent results of Thornton, who showed in
[
Tho22
] that even degree Borel graphs that are pmp (resp., of subexponential growth) admit
Borel orientations with outdegree at most
deg(v)
2
+ 1 a.e. (resp., everywhere), and of Bencs,
Hruˇskov´a, and T´oth, who showed in [
BHT
] that even degree planar lattices have factor of
i.i.d balanced orientations.
1.1. Future work.
In this paper we were able to show that all locally finite one-ended Borel graphs admit
one-ended spanning trees generically, and it was already known that such graphs admit
one-ended spanning trees a.e. if they are hyperfinite and pmp. While we were able to remove
the pmp assumption from the latter result for Schreir graphs of actions of amenable groups,
it remains unclear if we can do this in general for hyperfinite graphs.
Question 1.
Does every locally finite, one-ended, hyperfinite Borel graph also admit a Borel
one-ended spanning tree a.e.?
We have also shown that the existence of connected toasts is enough to ensure that
d
-regular
bipartite Borel graphs admit Borel perfect matchings almost everywhere and generically. It
remains unknown if this is enough to have a Borel perfect matching everywhere, but it was
shown by Gao, Jackson, Krohne, and Seward in [
GJKS
] that the standard Schreir graphs of
Zd
-actions admit Borel perfect matchings, so it seems possible that this fact can be extended.
Question 2.
Does every
d
-regular bipartite Borel graph that admits a connected toast admit
a Borel perfect matching?
4 MATT BOWEN, ANTOINE POULIN, AND JENNA ZOMBACK
Given that the classical K˝onig theorem implies every
d
-regular bipartite graph admits a
proper edge coloring with
d
colors, we could also strengthen Question 2to ask for a Borel
d-coloring. With Theorem 1.2 in mind, this is most likely much easier to obtain generically.
Question 3.
Does every
d
-regular bipartite one-ended Borel graph
G
admit a Borel edge
coloring with dcolors generically?
It is known by the work of the first author and Weilacher [
BW21
] that every such graph
admits a Baire measurable edge coloring with
d
+ 1 colors even when the one-ended condition
is dropped from the above, but as noted already one-endedness is required to find even a
single Baire measurable perfect matching (and unlike edge colorings with d+ 1 colors, each
color in an edge coloring with dcolors is a perfect matching.).
Acknowledgements.
The authors thank Anush Tserunyan for pointing out that in the
Connes-Feldman-Weiss theorem (see [
CFW81
]), unweighted Følner sets suffice in the (weighted)
quasi-pmp setting, and suggested looking at Marks’s proof in [
Mar17
]. We are grateful to
Anton Bernshteyn for pointing out that one can use the construction in Theorem 4.8 (a)
of [
CJM+20
] to produce toasts and not just witnesses to
asi
= 1 in actions of polynomial
growth groups. We thank Antoine Gournay for pointing out that Proposition 3.13 fails for
some amenable groups. Finally, the authors thank their advisors, Marcin Sabok and Anush
Tserunyan, for their support and feedback.
2. Preliminaries
Throughout let (
X, τ
) be a Polish space with Borel probability measure
µ
, and let
Ui
be a
countable basis for the open sets in τ. Let X<ω denote the space of finite subsets of X.
Given a graph G, we fix the following notation.
•V(G) is the set of vertices in G.
•E(G) is the set of edges in G.
•For Y⊆V(G), E(Y) denotes the set of edges in the induced subgraph of G.
•ρG
:
V
(
G
)
2→
[0
,∞
] is the
graph metric
, where
ρG
(
x, y
) =
∞
means that
x
and
y
are in different connected components.
•If C⊂X:
–Bn(C).
.={x∈X:ρG(x, C)≤n}
–∂nC.
.
=
Bn
(
C
)
−C
. In particular, we define the (outer)
boundary
of
C
to be
∂C .
.=∂1C.
–
The boundary visible from infinity,
∂visC,
is the subset of
∂C
so that each vertex
in ∂visCsees an infinite path avoiding C.
Definition 2.1.
If
B⊂V
(
G
) and
n
is a natural number, consider two points related if they
are in
B
and within distance
n
, and take the generated equivalence relation
En
. We say
C
is
an n-component of Bif it is an equivalence class of En.
Given a collection
T ⊆ X<ω,
let
T1⊂ T
denote the family of minimal sets (ordered by
containment), T2denote the family of minimal sets in T \ T1,etc.
2.1. Connected toasts and one-ended spanning trees.
Here we define connected toasts and show that they can be used to produce one-ended
spanning trees.
摘要：

ONE-ENDEDSPANNINGTREESANDDEFINABLECOMBINATORICSMATTBOWEN,ANTOINEPOULIN,ANDJENNAZOMBACKAbstract.Let(X;)beaPolishspacewithBorelprobabilitymeasure;andGalocally niteone-endedBorelgraphonX:WeshowthatGadmitsaBorelone-endedspanningtreegenerically.IfGisinducedbyafreeBorelactionofanamenable(resp.,polynomia...

展开>> 收起<<
ONE-ENDED SPANNING TREES AND DEFINABLE COMBINATORICS MATT BOWEN ANTOINE POULIN AND JENNA ZOMBACK Abstract. Let X be a Polish space with Borel probability measure andGa locally.pdf

共18页,预览4页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：18 页 大小：1.19MB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 18
评分 收藏
分享
立即下载
客服
关注