# Minimality condition in a certain class of hypergraphs

A hypergraph is a pair $H=(V,E)$ such that $V$ is a (possibly infinite) set and $E\subseteq \mathcal{P}(V)$. $C\subseteq E$ is said to be a cover if $\bigcup C = V$ and $C$is minimal if $C'\subseteq C$ and $C'\neq C$ imply $\bigcup C'\neq V$.

We call $H=(V,E)$ a flag complex if the following conditions are met:

1. $e\in E$ and $e'\subseteq e$ imply $e'\in E$;
2. $\bigcup E = V$;
3. $H$ is 2-determined, that is if $S\subseteq V$ and for all $s, t \in S$ we have $\{s,t\}\in E$ then $S\in E$.

A standard application of Zorn's Lemma shows that in a flag complex, every edge $e\in E$ is contained in a maximal edge $m\in E$ ($m$ being maximal in $E$ with respect to set inclusion). We denote the collection of maximal edges by $\text{Max}(E)$.

Question: Is there a flag complex $H=(V,E)$ and a cover $M\subseteq \text{Max}(E)$ such that for every cover $M'\subseteq M$ we have that $M'$ is not mimimal?

(Note: the example given in the answer of Strongly minimal covers does not work here, as it is not 2-determined.)

• Is the present problem an end to itself or is it a part of a larger picture (or an intermediate step, or has some ready applications)? – Włodzimierz Holsztyński Jan 9 '15 at 9:46
• Just a short answer: the question is an end to itself; I am toying around with (strongly) minimal coverings in hypergraphs in general. – Dominic van der Zypen Jan 9 '15 at 9:49
• What is the difference in meaning between "$(V,E)$ is a flag complex" and "$E$ is the family of all independent sets for some graph on the vertex set $V$"? What am I missing? – bof Jan 9 '15 at 10:04
• Thanks Wlodimierz - I deleted my comment and have recorded your information, you can delete yours now too – Dominic van der Zypen Jan 9 '15 at 10:07
• That's correct bof: the family of all independent sets of some graph $G=(V,E)$ does form a flag complex. On the other hand, given a flag complex, I would have to think about the question whether there is a graph whose collection of independent sets gives back the edge set of the original flag complex. – Dominic van der Zypen Jan 9 '15 at 10:10

## 1 Answer

NOTATION: $\ \mathbb Z_+\$ is the set of all non-negative integers $\ 0\ 1\ \ldots$.

The answer to the Question is YES, i.e.

THEOREM   There exists a flag complex $\ H=(V,E)\$ and a cover $\ M\subseteq Max(E)\$ such that for every cover $\ K\subseteq M\$ we have that K is not minimal.

PROOF   Let $\ V\$ be the set of all functions $\ f:\{0\ \ldots\ n\}\rightarrow \{0\,\ 1\}\$ such that

• $\ f(0):=0$

for every $\ n\in \mathbb Z_+.\$ (Values $\ f(n)\$ for $\ n>0\$ can be arbitrarily equal $\ 0\$ or $\ 1).\$ Then $\ E\$ is defined as the set of all chains $\ S\$ of functions, meaning that

• $\ \forall_{f:\{0\ \ldots\ n\}\rightarrow \mathbb Z_+\ and\ g:\{0\ \ldots\ m\}\rightarrow \mathbb Z_+}\ \ (\ n\le m\ \ \Rightarrow\ \ f=g|\{0\ldots n\}\ )$

Finally, let $\ M:=Max(E).\$ Obviously we truly have a flag complex $\ H,\$ and (as always) $\ Max(E)\$ is a cover. Thus let's consider an arbitrary cover $\ K\subseteq M.\$ Let $\ F\in K.\$. I'll show that $\ K\setminus\{F\}\$ is still a cover.

Indeed, Let $\ f\in F.\$ Then there exists a unique $\ f':\{0\ \ldots\ n\!+\!1\}\rightarrow\{0\,\ 1\}\$ such that $\ f'\in F\$ and $\ f=f'|\{0\ldots n\}.\$ Consider the unique $\ g:\{0\ \ldots\ n\!+\!1\}\rightarrow\{0\,\ 1\}\$ such that $\ f'\!\ne g\in E\$ and $\ f=g|\{0\ldots n\}.\$ Thus $\ g\notin F,\$ hence there exists $\ G\in K\setminus\{F\}\$ such that $\ g\in G.\$ But this means that also $\ f\in G.\$ Since $\ f\in F\$ was arbitrary, this means that $\ F\subseteq K\setminus\{F\}.$ END of proof

REMARK   In my example the required cover $\ M\$ is special, it is the whole $\ Max(E)$.

• It seems to me that flag complexes are in a 1-1 canonical correspondence with the (possibly infinite) graphs $\ (V\ \binom V2).\$ The flags (hypergraph edges) correspond to cliques, and maximal flags to maximal cliques. – Włodzimierz Holsztyński Jan 12 '15 at 12:20
• Very nice example - thanks Wlodzimierz! – Dominic van der Zypen Jan 12 '15 at 12:58