On positive matching decomposition conjectures of hypergraphs

Official URL: https://dx.doi.org/10.1142/S0218196725500390

In this paper, we prove the conjectures of Gharakhloo and Welker [S. Gharakhloo and V. Welker, Hypergraph LSS-ideals and coordinate sections of symmetric tensors, Commun. Algebra 51(8) (2023) 3299–3309, Conjectures 3.5 and 3.6] 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. As an application from an algebraic point of view, we obtain the radical, complete intersection, and prime properties of Lovász–Saks–Schrijver (LSS) ideals of r-uniform hypergraphs. For an r-uniform hypergraphs H = (V,E) such that |ei ∩ ej|≤ 1 for all ei,ej ∈ 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 properties of LSS ideals.