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 hyper-graph 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.