Michael Simkin's Homepage

Welcome!

I am an Instructor (≈ departmental postdoc) in Applied Mathematics at MIT's Department of Mathematics.

I completed my PhD at the Einstein Institute of Mathematics and the Federmann Center for the Study of Rationality at the Hebrew University of Jerusalem, Israel. I had the great fortune of being supervised by Prof. Nati Linial. Following my PhD, I spent three years as a postdoctoral fellow at Harvard's Center of Mathematical Sciences and Applications.

I am interested in using randomized algorithms to answer existential, enumerative, and structural questions in combinatorics. I especially enjoy thinking about combinatorial designs, and random graph and hypergraph thresholds.

Here is my curriculum vitae.

Research Highlights

Here is a Quanta magazine article about my work on the $n$-queens problem. And here is an article in the Harvard Gazette.

Quanta magazine also covered my joint work (to appear in Annals of Mathematics) with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney, which resolved a 1973 conjecture of Erdős on the existence of high girth Steiner triple systems.

Contact Information

Email: msimkin followed by @ followed by mit.edu
Office: 2-347, 77 Massachusetts Ave.

My Favorite Open Problem

An order-$n$ Latin square is an $n \times n$ matrix in which every column and every row contains all the values from $[n]$. This is equivalent to an $n \times n \times n$ $\{0,1\}$-array in which every row, column, and "shaft" contains a single $1$. Let $A$ be a random $n \times n \times n$ $\{0,1\}$-array in which the $n^3$ entries are independent random variables that equal $1$ with probability $p$. What is the threshold function $p(n)$ above which $A$ contains a Latin square with high probability?
Update (April 2022): Ashwin Sah, Mehtaab Sawhney, and I have determined this threshold up to a subpolynomial factor!
Update (June 2022): Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abshishek Methuku, and Deryk Osthus have determined the threshold up to a logarithmic factor!
Update (December 2022): Peter Keevash and, independently, Vishesh Jain and Huy Tuan Pham have determined the threshold up to a constant factor! Congratulations! Some questions remain, such as finding the correct constant or proving a hitting time result. These will likely require significant new ideas. However, as far as my original intent when posing the question, it has now been completely answered! Stay tuned for a new problem...

At MIT:

Fall 2023: Combinatorial Analysis (instructor of record): First undergraduate course in discrete mathematics.
Spring 2024: Probability and Random Variables (teaching Assistant).

I have TAed the following courses at Hebrew University:

Spring 2020: Discrete Mathematics: First year undergraduate course for math and CS students.
Spring 2019: Linear Algebra 2: Second undergraduate course in linear algebra.
Spring 2018: Linear Algebra 1: First year undergraduate course in linear algebra.
Fall2019, Fall 2018, Fall 2017, and Fall 2016: Mathematical Tools in Computer Science: Graduate course for CS students. Topics include:
- Probability (emphasizing the probabilistic method).
- Linear algebra: Spectral theorems and singular value decomposition for real matrices.
- Markov chains.
- Linear programming.
Spring 2017 and Fall 2015: Topics in Analysis for Computer Science Students: Second year undergraduate course for CS students. Topics include:
- Convexity.
- Norms, inner products, Banach and Hilbert spaces.
- Notions of convergence for function sequences.
- Fourier series.
Spring 2016 and Spring 2015: Infinitesimal Calculus 2 for Computer Science Students: Second course in undergraduate calculus.

Published / Accepted
- High-girth Steiner triple systems, with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney. Annals of Mathematics, to appear in November 2024.
- The number of $n$-queens configurations. Advances in Mathematics 427: 109127 (2023).
- Threshold for Steiner triple systems, with Ashwin Sah and Mehtaab Sawhney. Geometric and Functional Analysis (GAFA) 33: 1141-1172 (2023).
- Substructures in Latin squares, with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney. Israel Journal of Mathematics 256: 363-416 (2023).
- A lower bound for the $n$-queens problem, with Zur Luria. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022.
- What is learned in knowledge graph embedding, Michael R. Douglas, Michael Simkin, Omri Ben-Eliezer, Tianqi Wu, Peter Chin, Trung V. Dang, Andrew Wood. Complex Networks & their Applications 2021.
- Perfect matchings in random subgraphs of regular bipartite graphs, with Roman Glebov and Zur Luria. Journal of Graph Theory 2020; 97: 208-231.
- A randomized construction of high girth regular graphs, with Nati Linial. Random Structures & Algorithms 2021; 58: 345-369.
- On the threshold problem for Latin boxes, with Zur Luria. Random Structures & Algorithms 2019; 55: 926-949.
- Monotone subsequences in high-dimensional permutations, with Nati Linial. Combinatorics, Probability and Computing 27.1 (2018): 69-83.
Preprints
- Ramsey and Turán numbers of sparse hypergraphs, with Jacob Fox, Maya Sankar, Jonathan Tidor, and Yunkun Zhou. arXiv preprint 2401.00359 (2024).
- A toolkit for robust thresholds, with Huy Tuan Pham, Ashwin Sah, and Mehtaab Sawhney. arXiv preprint arXiv:2210.03064 (2022).
- $(n,k,k-1)$-Steiner systems in random hypergraphs. arXiv preprint arXiv:1711.01975 (2017).
Theses and Notes
- Finding structure with randomness. My PhD thesis, supervised by Prof. Nati Linial.
- Methods for analyzing random designs. Notes for a lecture I gave at the Israel Institute for Advanced Studies in March, 2018. The highlight is a proof, using Matthew Kwan's beautiful method, that almost every Steiner triple system on $n$ vertices contains at least $\left(1 - o(1) \right)n^2/24$ Pasch configurations. As far as I know this result is new, even if not ground-breaking.
- Construction and enumeration with the probabilistic method. Notes for a lecture I gave at the HUJI math department's student seminar in Spring 2017. I gave two examples of probabilistic tools in combinatorics: Erdős's lower bound on the diagonal Ramsey numbers, and an application of the Linial-Luria entropy method to bound from above the number of order-$n$ Latin squares.
- Random-turn and Richman games. My MSc thesis, supervised by Prof. Gil Kalai. In which the following question is considered: Many games (e.g. Tic-Tac-Toe, chess) employ a mechanism where players alternate taking turns. How are games affected if, instead of simple alternation, each turn is assigned randomly as we go along? What if before each turn there is an auction for the privilege of taking the next turn?
- Self-similar structures near the edges of strained elastic sheets. My Amirim (undergraduate honors) thesis, supervised by Prof. Raz Kupferman. Tear a plastic bag. Go ahead! Do it! Now examine the newly-created edge. Most likely you'll see wave-like patterns. In this project I numerically tested a proposed mathematical explanation for the phenomenon.
Slides
- Matchings and Latin squares. Slides for a talk given at the Rationality Center's Caesarea retreat (2018). The lecture is intended for a broad academic audience. I motivate the view of Latin squares as high-dimensional matchings, and explain the high-dimensional Erdős-Szekeres theorem.