Minimality condition in a certain class of hypergraphs

Question

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.)

Answer 1

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