3
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.