Freiling's [axiom of symmetry](https://en.wikipedia.org/wiki/Freiling%27s_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](http://jdh.hamkins.org/freilings-axiom-of-symmetry-graduate-student-colloquium-april-2016/).


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](http://jdh.hamkins.org/the-finite-axiom-of-symmetry/).)


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.



What is the optimal size in the finite axiom of symmetry?
Given $k$, let $X=\{1,2,\dots,2k\}$. We must have $1$ in $A\_1$, else we could take $x=y=1$. We may assume $A\_1=\{1,2,\dots,k\}$. So $r$ is not in $A\_1$ for $r=k+1,k+2,\dots,2k$. So we must have $1$ in $A\_r$ for $r=k+1,k+2,\dots,2k$. That is, $1$ must be in $k+1$ of the sets $A\_r$ (since it's also in $A\_1$). But there's nothing special about $1$, so each of the elements $1,2,\dots,2k$ must be in $k+1$ of the sets $A\_r$. But there isn't room for $2k(k+1)$ elements in $2k$ sets of size $k$. Therefore, if $n=2k$, there must be $x$ and $y$ (possibly $x=y$) with $x$ not in $A\_y$, and $y$ not in $A\_x$. 


If $n=2k-1$, let $A\_1=\{1,2,\dots,k\}$, $A\_2=\{2,3,\dots,k+1\}$, and so on, to $A\_{2k-1}=\{2k-1,1,2,\dots,k-1\}$, then there are no $x$ and $y$ with $x$ not in $A\_y$ and $y$ not in $A\_x$. 


