Michael Simkin's Homepage

Welcome!

I am a postdoctoral fellow at Harvard University's Center of Mathematical Sciences and Applications.

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.

I am interested in high-dimensional combinatorics, especially random high-dimensional permutations and designs. I also enjoy thinking about random (hyper) graphs and (hyper) graph processes. Lately I have been applying functional-analytic methods to study these objects.

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

Here is my curriculum vitae.

Contact Information

Email: msimkin followed by @ followed by cmsa.fas.harvard.edu
Office: 20 Garden St. 115C.

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!

I have TAed the following courses, all 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
- 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
- Threshold for Steiner triple systems, with Ashwin Sah and Mehtaab Sawhney. arXiv preprint arXiv:2204.03964 (2022).
- Substructures in Latin squares, with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney. arXiv preprint arXiv:2202.05088 (2022).
- High-girth Steiner triple systems, with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney. arXiv preprint arXiv:2201.04554 (2022).
- The number of $n$-queens configurations. arXiv preprint arXiv:2107.13460 (2021).
- $(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.