Anton Bernshteyn

Email: bernshteyn ~at~ math.ucla.edu
Office: MS5372

Welcome!

I am an Assistant Professor in the Department of Mathematics at UCLA. I am a member of the Mathematical Logic and Combinatorics research groups.

You can find my CV here (last update: Jan 31, 2025). Here's my Math Genealogy entry.

Will Adkisson and I are co-oganizing the Logic Seminar/Colloquium at UCLA. Click here to sign up for the mailing list and shoot either me or Will an email if you'd like to give a talk!

You can find a calendar of logic events at UCLA at the bottom of this page.


Research

My main areas of research are descriptive set theory and combinatorics, with an emphasis on their interactions and on connections to other fields such as computer science and dynamical systems.

Papers and Preprints

  1. With Katalin Berlow, Clark Lyons, and Felix Weilacher. Separating complexity classes of LCL problems on grids. Preprint.
  2. With Jing Yu. Borel Local Lemma: arbitrary random variables and limited exponential growth. Preprint.
  3. With József Balogh, Michelle Delcourt, Asaf Ferber, and Huy Tuan Pham. Sunflowers in set systems with small VC-dimension. Preprint.
  4. With Hemanshu Kaul, Jeffrey A. Mudrock, and Gunjan Sharma. On strongly and robustly critical graphs. Preprint.
  5. With Jing Yu. Embedding Borel graphs into grids of asymptotically optimal dimension. Preprint.
  6. With Abhishek Dhawan. A linear-time algorithm for (1+ε)Δ-edge-coloring. Preprint.
  7. With Eugene Lee and Evelyne Smith-Roberge. Weak degeneracy of planar graphs. Preprint.
  8. With Felix Weilacher. Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index. Preprint.
  9. With Abhishek Dhawan. Fast algorithms for Vizing's theorem on bounded degree graphs. Preprint.
  10. With Jing Yu. Large-scale geometry of Borel graphs of polynomial growth. Preprint.
  11. With James Anderson and Abhishek Dhawan. Coloring graphs with forbidden almost bipartite subgraphs. Preprint.
  12. With Daniel Dominik, Hemanshu Kaul, and Jeffrey A. Mudrock. DP-coloring of graphs from random covers. Random Structures and Algorithms (to appear).
  13. With James Anderson. Borel line graphs. Journal of Symbolic Logic (to appear).
  14. With Abhishek Dhawan. Borel Vizing's theorem for graphs of subexponential growth. Proceedings of the American Mathematical Society (2025).
  15. Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics. Inventiones Mathematicae (2023).
  16. With Eugene Lee. Weak degeneracy of graphs. Journal of Graph Theory (2023). [See this paper for a correct proof of Theorem 1.4]
  17. Equivariant maps to subshifts whose points have small stabilizers. Journal of Modern Dynamics (2023).
  18. With Tyler Brazelton, Ruijia Cao, and Akum Kang. Counting colorings of triangle-free graphs. Journal of Combinatorial Theory, Series B (2023).
  19. Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms. Advances in Mathematics (2023).
  20. With James Anderson and Abhishek Dhawan. Coloring graphs with forbidden bipartite subgraphs. Combinatorics, Probability and Computing (2023).
  21. Descriptive combinatorics and distributed algorithms. Notices of the American Mathematical Society, Feature Article (2022)
  22. Borel fractional colorings of Schreier graphs. Annales Henri Lebesgue (2022).
  23. With Eugene Lee. Searching for an intruder on graphs and their subdivisions. Electronic Journal of Combinatorics (2022).
  24. With Michelle Delcourt and Anush Tserunyan. Independent sets in algebraic hypergraphs. Journal of the European Mathematical Society (2022).
  25. Local coloring problems on smooth graphs. Fundamenta Mathematicae (2022).
  26. A fast distributed algorithm for (Δ+1)-edge-coloring. Journal of Combinatorial Theory, Series B (2022).
  27. With Clinton T. Conley. Equitable colorings of Borel graphs. Forum of Mathemarics, Pi (2021).
  28. On Baire measurable colorings of group actions. Ergodic Theory and Dynamical systems (2021).
  29. A short proof of Bernoulli disjointness via the Local Lemma. Proceedings of the American Mathematical Society (2020).
  30. Ergodic theorems for the shift action and pointwise versions of the Abért–Weiss theorem. Israel Journal of Mathematics (2020).
  31. With Omid Khormali, Ryan R. Martin, Jonathan Rollin, Danny Rorabaugh, Songling Shan, and Andrew J. Uzzell. Regular colorings in regular graphs. Discussiones Mathematicae Graph Theory (2020).
  32. With Alexandr Kostochka and Xuding Zhu. Fractional DP-colorings of sparse graphs. Journal of Graph Theory (2020).
  33. Multiplication of weak equivalence classes may be discontinuous. Transactions of the American Mathematical Society (2019).
  34. Building large free subshifts using the Local Lemma. Groups, Geometry, and Dynamics (2019).
  35. With Alexandr Kostochka. DP-colorings of hypergraphs. European Journal of Combinatorics (2019).
  36. With Michael Tait. Improved lower bound for difference bases. Journal of Number Theory (2019).
  37. Measurable versions of the Lovász Local Lemma and measurable graph colorings. Advances in Mathematics (2019).
  38. The Johansson–Molloy Theorem for DP-coloring. Random Structures and Algorithms (2019).
  39. With Michelle Delcourt, Henry Towsner, and Anush Tserunyan. A short nonalgorithmic proof of the containers theorem for hypergraphs. Proceedings of the American Mathematical Society (2019).
  40. With Alexandr Kostochka. On differences between DP-coloring and list coloring (in Russian). Matematicheskie Trudy (2018); English version.
  41. With Alexandr Kostochka. Sharp Dirac's theorem for DP-critical graphs. Journal of Graph Theory (2018).
  42. With Alexandr Kostochka and Xuding Zhu. DP-colorings of graphs with high chromatic number. European Journal of Combinatorics (2017).
  43. The Local Cut Lemma. European Journal of Combinatorics (2017).
  44. With Alexandr Kostochka and Sergei Pron. On DP-coloring of graphs and multigraphs (in Russian). Siberian Mathematical Journal (2017); English version.
  45. The asymptotic behavior of the correspondence chromatic number. Discrete Mathematics (2016).
  46. New bounds for the acyclic chromatic index. Discrete Mathematics (2016).
  47. With Alexandr Kostochka. On the number of edges in a graph with no (k+1)-connected subgraphs. Discrete Mathematics (2016).
  48. 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs (in Russian). Discrete Analysis and Operations Research (2014).
  49. With Nikolay V. Shilov. Robots in Space Multi-agent Problem: complexity, information and cryptographic aspects (in Russian). Modeling and Analysis of Information Systems (2013).

