Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

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'$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.