# Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices $U,V\subseteq [n]$ are adjacent and oriented as $\langle U, V\rangle$ if and only if there exists some $q\in [n]$ such that $U=V\setminus \{q\}$.

A cut $C$ of $H_n$ is a subset of the vertex set $C\subseteq \wp([n])\setminus \{\emptyset, [n]\}$ such that that (1) it does not contains neither the bottom vertex $\emptyset$ nor the top vertex $[n]$ (2) there exists no directed path from $\emptyset$ to $[n]$ in the subgraph of $H_n$ induced by $\wp([n])\setminus C$, i.e. there is no directed path in $H_n$ that goes from the bottom vertex $\emptyset$ to the top vertex $[n]$ simultaneously avoiding all vertices of $C$.

A cut $C$ is minimal when for every $S\subsetneq C$ we have that $S$ is not a cut.

Q. Is it known how to count and/or generate the family of minimal cuts on the directed hypercube graphs ?

Q. Let $\gamma(n)$ be the number of minimal cuts of $H_n$, is this integer sequence already known in the literature ?

Q. Is it anything known on minimal cuts ?

I do not know the answer to your first two questions, but here is what I was able to find relevant to your third question.

Q. Is it anything known on minimal cuts ?

What you call the hypercube digraph is the Hasse diagram of $B_n$ the Boolean algebra (or Boolean lattice). Using this keyword may help you find some literature on the subject.

In this paper by Furedi, Griggs, and Kleitman a minimal cutset of the Boolean algebra with almost all the members is found. That is they show existence of a minimal cut set in $B_n$ of size $c(n)$ where $\lim_{n \to \infty} c(n)/2^n = 1$.

That paper is from 1988, and I was not able to find anything more recent.

It seems difficult to enumerate all the minimal cutsets considering there is such a wide range of sizes. There are the obvious cutsets of size $\binom{n}{k}$ taking all the $k$ element subsets. Thus there is one of size $n$ taking all the $1$ element subsets. Also, the result in the paper above gives an "almost" explicit description of the cutset of size $c(n)$. So, what theis large cutset looks like is not exactly known (at least at the time of this paper).

Though maybe more is known today. I was not able to find anything on OEIS. It would be interesting to see some data at least for small $n$.