Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Anton Bernshteyn"'
Autor:
Anton Bernshteyn, Clinton T. Conley
Publikováno v:
Forum of Mathematics, Pi, Vol 9 (2021)
Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $\Delta $ , then for every integer $k \geq \Delta +1$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $1$ ; such
Externí odkaz:
https://doaj.org/article/4706ffbe755c4067b047c9f3a42482b6
Publikováno v:
Combinatorics, Probability and Computing. 32:45-67
A conjecture of Alon, Krivelevich and Sudakov states that, for any graph $F$ , there is a constant $c_F \gt 0$ such that if $G$ is an $F$ -free graph of maximum degree $\Delta$ , then $\chi\!(G) \leqslant c_F \Delta/ \log\!\Delta$ . Alon, Krivelevich
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3f26a8b2b6aa00a6cb9935780781b8a5
https://doi.org/10.1017/s0963548322000104
https://doi.org/10.1017/s0963548322000104
Autor:
Anton Bernshteyn
Publikováno v:
Fundamenta Mathematicae. 256:333-339
We construct a smooth locally finite Borel graph $G$ and a local coloring problem $\Pi$ such that $G$ has a coloring $V(G) \to \mathbb{N}$ that solves $\Pi$, but no such coloring can be Borel.
Comment: 5 pages, 1 figure
Comment: 5 pages, 1 figure
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::730fcb935de0d7447143ae6662b9c5fc
https://doi.org/10.4064/fm6-5-2021
https://doi.org/10.4064/fm6-5-2021
Autor:
Anton Bernshteyn
Publikováno v:
Journal of Combinatorial Theory, Series B. 152:319-352
We present a deterministic distributed algorithm in the LOCAL model that finds a proper ( Δ + 1 ) -edge-coloring of an n-vertex graph of maximum degree Δ in poly ( Δ , log n ) rounds. This is the first nontrivial distributed edge-coloring algo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::59540d8c37e6c5773aef39b34e26c8e6
https://doi.org/10.1016/j.jctb.2021.10.004
https://doi.org/10.1016/j.jctb.2021.10.004
Autor:
Anton Bernshteyn
This is a draft of an article to appear in the October 2022 issue of the Notices of the AMS. In this survey article we explore a fascinating area called descriptive combinatorics and its recently discovered connections to distributed algorithms -- a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8328acc4b0533d82b2cd9c9550f1f8f5
http://arxiv.org/abs/2208.02903
http://arxiv.org/abs/2208.02903
Autor:
Anton Bernshteyn
Publikováno v:
Proceedings of the American Mathematical Society. 148:5235-5240
Recently, Glasner, Tsankov, Weiss, and Zucker showed that if $\Gamma$ is an infinite discrete group, then every minimal $\Gamma$-flow is disjoint from the Bernoulli shift $2^\Gamma$. Their proof is somewhat involved; in particular, it invokes separat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c132672d56f5389007ccdafbde673d57
https://doi.org/10.1090/proc/15151
https://doi.org/10.1090/proc/15151
Autor:
Anton Bernshteyn, Eugene Lee
Motivated by the study of greedy algorithms for graph coloring, we introduce a new graph parameter, which we call weak degeneracy. By definition, every $d$-degenerate graph is also weakly $d$-degenerate. On the other hand, if $G$ is weakly $d$-degene
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1009d9e3a3726932352de617316dcdf7
http://arxiv.org/abs/2111.05908
http://arxiv.org/abs/2111.05908
By a theorem of Johansson, every triangle-free graph $G$ of maximum degree $\Delta$ has chromatic number at most $(C+o(1))\Delta/\log \Delta$ for some universal constant $C > 0$. Using the entropy compression method, Molloy proved that one can in fac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5c549c6a504f6acc3ab0a0a2b696bdc1
http://arxiv.org/abs/2109.13376
http://arxiv.org/abs/2109.13376
Autor:
Anton Bernshteyn
Publikováno v:
Israel Journal of Mathematics. 235:255-293
Let Γ be a countably infinite group. A common theme in ergodic theory is to start with a probability measure-preserving (p.m.p.) action Γ ↷ (X, μ) and a map f ∈ L1 (X, μ), and to compare the global average ∫ f dμ of f to the pointwise aver
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6d87e5675efa6955763031fc26887547
https://doi.org/10.1007/s11856-019-1957-4
https://doi.org/10.1007/s11856-019-1957-4
Autor:
Anton Bernshteyn
Publikováno v:
Advances in Mathematics. 353:153-223
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 →
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::672928a6c6b1290ea04db74d62007bd0
https://doi.org/10.1016/j.aim.2019.06.031
https://doi.org/10.1016/j.aim.2019.06.031