At the conclusion of my talk today for the CUNY Math Graduate Student Colloquium, Freiling’s axiom of symmetry Or, throwing darts at the real line, I had assigned an exercise for the audience, and so I’d like to discuss the solution here.
![By PeterPan23 [Public domain], via Wikimedia Commons](https://upload.wikimedia.org/wikipedia/commons/f/fb/Darts_in_a_dartboard.jpg)
The axiom of symmetry asserts that if you assign to each real number a countable set , then there should be two reals for which and .
Informally, if you have attached to each element of a large set a certain comparatively small subset , then there should be two independent points , meaning that neither is in the set attached to the other.
The challenge exercise I had made is to prove a finite version of this:
The finite axiom of symmetry. For each finite number there is a sufficiently large finite number such that for any set of size and any assignment of elements to subsets of size , there are elements such that and .
Proof. Suppose we are given a finite number . Let be any number larger than . Consider any set of size and any assignment of elements to subsets of size at most . Let be any many elements of . The union has size at most , and so by the choice of there is some element not in any . Since has size at most , there must be some not in . So and , and we have fulfilled the desired conclusion. QED
Question. What is the optimal size of as a function of ?
It seems unlikely to me that my argument gives the optimal bound, since we can find at least one of the pair elements inside any size subset of , which is a stronger property than requested. So it seems likely to me that the optimal bound will be smaller.
I asked the question on MathOverflow at http://mathoverflow.net/q/235949/1946.
There are at most kn doubles {x,y} with x ∈ Ay, so if k < (n-1)/2, some {x,y} contains two things and has neither x ∈ Ay nor y ∈ Ax.
and if I understand generalized rock-paper-scisors, the implied bound n > 2k + 1 is sharp.
Thanks! This bound agrees with the answers posted yesterday on MathOverflow—follow the link above.
Each time that I hear about Freiling’s “dart throwing problem” I can’t resist thinking about possible funny generalizations!
For example what happens if we change our weapon while practicing on the shooting range?!
Darts are kind of bullets with caliber zero! They only affect a single point of the target. But what happens if we try shooting at our target with a more powerful rifle with higher caliber which its bullets can affect a small piece of the target (of Lebesgue measure non-zero), say a very small disc?!
Intuitively there should be an upper limit for the truth of Freiling’s Axiom of Symmetry when we use weapons of higher caliber instead of darts because the bullets of such guns leave fewer unaffected places on the target and if we choose a super gun with a really big caliber, we can’t expect that the impact places of two bullets on our target have no intersection with each other.
I don”t know if the formal form of this intuitive generalization of Axiom of Symmetry is trivially false or not or even equivalent to it, but I thought it might be interesting to think about “real world intuition”-based generalizations.