Tuesday, January 22, 2013

A New application of Ramsey Theory to a Geometry problem

All of the material summazized here is in a new paper by Gasarch and Zbarsky. You can find that paper here)

Consider the following problem:

  1. Let {p1,...,pn} be a subset of distinct points in Rd. We think of d ≤ n. How big is the largest subset X of points such that all of the distances determined by pairs of elements of X are different? Let h(d,n) be the min size of X. That is, we always have a set X of size h(d,n) with all distances between points different.
  2. Assume that no three of the original points are collinear. How big is the largest subset X of points such that all of the areas determined by triples of points in X are different? Let g(d,n) be the min size of X. That is, we always have a set X of size g(d,n) with all triangle-areas of different sizes.
(This is NOT the Erdos Distance problem where you are given n points and want to know the min number of diff distances you have.) What is know about the problem posed?
  1. The case of d=1 is known h(1,n)=Θ(sqrt(n)).
  2. Erdos said somewhat mysterioulsy (I paraphrase)
    It is easy to see that there are constants ep(d) such that h(d) ≥ nep(d). (BILL: Frankly- I do not find it easy to see.)
    Aside from that, not much was known.
Until now. Gasarch and Zbarsky have shown the following (roughly)
  1. h(d,n) ≥ Ω(n1/(6d)).
  2. g(2,n) ≥ Ω((log log n)1/2901).
  3. g(3,n) ≥ Ω((log log n)1/27804).

We believe these results are new. They were obtained using variants of the Canonical Ramsey Theorem, originally due to Erdos and Rado, and some geometric lemmas.

6 comments:

  1. My above desc might not be clear so I claify here:

    h(a,n) is the largest number such that, given n points in
    R^d, there will be h(a,n) of them such that all of
    the distances between them are different.

    g(a,n) is the largest number such that, given n points in
    R^d, there will be g(a,n) of them such that all of
    the areas of triangles determined by 3 of them are different
    (OH- the original points have to be no-three-colinear)

    ReplyDelete
  2. yeah, unfortunately, that's not wat it used to mean anymore about getting some results. It's kinda cliche nowadays. but nice try nevertheless.

    ReplyDelete
    Replies
    1. yeah, unfortunately, you're what we call a dumb troll

      Delete
  3. What do you mean? Sam and I have a result, and the paper is linked to.

    ReplyDelete
  4. Anonymous coward is so awesome at math, he doesn't even need correct English! Clearly, his "results" are also so awesome that he doesn't even need to identify them, much less himself!

    ReplyDelete
  5. (this is actually GASARCH but I am having a hard time using my
    google account today)

    1) I improved the results- the exp of loglog n is now 1/186 and
    1/396.

    2) Using a paper of Shelah I am sure I can get (log n)^c for some c.

    ReplyDelete