1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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)? $\endgroup$ – Włodzimierz Holsztyński Jan 9 '15 at 9:46
  • $\begingroup$ Just a short answer: the question is an end to itself; I am toying around with (strongly) minimal coverings in hypergraphs in general. $\endgroup$ – Dominic van der Zypen Jan 9 '15 at 9:49
  • $\begingroup$ 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? $\endgroup$ – bof Jan 9 '15 at 10:04
  • $\begingroup$ Thanks Wlodimierz - I deleted my comment and have recorded your information, you can delete yours now too $\endgroup$ – Dominic van der Zypen Jan 9 '15 at 10:07
  • $\begingroup$ 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. $\endgroup$ – Dominic van der Zypen Jan 9 '15 at 10:10
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Włodzimierz Holsztyński Jan 12 '15 at 12:20
  • $\begingroup$ Very nice example - thanks Wlodzimierz! $\endgroup$ – Dominic van der Zypen Jan 12 '15 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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