Skip to main content
1 of 3
John Machacek
  • 7.9k
  • 1
  • 23
  • 40

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 $o(2^n)$.

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 $o(2^n)$. So, the what these large cutsets look 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$.

John Machacek
  • 7.9k
  • 1
  • 23
  • 40