(graph theory) hypergraph terminologies

Question

I am a newbie in graph theory, and I am wondering if there are two notions that capture the following.

1. A set of hyperedges $\{e_i\}$ that covers all vertices in graph. Formally, for any vertex $v$ we should be able to find a hyperedge $e_i$ such that $v \in e_i$. What is this set $\{e_i\}$ called?

2. A set of hyperedges $\{e_i\}$ such that no $e_i$ is a proper subset of another $e_i'$. What is this set $\{e_i\}$ called?

Any help (reference as well) will be appreciated!

Answer 1

In the case of graphs, a set of edges that covers all vertices is called an edge cover. When we generalize to hypergraphs, we have two options:

• continue calling this an edge cover, as in this paper just to give one example;
• call it a set cover (as in the set cover problem).

Generally, we'd use the first of these options if we're leaning heavily on the graphs-to-hypergraphs analogy (say, if we're also talking about independent sets or vertex degrees or any other concept that sees lots of use in graphs). But a hypergraph in full generality is no different from a set family, and so it's also valid to just call this a set cover.

---

A set $S$ of hyperedges such that no $e \in S$ is a proper subset of another $e' \in S$ can be called inclusion-free or an antichain; both of these are set-theoretic terms, and you can find both of them commonly used in various statements of Sperner's theorem, for instance.

Any such term will be more commonly used for "set families" than for "hypergraphs" (quotation marks because those are the same thing). That's because when we talk about hypergraphs, it's very common to only consider uniform hypergraphs, in which case this condition is automatic for any set of hyperedges.