7
$\begingroup$

For $x\in\mathbb{R}^d$ and $A\subset\mathbb{R}^d$, we say that $x$ is well separated from $A$ if there is a linear functional $f:\mathbb{R}^d\rightarrow\mathbb{R}$ such that $f(A)\subseteq [0,1]$ and $f(x)=2$.

Suppose that $P\subset\mathbb{R}^d$ is a set of $n$ points such that every $p\in P$ is well separated from $P\backslash\{p\}$. What can we say about the size of $d$? I believe that it must be $\Omega(n)$ (i.e., it grows linearly with $n$), or at least close to it, but a proof has eluded me thus far. I would not be too surprised if this were a consequence of a deeper known result I am unaware of.

For my purposes, it would actually suffice to show that $d$ is at least linear under the stronger assumption that for every $p\in P$ there is a functional $f_p$ such that $f_p(P\backslash\{p\})\subseteq\{0,1\}$ and $f_p(p)=2$. I am not sure this is particularly helpful, but it does allow you to assume that (after applying a linear transformation and deleting a small fraction of the points) the elements of $P$ are vertices of the hypercube $\{0,1\}^d$, which might make the problem more amenablea to combinatorial tools.

Note that, in either of the two variants, $P$ must be the vertex set of a convex polytope. Two simple examples of point sets with the above property: Any set of linarly independant vectors and the vertex set of the cross-polytope (of dimension $d-1$, embedded into an affine hyperplane).

P.D.: This is my first question on the forum! I hope it is not too dull.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Take all the vectors of the form $e_i+e_j$, $i\neq j$, where $e_1,\dots,e_d$ is a base in $\mathbb R^d$. They satisfy your requirements, the vector $e_i+e_j$ being separated from the others by $e_i^*+e_j^*$, the sum of two vectors from the dual base. This set has a quadratic in $d$ size, and it satisfies even the strong requirements.

Improve this answer
$\endgroup$
11
  • 2
    $\begingroup$ A generalization (not meeting the stronger requirements, and switching back to the notation of the OP): let $\mathcal I=\{I_i:i<n\}$ be a family of subsets of $[d]$ such that $|I_i|=s$ and $|I_i\cap I_j|\le s/2$ for all $i\ne j$. Then $\{\sum_{u\in I_i}e_u:i<n\}$ is well separated, using the functionals $\frac2s\sum_{u\in I_i}e_u^*$. One way to construct such a family $\mathcal I$ is to take $s\approx\sqrt d$ a prime power, and identifying $[d]$ with $\mathbb F_s^2$, let $\mathcal I$ consists of the graphs of all polynomials $f\in\mathbb F_s$ of degree $<s/2$. Then $n\approx d^{\sqrt d/4}$. $\endgroup$
    – Emil Jeřábek
    Commented Nov 7, 2022 at 11:37
  • 2
    $\begingroup$ ... My memory of parameters of Nisan–Wigderson designs is rusty, but I suspect there should even be such a family of size $2^{\Omega(d)}$. $\endgroup$
    – Emil Jeřábek
    Commented Nov 7, 2022 at 11:49
  • 3
    $\begingroup$ @Emil if you take $s=d/3$ and choose subsets one by one, you take exponentially many of them $\endgroup$
    – Fedor Petrov
    Commented Nov 7, 2022 at 12:37
  • 2
    $\begingroup$ ... belongs to exactly half of the sets, thus $s=d/2$ by double counting, thus $\lambda_i=0$ after all. Now, consider the general case $|I\cap J|\in\{0,s/2\}$ for all $I\ne J\in\def\cI{\mathcal I}\cI$. Let $\{I_i:i<k\}$ be a maximal disjoint subset of $\cI$, thus every $I\in\cI$ intersects some $I_i$. Let $\cI_i=\{I\in\cI:I\cap I_i\ne\varnothing\}$ and $E_i=\{(I,J)\in\cI_i:I\cap J=\varnothing\}$. The graph $(\cI_i,E_i)$ is bipartite: if $(I,J)\in E_i$, then $I\cap I_i$ is the complement of $J\cap I_i$ (in $I_i$), hence there is no odd cycle. Thus, we can write $\cI_i=\cI'_i\cup\cI''_i$ ... $\endgroup$
    – Emil Jeřábek
    Commented Nov 9, 2022 at 14:34
  • 2
    $\begingroup$ ... where all elements of $\def\cI{\mathcal I}\cI'_i$ interesect, and likewise for $\cI''_i$. Thus, $|\cI'_i|,|\cI''_i|\le d$ by the first part of the proof, and $|\cI|\le2dk\le2d^2/s\le d^2$. $\endgroup$
    – Emil Jeřábek
    Commented Nov 9, 2022 at 14:37

You must log in to answer this question.

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