Dirac-type theorems in random hypergraphs (Q2131868)

There has been much interest in recent years in extending results in extremal (hyper)graph theory to the situation where there is randomness about which edges are present. For example, let us consider a perfect matching. For a 2-uniform hypergraph (i.e. a graph) Dirac's theorem implies that if every vertex has degree \(\geq n/2\) (where \(n\geq 3\) is the number of vertices) then there is a perfect matching. More generally, for a \(k\)-uniform hypergraph \(H=(V,E)\) on \(n\) vertices, with \(k\) dividing \(n\) so that a perfect matching is possible, and for \(S\subset V(H)\) let \(\text{deg}_{H}(S)\) be the number of hyperedges containing \(S\) and \(\delta_{d}(H)\) be the minimum, over all \(d\)-element subsets of \(V(H)\) of \(\text{deg}_{H}(S)\). Finally let \(m_{d}(k,n)\) be the smallest \(m\) such that every \(k\)-uniform hypergraph with minimum degree \(\delta_{d}(H)\geq m\) has a perfect matching. The consequence of Dirac's theorem noted above can now be viewed as the statement that \(m_{1}(2,n)\geq n/2\). A natural conjecture now is that in general \[ m_{d}(k,n)=\left( \max \{\frac{1}{2}, 1-\left(1-\frac{1}{k}\right)^{k-d} \}+o(1) \right) \binom{n-d}{k-d}. \] There are constructions showing this is a lower bound, the issue is to get an upper bound. A preliminary result in the important paper under review is that \(m_{d}(k,n)/\binom{n-d}{k-d}\) has a limit \(\mu_{d}(k)\) as \(n\rightarrow\infty\) through the multiples of \(k\). This result -- the existence of Dirac densities -- is harder by some distance than the existence of Turan densities, and the quantities \(\mu_{d}(k)\) are not well understood. However the natural guess for the random version of this result would be as follows. Fix \(\gamma>0\) and positive integers \(d<k\) and let \(n\) be a multiple of \(k\). Let \(0<p(n)<1\) be a probability, and \(H^{k}(n,p)\) be a \(k\)-uniform hypergraph in which each \(k\)-element subset of \(\{1,2,\ldots, n\}\) is present as a hyperedge with probability \(p\) independent of all other \(k\)-element subsets. Then with probability tending to 1 as \(n\rightarrow \infty\), \(H^{k}(n,p)\) has the property that every spanning subhypergraph \(G^{\prime}\) with \(\delta_{d}(G^{\prime})\geq (\gamma+\mu_{d}(k))\binom{n-d}{ k-d}p(n)\) has a perfect matching. The main result of the paper under review is to prove this conjecture for all \(d<k\) subject to \(p\) not being too small. More precisely, again fixing \(\gamma>0\) and \(d<k\), there is \(C\) such that, provided \(p\geq \max \{ n^{-k/2+\gamma}, Cm^{-k+2}\}\), and \(n\) is divisible by \(k\), we do get that the desired property of \(H^{k}(n,p)\) in the previous conjecture holds. One of the key ideas in the difficult proof is to define absorbers -- very roughly, flexible structures which allow us to transform near-spanning structures (which can be found comparatively easily) into full spanning structures - by local modifications -- in a way that can cope with the fact that we know little about the Dirac thresholds \(\mu_{d}(k)\). A similar idea was used by \textit{S. Glock} et al. [J. Comb. Theory, Ser. B 139, 47--127 (2019; Zbl 1428.05246)].