Let $A\in \mathbb R^{n\times n},\ b\in \mathbb R^n$ such that $\forall x\in \{-1,1\}^n : Ax\ne b$.

Let us denote: $S=\{x\in\mathbb R^n|Ax=b\}$ ('S' for solution set).

Is $\ \#\Big\{H\in\big\{ \{-1\}, \{1\}, (-1,1)\big\}^n \ \Big|\ H\cap S\ne\emptyset\ \Big\} = O(n)$?

where '#' denotes the cardinality of the set.

My intuition tells me that this should be true, but I can't figure out how to prove or disprove it.

So far, I've done many trial and error "experiments" that also support my conjecture, but I am stuck in proving/ disproving it in the general case.

By the way, it is easy to see that WLOG the solution set is a hyper-plane. So, we can modify $S$ to be $S=\{x\in\mathbb R^n|a^T x=b\}$ for $a\in\mathbb R^n, b\in\mathbb R$ such that $\forall x\in \{0,1\}^n:a^T x\ne b$.

  • $\begingroup$ I think you mean certain equivalence classes of points. Are you asking how many faces intersect a solution set? By the way, if b is zero and A is zero, the answer is probably "No", so you should expect an answer conditional on the real rank of A. Gerhard "Unsure Which Grouping Is Used" Paseman, 2018.09.19. $\endgroup$ – Gerhard Paseman Sep 19 '18 at 18:07
  • $\begingroup$ @GerhardPaseman I edited my question and added some more essential requirement: that $\forall x\in \{0,1\}^n : Ax\ne b$. $\endgroup$ – Dudi Frid Sep 19 '18 at 20:11
  • $\begingroup$ @DudiFrid: I believe that you may drop the corners $\{-1\}^n$ and $\{1\}^n$, because they are always just two points, and this does not change the asymptotics. $\endgroup$ – Alex M. Sep 19 '18 at 20:12
  • $\begingroup$ @AlexM. My bad, it was just a typo. Thanks for pointing it out $\endgroup$ – Dudi Frid Sep 19 '18 at 20:15
  • $\begingroup$ @DudiFrid: Notice that I have made a change in the definition of the set that you are describing, please check whether it conveys what you meant to say. $\endgroup$ – Alex M. Sep 19 '18 at 20:19

Just take $\sum x_i=n-1$ and you get $O(n\cdot2^n)$ instead of $O(n)$.


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.