4
$\begingroup$

Following this post, I have been thinking about the problem posed by Erdős,

Does there exist a constant $c > 0$ such that every subset $A$ of the plane of area more than $c$ contains the vertices of a triangle of unit area?

I think the spirit of the problem justifies assuming $A$ is measurable (counterexamples exist for non-measurable sets, see post), and so we can use the following to simplify:

If $A$ is measurable, with finite measure $a$, then for every $\epsilon >0$ there exists an $n \in \mathbb{N},$ $r > 0,$ such that $A$ can be filled with $n$ non-overlapping disks of radius $r$ with combined area $a' = n \pi r^2 > a(\eta_h -\epsilon)$, where $\eta_h \approx 0.9$ is the optimal packing density of disks in the plane.

So we can reduce to just considering sets of nonoverlapping disks of equal radius $r$. The problem becomes,

Does there exist a constant $c > 0$ such that every set $A$ of $n$ disks of radius $r$, with $n \pi r^2 > c$, contains the vertices of a triangle of unit area?

Now, we can scale such a set $A$ by $1/r$ (that is, probably expanding it, because probably $r < 1$.) and ask of the new set of $n$ unit disks, if $n\pi r^2>c$, for some $c$, must $A$ contain the vertices of a triangle of area $1/r^2$? Defining $\ell = c/{(\pi r^2)}$, if $\ell<n$, must $A$ contain the vertices of a triangle of area $\pi \ell/c$? That is, must $A$ contain vertices of triangles of all areas $< \pi n/c$? So, setting $c' = c/\pi$ (to get rid of the constant), we get the equivalent question,

Does there exist a constant $c' > 0$ such that every set of $n$ unit disks in the plane must contain the vertices of triangles of all areas $< n/c'$?

Say we are given some such $c'$, and we must determine the conditions under which a triangle of area $c < c'$ must have vertices in $A$. Now, since two unit disks with centers a distance $> n/c$ apart always contain the vertices of a triangle of area $n/c$, we can assume that these disks are all within a distance of $n/c$ of each other. Thus, they all lie in a big disk $D$ of radius $\frac{2n}{\sqrt{3}c}+2$, and area $d_c$.

We can then look at pairs of points within this disk that must not both lie in $A$. That is, pairs of points in $D$ which, together with some point in $A$, form the vertices of a triangle of area $n/c$. We denote this set $\mathcal{F}_2$.

Using the usual product measure, we denote the measure of $\mathcal{F}_2 \in D \times D$, $m_2$. The measure of $D \times D$ itself is $d_c^2$. We can show that,

$m_2$ = $\Omega(cd_c^2/\sum_{1 \leq i \leq j \leq n} {s_{ij}})$

as a function of $c$ and $n$, where $s_{ij}$ is the distance between the centers of the $i^\text{th}$ and $j^\text{th}$ disks.

Letting $S = \sum_{1 \leq i \leq j \leq n} {s_{ij}}$, we win if $S = o(c)$ (S a function of both $c$ and $n$).

Now, we can also look at the set of individual points in $D$ that are "forbidden," i.e., together with two points from $A$, form a triangle of area $n/c$. We denote this set $\mathcal{F}_1$, and take it as a subset of $D$, with measure denoted $m_1$.

It can be shown that the set of points $f_{ij}$ that are forbidden due to forming a triangle of area $n/c$ with points in disks $i$ and $j$, which we say has measure $m_{1,ij}$, satisfies,

$m_{1,ij} = \Omega(d_c/s_{ij})$

$\mathcal{F}_1$ is the union of the $f_{ij}$. Naïvely summing the $m_{1,ij}$, we get the sum $m_1'$ of their measures is,

$m_1' = \Omega(d_cS)$.

If this were indeed $\mathcal{F}_2$, we would win if $S \neq o(c)$, since $d_c \sim \frac{2n}{\sqrt{3}c}$ (winning meaning $m_1 > d_c$, a contradiction). Since, from before, if $S = o(c)$ we also win, the problem would be finished. You could simply pick $c$ large enough, and either $\mathcal{F}_1$ or $\mathcal{F}_2$ would exceed the measure of its superset, a contradiction.

But of course the area of a union is not the sum of the areas. And I can't find a way to deal with the intersections of the $m_{1,ij}$. I also can't tell if I'm really right next to a solution, or if I'm just hitting the brick wall surrounding the problem in a different spot.

I hope you found this interesting, at least. If the way I put growth rates is too confusing, I'll post some updates to clarify. If you have any ideas, please let me know.

$\endgroup$
  • $\begingroup$ (Lebesgue) measurable sets with positive measure do not necessarily contain any disks with positive radius at all, e.g. unit disk - rational points. Nevertheless your circle problem seems interesting in its own right. $\endgroup$ – Xiaoyu He Sep 17 '15 at 3:25
  • $\begingroup$ Your equivalence argument is not too hard to fix by first going to compact convex sets and then packing with circles as in the answer from the previous question. $\endgroup$ – Xiaoyu He Sep 17 '15 at 3:47
  • $\begingroup$ Yes, even if measurable is not enough, it should be no problem. In the original post it is mentioned that we can equivalently go to compact convex sets. Thank you. $\endgroup$ – Jason Eliot Sep 17 '15 at 17:53
2
$\begingroup$

The Heilbronn triangle problem seems closely related, and the method of Roth for a power-saving upper bound goes through a similar area-covering argument. Let me sketch the basic idea Roth uses to show that for any $n$ points in a unit disk, some three of them form a triangle of area $<n^{-1-\epsilon}$. All constants are missing intentionally.

Suppose that there are $n$ points in the unit disk $D$ no triple of whom form a triangle of area $<\Delta$, and $\Delta$ is large (i.e. $~1/n$ contrary to our expectations). Then, this means that for every pair of points $t = (p_1, p_2)\in D^2$, the infinite linear strip $H(t,\Delta/d(t))$ of width $\Delta/d(t)$ around the line $p_1 p_2$, where $d(t)$ is the distance between $p_1,p_2$, contains no other points of our set.

Roth then finishes by (A) if the pair $t$ is close together, as some pairs have to be by pigeonhole (~$1/\sqrt{n}$), this means that the corresponding linear strip $H(t,\Delta/d(t))$ contains much less than the expected number of points ($\approx \sqrt{n}$), and (B) if instead of considering all pairs $t$ we restrict to some subcollection of pairs with similar slopes, the corresponding regions essentially can't intersect (or else there would be a small-area triangle).

You might want to look for an analogue of (B): some subfamily of the all your pairs $f_{ij}$ have some structure making them repel one another such as having similar slopes. It might be possible to transform the problem so that if two pairs have similar slopes and the corresponding $f_{ij}$ intersect within the disk, among the four points involved some three will give you the triangle you want.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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