# When does a hypergraph represent maximal independent sets?

Let $G = (V,E)$ be a simple graph. Then, we can view the set of maximal independent sets (or the set of maximal cliques) as a hypergraph $H = (V, E')$. This is quite a useful device when connecting the (fractional) packing/covering numbers of $H$ with the (fractional) clique/chromatic numbers of $G$ (cf. Scheinerman and Ullman, Fractional Graph Theory).

When is the converse true, namely, when does a hypergraph correspond to a set of maximal independent sets?

As an example, $H = ([3], \{ \{1,2\}, \{2,3\} \})$ corresponds to the maximal independent sets of the graph

$1 \text{------}3~~~~~~~~2$,

or equivalently, to the maximal cliques of the complementary graph

$1 \text{------} 2 \text{------} 3$.

But another hypergraph with hyperedges $\{ \{1,2\}, \{2,3\}, \{3,1\} \}$ does not correspond to the maximal independent sets of any graph.

Is there any sufficient and necessary condition that can be captured by the incidence matrix of $H$?

-

Clearly, if $E'=\{X_1,X_2,\dots,X_n\}$ is the set of all maximal cliques of a simple graph $(V,E)$, then $$E=\binom{X_1}2\cup\binom{X_2}2\cup\cdots\cup\binom{X_n}2.$$ Hence, a necessary and sufficient condition for an antichain $E'$ of subsets of $V$ to be the set of all maximal cliques of a simple graph on the vertex set $V$ is that, for every set $S\subseteq V$, if each $2$-element subset of $S$ is contained in an element of $E'$, then $S$ is contained in an element of $E'$.