5 papers
Randomized Borel -coloring of digraphs
Anton Bernshteyn, Edward Hou, Forte Shinko +1
Let be a Borel digraph with maximum out-degree . We show that admits a random Borel -coloring for which every edge is almost surely not monochroma…
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 properties…
Embedding Borel graphs into grids of asymptotically optimal dimension
Anton Bernshteyn, Jing Yu
Let be a Borel graph all of whose finite subgraphs embed into the -dimensional grid with diagonals. We show that then itself admits a Borel embedding into the Schreier g…
A linear-time algorithm for -edge-coloring
Anton Bernshteyn, Abhishek Dhawan
We present a randomized algorithm that, given a constant , outputs a proper -edge-coloring of an -edge simple graph of maximum degree in tim…
Borel line graphs
James Anderson, Anton Bernshteyn
We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph as…