Width of a hypergraph
In graph theory, there are two related properties of a hypergraph that are called its "width". 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] Then:
- The width of H, denoted w(H), is the smallest size of a subset of E that pins E.[2]
- The matching width of H, denoted mw(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, for all H: w(H) ≥ mw(H).
The width of a hypergraph is used in Hall-type theorems for hypergraphs.
Examples
Let H be the hypergraph with vertex set V = {A,B; a,b} and edge set:
E = { {A,a}, {B,b}, {A,b}, {B,a} }
The widths of H are:
- w(H) = 2, since E is pinned e.g. by the set { {A,a}, {B,b} }, and cannot be pinned by any smaller set.
- mw(H) = 1, since every matching can be pinned by a single edge. There are two matchings: {{A,a}, {B,b}} is pinned e.g. by { {A,b} }, and { {A,b}, {B,a} } is pinned e.g. by { {A, a} }.
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.