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} }.

Characterizations

The disjointness graph of H, denoted D(H), is a graph where each edge in H is a vertex in D(H), and every two disjoint edges in H are adjacent in D(H). The matchings in H correspond to the cliques in D(H). Meshulam[2] characterized the widths of a hypergraph H in terms of the properties of D(H). For any positive integer r:

  • w(H) > r if and only if D(H) satisfies a property called P(r,∞), which means that every set of r vertices in D(H) have a common neighbor. This is because w(H) > r iff H has no pinning-set of size r, iff for every subset of r edges of H there is an edge that is not pinned by it, iff every subset of r edges of H has a common neighbor in D(H).
  • mw(H) > r if and only if D(H) satisfies a property called P(r,0), which means that every set of r vertices in D(H) have a common neighbor, and in addition, there is a clique C in D(H) which contains a common neighbor of every such set.

The line graph of H, denoted L(H), is a graph where each edge in H is a vertex in L(H), and every two intersecting edges in H are adjacent in L(H). The matchings in H correspond to the independent sets in L(H). Since L(H) is the complement of D(H), the above characterization can be translated to L(H):

  • w(H) > r if and only if for every set of r vertices in L(H) there is a vertex not adjacent to any of them.
  • mw(H) > r if and only if for every set of r vertices in L(H) there is a vertex not adjacent to any of them, and in addition, there is an independent set I in L(H) which contains a vertex not adjacent to any such set.
gollark: Sadly there aren't more available right now.
gollark: And yes, I do want a pinephone.
gollark: Yes.
gollark: And for only $25, too.
gollark: Yep!

See also

References
  1. 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.
  2. Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912.
  3. Aharoni, Ron (2001-01-01). "Ryser's Conjecture for Tripartite 3-Graphs". Combinatorica. 21 (1): 1–4. doi:10.1007/s004930170001. ISSN 1439-6912.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.