تقرير
Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs
| العنوان: | Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs |
|---|---|
| المؤلفون: | Sumnicht, Christopher, Weber, Jamison W., Giriyan, Dhanush R., Sen, Arunabha |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Mathematics - Combinatorics |
| الوصف: | 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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2409.09155 |
| رقم الأكسشن: | edsarx.2409.09155 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |