Max Non-Adjacent Vertices from Intersection of Hyperplane & n-Cube

[jorgealnino]

Hi

Taking the intersection of a n-cube with any hyperplane, i would like to know the maximum number X of non adjacent vertices of the cube lying in such intersection.

In R2 for instance, i can cut the unit square {(0,0),(1,0),(1,1),(0,1)} with a diagonal line passing through
(1,0) and (0,1). Hence, X=2

In R3 i have the cube {(0,0,0),(1,0,0),(1,0,1),(0,0,1),(0,1,0),(1,1,0),(1,1,1),(0,1,1)} and the plane x1 + x2 + x3 = 1 touches the points {(1,0,0),(0,0,1),(0,1,0)}. Thus X=3?

In Rn, X = n? and if it is, how to show it?

Thanks for any hint!

 

[henry_m]

Interesting problem, you sure managed to distract me!

It's not n, I've found a counterexample. For n=4, you have X=6. The hyperplane w+x-y-z=0 intersects the vertices (0,0,0,0),(0,1,1,0),(0,1,0,1),(1,0,1,0),(1,0,0,1),(1,1,1,1), no pair of which are adjacent. And it can't be more than six, because the hyperplane can intersect the cubes at w=0 and w=1 no more than three times each from the n=3 case (in general, X_n\leq 2X_{n-1}).

I still have no solution, but I've found a way to state the problem in a rather different form, which is how I found the counterexample:

From n nonzero numbers, not necessarily distinct, what is the largest possible number of ways of adding the numbers to get zero (including the sum of none of them, which is always a solution)?

How this works: the vertices of the cube are the points with all coordinates 0 or 1. We might as well take the hyperplane passing through the origin by symmetry. Then the hyperplane has an equation a_1 x_1+\cdots+a_n x_n=0. The vertices correspond to subsets of {1,2,...,n}, being those coordinates which are 1. If a vertex intersects the hyperplane, its corresponding subset of the numbers a_n sums to zero. Finally, there will be intersections of adjacent vertices if and only if one of the a_n is zero.

I'm pretty sure you can take them all to be integers WLOG, but not sure how to prove it immediately.

 

[jorgealnino]

Hi again

Yes, I agree it is an interesting problem as it is your approach to find the couterexample henry_m!

Even if this problem seems to be "standar", it was not easy for me to find some information about its solution. At the end i found this thesis:

Combinatorial & Computational Properties of the Hypercube
O Aichholzer

and in chapter 4 you can see that X = \binom {n}{\lceil n/2 \rceil} is apparently
a well known result. There you can find also your bound: X_n\leq 2X_{n-1}.

Now I'm posting a variant of this problem which is indeed my original problem:

Having the unit simplex S_1 = \{x_i \in R^n : \sum_{i=1}^n{x_i}=1, x_i \geq 0\},
how many vertices (X) of a parallepiped defined by
lb_i \leq x_i \leq ub_i can be in S_1?

Here, taking the parallepiped as the n-cube \{lb_i = 0,ub_i =1 \ \forall i\} we have that n is a lower bound for X.

Any idea to show that X = n or another couterexample will be appreciated.