ArticleslgStudy

science

Width of a hypergraph

Width of a hypergraph is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Width of a hypergraph rather than just read about it. In short: 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.

Width of a hypergraph — main illustration
Width of a hypergraph — illustration

Key takeaways

  • Width of a hypergraph belongs to science; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Width of a hypergraph to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Width of a hypergraph from memory before moving on to harder problems.

Reference excerpt

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. Then:

The width of H, denoted w(H), is the smallest size of a subset of E that pins E. The matching width of H, denoted mw(H), is the maximum, over all matchings M in H, of the minimum size of a subset of E that pins M. 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 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. The domination number of a graph G, denoted γ(G), is the smallest size of a vertex set that dominates all vertices of G. The width of a hypergraph equals the domination number or its line-graph: w(H) = γ(L(H)). This is because the edges of E are the vertices of L(H): every subset of E that pins E in H corresponds to a vertex set in L(H) that dominates all L(H). The independence domination number of a graph G, denoted iγ(G), is the maximum, over all independent sets A of G, of the smallest set dominating A. The matching width of a hypergraph equals the independence domination number or its line-graph: mw(H) = iγ(L(H)). This is because every matching M in H corresponds to an independent set IM in L(H), and every subset of E that pins M in H corresponds to a set that dominates IM in L(H).

See also For other concepts termed "width" in graph theory, see Width (disambiguation)#Graph theory.

References

Illustrations

Width of a hypergraph: The hypergraph H shown in both illustrations has width w(H) = 2 and matching width mw(H) = 1. The set of edges in the first graph highlighted yellow pins all other edges (each edge outside the set shares a vertex with at least one edge inside the set), and there is no smaller set that can pin all edges. Any matching of the graph can be pinned by a single edge. Here, a matching is shown in red, and an edge that pins it in yellow.
The hypergraph H shown in both illustrations has width w(H) = 2 and matching width mw(H) = 1. The set of edges in the first graph highlighted yellow pins all other edges (each edge outside the set shares a vertex with at least one edge inside the set), and there is no smaller set that can pin all edges. Any matching of the graph can be pinned by a single edge. Here, a matching is shown in red, and an edge that pins it in yellow.

Worked examples

Example 1 — a first encounter with Width of a hypergraph

Start with the simplest possible case. Write down what Width of a hypergraph claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Width of a hypergraph before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Width of a hypergraph ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Width of a hypergraph

In research
Width of a hypergraph appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Width of a hypergraph in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Width of a hypergraph is common in secondary-school and first-year university syllabi. It links to neighbouring topics Hypergraphs, so understanding it makes those chapters shorter.
In everyday life
Look for Width of a hypergraph outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Width of a hypergraph in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Width of a hypergraph means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Width of a hypergraph out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Width of a hypergraph in simple terms?

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.

Why does Width of a hypergraph matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Width of a hypergraph?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Width of a hypergraph.

Tags

  • Hypergraphs

Keep exploring