Michael Simkin

activity

20172022

collaborators

Showing math.COShow all

5 papers · 1 filter

math.CO2022

Threshold for Steiner triple systems

Ashwin Sah, Mehtaab Sawhney, Michael Simkin

We prove that with high probability $G^{(3)} (n, n^{- 1 + o (1)})$ contains a spanning Steiner triple system for $n \equiv 1, 3 (mod 6)$ , establishing the exponent for the thresho…

math.CO2021

A lower bound for the $n$ -queens problem

Zur Luria, Michael Simkin

The $n$ -queens puzzle is to place $n$ mutually non-attacking queens on an $n \times n$ chessboard. We present a simple two stage randomized algorithm to construct such configuratio…

math.CO2019

A randomized construction of high girth regular graphs

Nati Linial, Michael Simkin

We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k \geq 3$ and $c \in (0, 1)$ be fixed. Let $n \in N$ be even and set $g = c \log_…

math.CO2018

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Roman Glebov, Zur Luria, Michael Simkin

Consider the random process in which the edges of a graph $G$ are added one by one in a random order. A classical result states that if $G$ is the complete graph $K_{2 n}$ or the co…

math.CO2017

$(n, k, k - 1)$ -Steiner Systems in Random Hypergraphs

Michael Simkin

Let $H$ be a random $k$ -uniform $n$ -vertex hypergraph where every $k$ -tuple belongs to $H$ independently with probability $p$ . We show that for some $ε_{k} > 0$ , if $p \geq…

Threshold for Steiner triple systems

A lower bound for the n-queens problem

A randomized construction of high girth regular graphs

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

(n,k,k−1)-Steiner Systems in Random Hypergraphs

A lower bound for the $n$ -queens problem

$(n, k, k - 1)$ -Steiner Systems in Random Hypergraphs