On Positive Matching Decomposition Conjectures of Hypergraphs

Abstract

In this paper, we prove the conjectures of Gharakhloo and Welker (2023) that the positive matching decomposition number (pmd) of a $3$-uniform hypergraph is bounded from above by a polynomial of degree $2$ in terms of the number of vertices. Moreover, we derive a lower bound for pmd specifically for complete $3$-uniform hypergraphs. Additionally, we obtain an upper bound for pmd of $r$-uniform hypergraphs. For a $r$-uniform hypergraphs $H=(V,E)$ such that $|e_i\cap e_j|\le 1$ for all $e_i,e_j\in E$, we give a characterization of positive matching in terms of strong alternate closed walks. For a specific class of hypergraphs, we classify the radical and complete intersection Lovász$-$Saks$-$Schrijver ideals.

To appear in International Journal of Algebra and Computation