Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs

Abstract

Significant work has been done on computing the ``average'' optimal solution value for various $\mathsf{NP}$-complete problems using the Erdös-Rényi model to establish \emph{critical thresholds}. Critical thresholds define narrow bounds for the optimal solution of a problem instance such that the probability that the solution value lies outside these bounds vanishes as the instance size approaches infinity. In this paper, we extend the Erdös-Rényi model to general hypergraphs on $n$ vertices and $M$ hyperedges. We consider the problem of determining critical thresholds for the largest cardinality matching, and we show that for $M=o(1.155^n)$ the size of the maximum cardinality matching is almost surely 1. On the other hand, if $M=\hat{I}˜(2^n)$ then the size of the maximum cardinality matching is $\hat{I}\text{c◯}(n^{\frac{1}{2}-{\hat{I}}^3})$ for an arbitrary ${\hat{I}}^3>0$. Lastly, we address the gap where $\hat{I}\text{c◯}(1.155^n)=M=o(2^n)$ empirically through computer simulations.