Width of a hypergraph
In graph theory, the width is a property of a hypergraph. Given a hypergraph H = (V, E), we say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K.[1] The width of H is the smallest size of a subset of E that pins E.[2] The matching width of H is the maximum, over all matchings M in H, of a subset of E that pins M.[3]
Since E contains all matchings in E, the width of H is obviously at least as large as the matching-width of H.
The width of a hypergraph is used in Hall-type theorems for hypergraphs.
References
- ^ Aharoni, Ron; Haxell, Penny (2000). "Hall's theorem for hypergraphs". Journal of Graph Theory. 35 (2): 83–88. doi:10.1002/1097-0118(200010)35:23.0.CO;2-V. ISSN 1097-0118.
- ^ Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912.
- ^ Aharoni, Ron (2001-01-01). "Ryser's Conjecture for Tripartite 3-Graphs". Combinatorica. 21 (1): 1–4. doi:10.1007/s004930170001. ISSN 1439-6912.