2
$\begingroup$

Let $C$ be a full-dimensional cone in $\mathbb{R}^{d}$, defined as the positive span of $c = {n \choose 3} \gg d$ vectors. $C$ is highly symmetric in the following sense: each such vector is labelled with a distinct unordered triple from $[n]$, and the automorphism group of $C$ is basically $S_n$: for each permutation $\pi : [n] \to [n]$, there is a linear transformation of $\mathbb{R}^d$ that takes each vector labelled $(x, y, z)$ to the vector $(\pi(x), \pi(y), \pi(z))$.

My intuition is that any supporting hyperplane to $C$ can have only $O(d/n)$ of these vectors, roughly because the symmetry constraints prevent too many supporting vectors from being concentrated on one side of the cone. Is this true?

$\endgroup$
1
  • $\begingroup$ in my answer I give an example where one can have $O(n)$ of these vectors. $\endgroup$ Jul 6, 2019 at 8:23

1 Answer 1

2
$\begingroup$

The prescribed group action allows to start from it and build the cones in question. It is well-known how the permutation representation of $S_n$ on 3-subsets decomposes into irreducibles - there will be just 4 of these, one of them trivial 1-dimensional one. With the other ones (more precisely, subsets of these) you have a graph embedding, affording the group action. You could start by figuring out which ones satisfy your $c\gg d$ condition, and basically classify all the possibilities for $C$.

Specifically, the irreducibles correspond to partitions of $n$ as $n=(n-j)+j$, with $0\leq j\leq 3$, and dimensions are given by $$ d_j:=\frac{n-2j+1}{n-j+1}\binom{n}{j},\qquad 0\leq j\leq 3, $$ Now, $d_j$ is a degree $j$ polynomial in $n$, and I guess that this only leaves $j=1$ as the $d=d_1$ or $d=d_1+1=n$, satisfying $c\gg d$.


E.g. in the case $d=n$ you get the generators of $C$ given by indicator vectors of the 3-subsets, and one should be able to expicitly classify the facets of this cone. In any event, the facets will contain at least $O(n)$ of the generators, and not $O(1)$. So it seems that the question needs an adjustment to make sense of this case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.