Other Writing


Mentoring

Past advised students

Past supervised postdocs

REUs, GRAs, etc.

  • Cameron Chang, Horace Fusco, Sarah Peterson, Faren Roth, and Henry Simmons, Georgia Tech REU, Summer 2022
  • Manuel Fernandez, GRA, Spring–Summer 2022
  • Tyler Brazelton, Ruijia Cao, and Akum Kang, undergraduate research project, Summer 2021

Teaching

Current Teaching

Directed Reading in Secriptive Set Theory (MATH 596).

Highlights of Past Teaching

At UCLA:
  • 2024, Fall Graph Theory (MATH 180).
At Georgia Tech:
  • 2024, Spring Probabilistic Combinatorics (MATH 7018) and Set Theory (MATH 8803).
  • 2023, Fall Applied Combinatorics (MATH 3012).
  • 2023, Spring Probabilistic Combinatorics (MATH 7018).
  • 2022, Fall Applied Combinatorics (MATH 3012) and Introduction to Graph Theory (MATH 4022).
  • 2022, Spring Probabilistic Combinatorics (MATH 7018).
  • 2021, Fall Descriptive Combinatorics (MATH 8803).
  • 2021, Summer Undergraduate Research (MATH-2699 and MATH-4699).
  • 2021, Spring Combinatorial Analysis (MATH 4032).
  • 2020, Fall Introduction to Graph Theory (MATH 4022).
At CMU:
  • 2019, Fall Combinatorics (21-301) and Algebraic Structures (21-373).
  • 2019, Summer Research Topics in Combinatorics (21-499).
  • 2019, Spring Set Theory (21-329).
  • 2018, Fall Linear Algebra (21-341).
At UIUC: