Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs
<|reference_start|>Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs: Significant work has been done on computing the ``average'' optimal solution value for various $\mathsf{NP}$-complete problems using the Erd\"{o}s-R\'{e}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\"{o}s-R\'{e}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=\Theta(2^n)$ then the size of the maximum cardinality matching is $\Omega(n^{\frac12-\gamma})$ for an arbitrary $\gamma >0$. Lastly, we address the gap where $\Omega(1.155^n)=M=o(2^n)$ empirically through computer simulations.<|reference_end|>
@article{sumnicht2024critical,
    title={Critical Thresholds for Maximum Cardinality Matching on General
  Hypergraphs},
    author={Christopher Sumnicht, Jamison W. Weber, Dhanush R. Giriyan, and
  Arunabha Sen},
    journal={arXiv preprint arXiv:2409.09155},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.09155},
    primaryClass={cs.DM math.CO}
}