检索结果-内蒙古大学图书馆

Basic orders in descriptive combinatorics

TOPOLOGY AND ITS APPLICATIONS 2023年 323卷

作者： Todorcevic, Stevo Univ Toronto Dept Math Toronto ON M5S 2E4 Canada Inst Math Jussieu Paris France SANU Matemat Inst Belgrade Serbia

Basic orders were originally introduced in order to illuminate Tukey theory of directed sets and in particular explain the phenomenon that Tukey reductions between definable directed sets tend to be definable themselves. We show here that they can be also used to calibrate between different properties of topological spaces and topological groups. (c) 2022 Elsevier B.V. All rights reserved.

关键词： descriptive combinatorics Basic orders

来源：评论

学校读者我要写书评

暂无评论

Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics

引用

ADVANCES IN MATHEMATICS 2023年第1期431卷

作者： Grebik, Jan Rozhon, Vaclav Masaryk Univ Fac Informat Botanicka 68A Brno 60200 Czech Republic UCLA Dept Math Los Angeles CA 90095 USA Univ Warwick Coventry Ireland Swiss Fed Inst Technol Zurich Switzerland

We present an intimate connection among the following fields: (a) distributed local algorithms: coming from the area of computer science, (b) finitary factors of iid processes: coming from the area of analysis of randomized processes, (c) descriptive combinatorics: coming from the area of combinatorics and measure theory. In particular, we study locally checkable problems on grids from all three perspectives. Most of our results are for perspective (b) where we prove time hierarchy theorems similar to those known in the field (a) Chang and Pettie (2017) [16]. This approach, which borrows techniques from fields (a) and (c), implies a number of results about the possible complexities of finitary factor solutions. Among others, it answers three open questions of Holroyd et al. (2017) [46] or the more general question of Brandt et al. Brandt (2017) [9] who asked for a formal connection between the fields (a) and (b). In general, we hope that our treatment will help to view all three perspectives as a part of a common theory of locality, in which we follow the insightful paper of Bernshteyn (2023) [6]. & COPY;2023 Elsevier Inc. All rights reserved.

关键词： descriptive combinatorics Local algorithms Finitary factors

来源：评论

学校读者我要写书评

暂无评论

Measurable versions of the Lovasz Local Lemma and measurable graph colorings

引用

ADVANCES IN MATHEMATICS 2019年 353卷 153-223页

作者： Bernshteyn, Anton Univ Illinois Dept Math Champaign IL USA Carnegie Mellon Univ Dept Math Sci 5000 Forbes Ave Pittsburgh PA 15213 USA

In this paper we investigate the extent to which the Lovasz Local Lemma (an important tool in probabilistic combinatorics) can be adapted for the measurable setting. In most applications, the Lovasz Local Lemma is used to produce a function f : X -> Y with certain properties, where X is some underlying combinatorial structure and Y is a (typically finite) set. Can this function f be chosen to be Borel or mu-measurable for some probability Borel measure on X (assuming that X is a standard Borel space)? In the positive direction, we prove that if the set of constraints put on f is, in a certain sense, "locally finite," then there is always a Borel choice for f that is "epsilon-close" to satisfying these constraints, for any epsilon > 0. Moreover, if the combinatorial structure on X is "induced" by the [0;1]-shift action of a countable group Gamma, then, even without any local finiteness assumptions, there is a Borel choice for f which satisfies the constraints on an invariant conull set (i.e., with epsilon = 0). A direct corollary of our results is an upper bound on the measurable chromatic number of the graph an generated by the shift action of the free group F-n that is asymptotically tight up to a factor of at most 2 (which answers a question of Lyons and Nazarov). On the other hand, our result for structures induced by measure-preserving group actions is, at least for amenable groups, sharp in the following sense: a probability measure-preserving action of a countably infinite amenable group satisfies the measurable version of the Lovasz Local Lemma if and only if it admits a factor map to the [0;1]-shift action. To prove this, we combine the tools of the Ornstein-Weiss theory of entropy for actions of amenable groups with concepts from computability theory, specifically, Kolmogorov complexity. (C) 2019 Elsevier Inc. All rights reserved.

关键词： descriptive combinatorics Graph coloring Measurable Lovasz Local Lemma

来源：评论

学校读者我要写书评

暂无评论

Equitable colourings of Borel graphs

引用

FORUM OF MATHEMATICS PI 2021年 9卷 e12-e12页

作者： Bernshteyn, Anton Conley, Clinton T. Georgia Inst Technol Sch Math 686 Cherry St NW Atlanta GA 30332 USA Carnegie Mellon Univ Dept Math Sci Wean Hall 6113 Pittsburgh PA 15213 USA

Hajnal and Szemeredi proved that if G is a finite graph with maximum degree., then for every integer k >= Delta + 1, G has a proper colouring with k colours in which every two colour classes differ in size at most by 1;such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree Delta, then for each k >= Delta + 1, G has a Borel proper k-colouring in which every two colour classes are related by an element of the Borel full semigroup of G. In particular, such colourings are equitable with respect to every G-invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable Delta-colourings of graphs with small average degree. Namely, we prove that if Delta >= 3, G does not contain a clique on Delta + 1 vertices and mu is an atomless G-invariant probability measure such that the average degree of G with respect to mu is at most Delta/5, then G has a mu-equitable Delta-colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks' theorem due to Kostochka and Nakprasit.

关键词： equitable colouring Borel graph descriptive combinatorics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：