Mathematics Asked by Erel Segal-Halevi on August 16, 2020

In this paper, the *width of a hypergraph* $H$ is defined as the minimum integer $t$ for which there exists a subset $T$ of $t$ hyperedges in $H$, such that every hyperedge of $H$ intersects at least one hyperedge of $T$.

To better understand this notion, I am trying to relate it to terms related to graphs. I found many "width" terms related to graphs, such as: tree-width, path-width, branch-width and bandwidth. But I could not understand which of these terms, if any, is equivalent to the above definition. Is this "width of a hypergraph" a well-known term in graph theory? Does it have a counterpart for simple graphs, maybe in another name?

The exact analogue of this width for simple graphs, where your 'hyperedges' are all normal edges between two vertices, is the 'minimum size of a maximal matching'. wikipedia - matching

Hyper-edges can be 'large' as subsets of the vertex set, where as edges are quite constrained. So the most 'spiritually similar' concept to this width that is well studied is probably the 'vertex cover number'. This is the size of the smallest subset of vertices that is incident with every edge of the graph. wikipedia - vertex cover

Correct answer by Brandon du Preez on August 16, 2020

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP