Michael Simkin

activity

20172019

collaborators

3 papers

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…

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

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