Boris Pittel
The Ohio State University
Title
On Exact Covers of a Large Set by Small, Randomly Selected Subsets
Abstract
A total number of exact covers of a set $[n]$ by $m$ randomly selected distinct subsets of $[n]$, each of the same fixed cardinality $r$, is analyzed. The problem of identifying a critical number $m_r(n)$ for likely existence of at least one such cover has a long history. For $r=2$, it was solved by Erd\H os and R\'enyi in $1966$. In $2008$, Johansson, Kahn and Vu proved that $m_r(n)$ is of order $n\log n$ for each $r\ge 2$.
Recently, Kahn proved a sharp ``hitting time'' version: with high probability (w.h.p.) a first exact cover in an evolving hyper-graph appears at a random moment w.h.p. asymptotic to $r^{-1} n\log n$. He also found a logarithmically sharp bound for $X_{n,m}(r)$, the total number of exact covers for $m>r^{-1}n\log n$. We show: for $m$ between $n^{3/2}$ and $n^2$, $X_{n,m}(r)$ it is at least of order of $\Bbb E[X_{n,m}(r)]$ with probability $1/2-o(1)$, and for $m$ above $n^2$, $r>2$, $X_{n,m}(r)$ is w.h.p. asymptotic to $\Bbb E[X_{n,m}(r)]$.
