maximal number of points in a set such that no more than three lie in same "direction"?

[c.r...@espero.org.uk]

Is the below a question with a known answer? If not, I would
appreciate any suggestions as to what the appropriate mathematics to
use might be.

Let x = (x1,...,xn) and y=(y1,…,yn) be points in the positive orthant
of R^n. Perform a componentwise comparison, xi – yi, yielding “+”
when xi > yi, “-“ when xi < yi, and “0” when xi = yi. Thus, if
x=(1,0,0) and y=(1/2,1/2,0), the componentwise comparison is “+-0“.
Call each possible componentwise comparison (“+++”, “++0,”…,”---“) a
direction.

What, then, is the largest set of such points in R^n so that no more
than three of them lie in the same direction with respect to each
other? That is, given any w,x,y, and z in such a set, it cannot be
that the direction from w to x to y to z is the same.

Here is an example in R^3 for which no more than three points lie in
the same direction; this may not be the maximal set: {(1,0,0),
(0,1,0), (0,0,1), (1/2,1/2,0), (1/2,0,1/2), (0,1/2,1/2),
(1/2,1/4,1/4), (1/4,1/2,1/4), (1/4, 1/4, 1/2)}.

Thank you in advance,

Colin Rowat
Economics, University of Birmingham

[Mensanator]

On Sep 6, 5:30 am, "c.ro...@bham.ac.uk" <c.ro...@espero.org.uk> wrote:
> Is the below a question with a known answer?  If not, I would
> appreciate any suggestions as to what the appropriate mathematics to
> use might be.
>
> Let x = (x1,...,xn) and y=(y1,…,yn) be points in the positive orthant
> of R^n.  Perform a componentwise comparison, xi – yi, yielding “+”
> when xi > yi, “-“ when xi < yi, and “0” when xi = yi.  Thus, if
> x=(1,0,0) and y=(1/2,1/2,0), the componentwise comparison is “+-0“.
> Call each possible componentwise comparison (“+++”, “++0,”…,”---“) a
> direction.

Three symbols (+,0,-) maps to base 3.

>
> What, then, is the largest set of such points in R^n so that no more
> than three of them lie in the same direction with respect to each
> other?  That is, given any w,x,y, and z in such a set, it cannot be
> that the direction from w to x to y to z is the same.

And n points maps to an n-digit base 3 number.

So there are 3**n distinct directions since there
are Base**n possible n-digit numbers for a given base.

>
> Here is an example in R^3 for which no more than three points lie in
> the same direction;

So there are a maximum of 3 copies of each distinct direction.

That makes 3*3**n or 3**(n+1). Use the former if the maximum
number of points doesn't equal the number of symbols. For
example, if you allow 5 points in each distinct direction,
it would be 5*3**n.

[c.r...@espero.org.uk]

Thank you Mensanator. The case that interests me most is that in
which the set of points in R^n is restricted to lying in an (n-1)
dimensional subspace governed by x1 + ... + xn = 1. Your answer above
provides an upper bound for this: is there a clean way of expressing
the exact number?

[Mariano Suárez-Alvarez]

You are counting/bounding the maximal number of
points such that there are at most 3 in each "directions".
But the problem was, IIUC, counting the maximal number
of points such that at most 3 of their *differences*
are in each "direction".

-- m

[Mariano Suárez-Alvarez]

On Sep 6, 7:30 am, "c.ro...@bham.ac.uk" <c.ro...@espero.org.uk> wrote:
> Is the below a question with a known answer?  If not, I would
> appreciate any suggestions as to what the appropriate mathematics to
> use might be.
>
> Let x = (x1,...,xn) and y=(y1,…,yn) be points in the positive orthant
> of R^n.  Perform a componentwise comparison, xi – yi, yielding “+”
> when xi > yi, “-“ when xi < yi, and “0” when xi = yi.  Thus, if
> x=(1,0,0) and y=(1/2,1/2,0), the componentwise comparison is “+-0“.
> Call each possible componentwise comparison (“+++”, “++0,”…,”---“) a
> direction.
>
> What, then, is the largest set of such points in R^n so that no more
> than three of them lie in the same direction with respect to each
> other?  That is, given any w,x,y, and z in such a set, it cannot be
> that the direction from w to x to y to z is the same.

Let me check I understand what you mean, by rephrasing it.

Let S = {0, +1, -1} and let sgn : R --> S be the usual
sign function, so that

sgn(x) = 0, if x = 0;
+1, if x > 0; and
-1, if x < 0.

Define a function sgn : R^n --> S^n (with the same name...)
by applying sgn componentwise, that is: if v = (v1, ..., vn)
is in R^n, we put

sgn(v) = (sgn(v1), ..., sgn(vn))

You want to know the maximal size of a finite
subset X of R^n such that the following condition
holds:

for all s in S^n, the set

{ (x,y) in X^2 : x != y, sign(x-y) = s }

has at most 3 elements.

Is that correct?

-- m

[c.r...@espero.org.uk]

On Sep 7, 1:24 am, Mariano Suárez-Alvarez

Thank you Mariano. That's almost what I have in mind, but I'm only
interested in the direction for a particular sequence of points with
the set. Thus (altering some of the notation above, and including the
constraint on sum xi):

Let X = {x in R^n : xi >= 0, sum_i xi = 1}. What is the largest
subset, Y, of X such that there is no sequence x^1, ..., x^4 of points
in Y satisfying sign(x^{k+1} - x^k) = s != (0,0,0) for all k = 1,...,
3 and for some s in S^n?

Returning to the initial example, seven (x,y) pairs satisfy the
pairwise definition when s = (-1,0,1): ((1,0,0), (1/2,0,1/2)),
((1/2,0,1/2), (0,0,1)), (1/2,1/4,1/4), (1/4,1/4,1/2)), ((1/2,1/2,0),
(1/4,1/2,1/4)), ((1/4,1/2,1/4), (0,1/2,1/2)), ((1,0,0), (0,0,1)),
((1/2,1/2,0), (0,1/2,1/2)). However, the example satisfies the
sequencewise definition, as the longest such sequence is x^1 =
(1,0,0), x^2 = (1/2,0,1/2), x^3 = (0,0,1).

Thanks,

Colin

[Mariano Suárez-Alvarez]

I would have never understood that from what you wrote
originally...

-- m

[c.r...@espero.org.uk]

On Sep 7, 11:22 pm, Mariano Suárez-Alvarez

I believe that I have an upper bound to the answer. Given any set of
points, there are at most c = (3^n - 1)/2 "directions". Form a
complete, c-coloured graph from the points as follows: for any nodes x
and y, colour the edge between them to match the "direction" between
them (the division by 2 in defining c means that we have an undirected
graph). The question may now be interpreted in terms of Ramsey
theory: what is the largest set of points such that a monochromatic 4-
clique does not exist? The answer to this is the Ramsey number, R_c
(4) - 1.

This bound is generally loose as it makes use of little of the
problem's structure. Knowing that x and y are related to each other
by a particular direction, and knowing that y and z are related by
another direction, allows one to determine how x and z are related;
this information is not used. Using it would obviously tighten the
bound.

I am also generally interested in symmetric solutions. Again, the
bound does not draw on symmetry.

I am happy to provide full details of the proof to anyone interested.

Best, and thank you again for your thoughts,

Colin Rowat