Anton Bernshteyn

collaborators

3 papers

math.CO2026

Borel Local Lemma: arbitrary random variables and limited exponential growth

Anton Bernshteyn, Jing Yu

The LovÃ¡sz Local Lemma (the LLL for short) is a powerful tool in probabilistic combinatorics that is used to verify the existence of combinatorial objects with desirable propertie…

math.CO2025

Embedding Borel graphs into grids of asymptotically optimal dimension

Anton Bernshteyn, Jing Yu

Let $G$ be a Borel graph all of whose finite subgraphs embed into the $d$ -dimensional grid with diagonals. We show that then $G$ itself admits a Borel embedding into the Schreier g…

cs.DS2025

A linear-time algorithm for $(1 + I^µ) I^$ -edge-coloring

Anton Bernshteyn, Abhishek Dhawan

We present a randomized algorithm that, given a constant $I^µ > 0$ , outputs a proper $(1 + I^µ) I^$ -edge-coloring of an $m$ -edge simple graph $G$ of maximum degree $I^ \geq 1/ I^µ$ in $O(m)…

Borel Local Lemma: arbitrary random variables and limited exponential growth

Embedding Borel graphs into grids of asymptotically optimal dimension

A linear-time algorithm for (1+I^µ)I^-edge-coloring

A linear-time algorithm for $(1 + I^µ) I^$ -edge-coloring