8 papers
Measurable matchings in unbalanced graphs
Anton Bernshteyn, Matt Bowen, Felix Weilacher
Let be a locally finite multigraph that is bipartite and "unbalanced," meaning that it has a nontrivial bipartition with for all $x…
On strongly and robustly critical graphs
Anton Bernshteyn, Hemanshu Kaul, Jeffrey A. Mudrock +1
In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. In particular, critical and list-critical graphs occupy a promin…
Fast algorithms for Vizing's theorem on bounded degree graphs
Anton Bernshteyn, Abhishek Dhawan
Vizing's theorem states that every graph of maximum degree can be properly edge-colored using colors. The fastest currently known -edge-coloring algorithm…
Weak Degeneracy of Planar Graphs
Anton Bernshteyn, Eugene Lee, Evelyne Smith-Roberge
The weak degeneracy of a graph is a numerical parameter that was recently introduced by the first two authors with the aim of understanding the power of greedy algorithms for g…
Coloring graphs with forbidden almost bipartite subgraphs
James Anderson, Anton Bernshteyn, Abhishek Dhawan
Alon, Krivelevich, and Sudakov conjectured in 1999 that for every finite graph , there exists a quantity such that whenever is a…
Large-scale geometry of Borel graphs of polynomial growth
Anton Bernshteyn, Jing Yu
We study graphs of polynomial growth from the perspective of asymptotic geometry and descriptive set theory. The starting point of our investigation is a theorem of Krauthgamer and…