What is the optimal size in the finite axiom of symmetry?

Question

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.

Answer 1

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

Answer 2

Suppose we have $|A|=n\in\mathbb N,$ and $A_x\in\binom Ak$ for each $x\in A,$ such that for any two distinct elements $x,y\in A,$ either $x\in A_y$ or $y\in A_x.$ Define a tournament $T$ on the vertex-set $V(T)=A$ so that $xy\in E(T)\implies y\in A_x.$ Then the score (outdegree) of each vertex is $\le k.$ Since the sum of all the scores is $\binom n2=\frac{n(n-1)}2,$ the average score is $\frac{n-1}2,$ whence $\frac{n-1}2\le k,$ i.e., $n\le2k+1.$

That is, if $|A|\ge2k+2,$ and if $|A_x|\le k$ for each $x\in A,$ then there exist two distinct elements $x,y\in A$ with $x\notin A_y$ and $y\notin A_x.$

On the other hand, it is quite easy to construct a tournament on $2k+1$ vertices in which each vertex has score $k;$ namely, put the vertices on a circle, and draw directed edges from each vertex to the next $k$ vertices clockwise.

P.S. Replacing "distinct" with "not necessarily distinct" amounts to imposing the condition $x\in A_x$ which amounts to replacing $k$ with $k-1.$

Answer 3

This seems really easy? Let $A \subseteq X^2$ be the set of all $(x,y)$ such that $y \in A_x$, and let $A^r$ be the reflection of this across the main diagonal. You are asking whether $A\cup A^r = X^2$. Suppose, for a contradiction, that $n \ge 2k$ and that $A\cup A^r = X^2$. Then $A$ must certainly contain the diagonal of $X^2$, so by the Principle of Inclusion and Exclusion, we have

$|X^2| = |A\cup A^r| = |A| + |A^r| - |A \cap A^r| \le 2nk - n < n^2 = |X^2|,$

a contradiction. On the other hand, if $n \le 2k-1$ then we can take $X = \mathbb{Z}/n$ and $A_x = \{x, x+1, ..., x+k-1\}$, so that $A = \{(x,y) \mid y-x \in \{0, ..., k-1\}\}$.