Matching criticality in intersecting hypergraphs

Abstract

The transversal number τ(H) of a hypergraph H is the minimum cardinality of a set of vertices that intersects all edges of H. The matching number α′(H) of H is the maximum cardinality of a matching in H. A hypergraph H is intersecting if and only if α′(H) = 1. For an intersecting hypergraph H of rank r without isolated vertex, clearly τ(H) ≤ r. H is called 1-special if τ(H) = r, and H is maximal 1- special if H is 1-special and adding any missing r-edge to H increases the matching number. n²(r) and n³(r) are the maximum orders of a 1-special hypergraph and a maximal 1-special hypergraph, respectively. Furthermore, the intersecting hypergraph H is called 1-edge-critical if for any e ∈ E(H) and any v ∈ e, v-shrinking e increases the matching number; H is called 1-vertex-critical if for any v ∈ V (H) deleting the vertex v and v-shrinking all edges incident with v increases the matching number. n⁴(r) and n⁵(r) are the maximum orders of a 1-edge-critical hypergraph and a 1-vertex-critical hypergraph, respectively. The intersecting hypergraphs, as defined above, are said to be matching critical [M.A. Henning and A. Yeo, Quaest. Math. 37 (2014), 127–138]. In this paper we study the extremal behavior of matching critical intersecting hypergraphs. We show that n²(r) = n³(r) and n⁴(r) = n⁵(r) for all r ≥ 2, which partly answers an open problem on matching critical intersecting hypergraphs posed by Henning and Yeo. We also give a strengthening of the result n⁴(r) = n⁵(r) for intersecting r-uniform hypergraphs.

Mathematics Subject Classification (2010): 05C65, 05C70.

Key words: Hypergraph, intersecting hypergraph, matching, transversal.