3
$\begingroup$

Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this bound is tight.

Now consider the directed hypercube graph $\vec{Q}^{n}$, where we direct every edge in the natural way. I am looking for references related to similar problems one can ask on this graph, when one looks at induced subgraph on $2^{n-1}$ vertices.

  1. What about max (max in degree, max out degree)? From Huang's result we know that this is at least $\frac{\sqrt{n}}{2}$. Can we do better, and is this tight?

  2. What about min (max in degree, max out degree) and lower bound for this?

There are several such questions one might ask in this flavour, and some have probably been studied.

$\endgroup$
7
  • $\begingroup$ what is the natural way of directing each edge? $\endgroup$
    – vidyarthi
    Commented Mar 1 at 10:43
  • 3
    $\begingroup$ @vidyarthi consider the vertices of the hypercube as all $0,1$ strings of length $n$ bits. Then there is an edge between two strings iff they differ in exactly one bit (Hamming distance is $1$). Now, the natural way to direct this edge is from the vertex where the differing bit is $0$ to the one where it is $1$. $\endgroup$ Commented Mar 1 at 15:26
  • 1
    $\begingroup$ Since directing each edge introduces a poset structure and a grading on the hypercube, you might have better luck checking in the world of boolean lattices and algebras. $\endgroup$ Commented Mar 11 at 21:03
  • $\begingroup$ Perhaps just to save others the time I took: the result showing that $\sqrt{n}$ is tight unfortunately has the property that every vertex has either only incoming edges or only outgoing edges with this directed graph structure. So it is unhelpful for (1) in that it only provides an upper bound of $\sqrt{n}$ there as well. $\endgroup$ Commented Mar 12 at 22:29
  • $\begingroup$ @RonniePavlov thanks for the observation $\endgroup$ Commented Mar 12 at 23:10

1 Answer 1

1
+50
$\begingroup$

I thought this would be a full solution (i.e. showing (1) is $\sqrt{n}/2$), but in fact it only yields (1) is less than or equal to $\sqrt{n}/\sqrt{2}$. I'll still post it after all of the effort, while hoping that someone can improve it!

I believe that a simple change in the Chung-Furedi-Graham-Seymour paper which proves $\sqrt{n}$ is tight can be used to show that your (1) is at most $\sqrt{n}/\sqrt{2}$. Their construction works for all $n$ and uses floor functions, for simplicity I'm going to present a construction only for the case when $n$ is twice the square of an even integer.

Suppose that $n = 2k^2$, $k$ is even, and define a collection of sets $S \subset \mathcal{P}([n])$ as follows. First define $T$ to be the set of all $A \subset [n] = \{1, \ldots, n\}$ for which, for some $0 \leq i < k$, $S$ contains all of $2ki+1, \ldots, 2ki+k$ and none of $2ki+k+1, \ldots, 2ki+2k$. Then $S$ consists of all $B \subset [n]$ for which either

$\bullet$ $|B|$ is even and $B \in T$ or

$\bullet$ $|B|$ is odd and $B \notin T$

For instance, when $k = 2$ and $n = 8$, $T$ contains all sets which either (contain both of $1,2$ and omit both of $3,4$) or (contain both of $5,6$ and omit both of $7,8$), and $S$ consists of all even sets in $T$ and all odd sets in $T^c$.

Claim 1: $|S| = 2^{n-1} \pm 1$. I don't think I should try to write a full proof here, but it's essentially the same proof as for the Chung-Furedi-Graham-Seymour example. For context, their example is the same, but where the definition of $T$ is simpler, instead of containing all of $2ki+1, \ldots, 2ki+k$ and missing all of $2ki+k+1, \ldots, 2ki+2k$ for some $i$, they just require containing all of $2ki+1, \ldots, 2ki+2k$ for some $i$.

They find $|S|$ by inclusion-exclusion, and the key is that for any nonempty proper $\{i_1, \ldots, i_j\} \subsetneq \{0, \ldots, 2k-1\}$, the number of even/odd sets $B$ containing all of $2ki_m + 1, \ldots, 2ki_m + 2k$ for $1 \leq m \leq j$ is $2^{n-2kj-1}$. That fact is still true in our setting (specifying some elements to be out of $B$ instead of in $B$ has the same effect probabilistically). The only subtlety is what happens when the condition holds for all $i$. In their paper, this forces $B$ to be all of $[n]$ (so even in our setting), and the same condition for us forces $B$ to be exactly the set $\{1, \ldots, k, 2k+1, \ldots, 3k, \ldots, (2k-2)k+1, \ldots, (2k-1)k\}$, of size $k^2$, again even since we assumed $k$ even.

So see their paper for more details, but this should still be true (and I checked for some small $k$).

Claim 2: every set in the induced subgraph for $S$ has no more than $k = \sqrt{n}/\sqrt{2}$ incoming edges and no more than $k = \sqrt{n}/\sqrt{2}$ outgoing edges, and the same is true of the induced subgraph for $S^c$.

Proof: There are eight cases, all similar. Consider an even set $B$ in $S$ with an outgoing edge in $S$, meaning $m \notin B$ so that $B \cup \{m\} \in S$. Then by definition, $B \in T$ and $B \cup \{m\} \notin T$. The only possibility is that $B$ contains all of $2ki+1, \ldots, 2ki+k$ and none of $2ki+k+1, \ldots, 2ki+2k$ for exactly one $i$, and $m \in \{2ki + k + 1, \ldots, 2ki + 2k\}$, so there are exactly $k$ choices for $m$.

If instead there is an incoming edge, then $m \in B$, $B \in T$, and $B - \{m\} \notin T$. Again there is only one possibility; $B$ contains all of $2ki+1, \ldots, 2ki+k$ and none of $2ki+k+1, \ldots, 2ki+2k$ for exactly one $i$, and $m \in \{2ki+1 + 1, \ldots, 2ki + k\}$. Again there are exactly $k$ choices for $m$.

Now suppose instead that $B$ was odd. For an incoming edge, $B \notin T$ and $B \cup \{m\} \in T$. The only possibility is that $B$ nearly satisfied the condition for being in $T$ in that there exists $0 \leq i < k$ for which all but one of $2ki + 1, \ldots, 2ki+k$ are in $B$ and none of $2ki + k+1, \ldots, 2ki+2k$ are in $B$. Each such $i$ yields a single possible value of $m$ (the single missing element), and there are at most $k$ possible values of $i$, so there are at most $k$ possibilities for $m$.

For an outgoing edge, it's the same as above except that now $B$ must contain all of $2ki+1, \ldots, 2ki+k$ and exactly one of $2ki+k+1, \ldots, 2ki+2k$ for some $0 \leq i < k$, and for each such $i$, there is again only one possibility.

The other four cases ($B$ in $S^c$) are trivially similar; the key is still that there are at most $k$ ways to add or remove a single element to pass from $T$ to $T^c$ or vice versa.

So now we're done; choose whichever of $S$ or $S^c$ has cardinality $2^{n-1} + 1$, and it has max(max indegree, max outdegree) = $k = \sqrt{n}/\sqrt{2}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .