The finite axiom of symmetry

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. The axiom of symmetry asserts that if you assign to each real number $x$ a countable set $A_x\subset\mathbb{R}$, then there should be two reals $x,y$ for which $x\notin A_y$ and $y\notin A_x$.

Informally, if you have attached to each element $x$ of a large set $\mathbb{R}$ a certain comparatively small subset $A_x$, then there should be two independent points $x,y$, 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 $k$ there is a sufficiently large finite number $n$ such that for any set $X$ of size $n$ and any assignment $x\mapsto A_x$ of elements $x\in X$ to subsets $A_x\subset X$ of size $k$, there are elements $x,y\in X$ such that $x\notin A_y$ and $y\notin A_x$.

Proof. Suppose we are given a finite number $k$. Let $n$ be any number larger than $k^2+k$. Consider any set $X$ of size $n$ and any assignment $x\mapsto A_x$ of elements $x\in X$ to subsets $A_x\subset X$ of size at most $k$. Let $x_0,x_1,x_2,\dots,x_k$ be any $k+1$ many elements of $X$. The union $\bigcup_{i\leq k} A_{x_i}$ has size at most $(k+1)k=k^2+k$, and so by the choice of $n$ there is some element $y\in X$ not in any $A_{x_i}$. Since $A_y$ has size at most $k$, there must be some $x_i$ not in $A_y$. So $x_i\notin A_y$ and $y\notin A_{x_i}$, and we have fulfilled the desired conclusion. QED

Question. What is the optimal size of $n$ as a function of $k$?

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 $k+1$ size subset of $X$, which is a stronger property than requested. So it seems likely to me that the optimal bound will be smaller.

5 thoughts on “The finite axiom of symmetry”

1. 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.

2. Ali on said:

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.