Skip to main content
Correction pointed out in comment
Source Link
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)$$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 $o(2^n)$$c(n)$. So, what thesetheis large cutsets lookcutset 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$.

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

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

deleted 4 characters in body
Source Link
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$.

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

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

Source Link
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$.