Freiling's axiom of symmetry states 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$.

This principle turns out to be equivalent to the failure of the continuum hypothesis, a fact on which I spoke today at the CUNY math graduate student colloquium, Freiling's axiom of symmetry or, throwing darts at the real line.

Informally, the axiom asserts that 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.

At the conclusion of the talk I had assigned an exercise to the audience to prove the finite analogue of the axiom:

**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$. (See my blog post.)

That is, for any concept of smallness $k$, there is a large size $n$ such that whenever we attach a small subset $A_x$ to each element $x$ of a large set $X$, then there are two independent elements, neither of which are in the set attached to the other.

Here is one way to see it. 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.

It seems unlikely to me that this argument gives the optimal bound on the size of $n$, since first of all it is simply the first argument I thought about, and secondly, the argument gives more than is necessary, since it shows with $n>k^2+k$ that we can find at least one of the pair of independent elements inside any $k+1$ size subset of $X$ and the other outside. So perhaps we might hope for a smaller bound. MathOverflow is overrun with talented finite combinatoricists, and I am hoping they can help me find the optimal size:

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

That is, what is the smallest size $n$ for which the conclusion of the finite axiom of symmetry holds for assignments in a set of size $n$ to subsets of size $k$?

Please feel free to post better bounds than I have given, even if you don't know it is optimal. Or perhaps there is an easy argument for the optimal bound.

counton the MO combinatoricists! $\endgroup$3more comments