10
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Or perhaps the combinatoricists already have a standard name for what I am calling the finite axiom of symmetry? If so, what is it? $\endgroup$ Apr 12, 2016 at 2:35
  • 1
    $\begingroup$ Is it assumed that the two elements $x$, $y$, are distinct? Say $k=1$, and $n=3>k^2+k$, $X=\{a,b,c\}$, $a\mapsto\{b\}$, $b\mapsto\{c\}$, $c\mapsto\{a\}$. Then $a$ is not in $A_b$, but $b$ is in $A_a$; $b$ is not in $A_c$, but $c$ is in $A_b$; $c$ is not in $A_a$, but $a$ is in $A_c$. $\endgroup$ Apr 12, 2016 at 2:53
  • $\begingroup$ My proof does not assume that $x$ and $y$ are distinct, as your example shows. Namely, in your example we can take $x=a$ and $y=a$ to fulfill the axiom. In the infinite cases that inspire the question, we may always assume $x\in A_x$ without loss, since this doesn't change the size, and in that case, one can equivalently assume $x\neq y$. But in the finite case of course this changes the size. Feel free to post an answer for the case where you interpret the principle as requiring $x\neq y$. This may amount to changing $k$ to $k+1$. $\endgroup$ Apr 12, 2016 at 2:58
  • $\begingroup$ That is, if you want to insist that $x\neq y$, then my argument shows that $n>(k+1)(k+2)$ suffices, since for any assignment, we modify it by insisting $x\in A_x$, which may make the sizes $k+1$, and then apply my argument. But in this case, we will have $x\neq y$ in order to have independence. $\endgroup$ Apr 12, 2016 at 3:11
  • $\begingroup$ Thanks for all the answers, everyone! I knew I could count on the MO combinatoricists! $\endgroup$ Apr 12, 2016 at 12:10

3 Answers 3

8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Great! It seems like this solves it. Could you translate this solution for the case where we insist $x\neq y$? $\endgroup$ Apr 12, 2016 at 3:39
  • $\begingroup$ Looks like @bof has done this. $\endgroup$ Apr 12, 2016 at 5:33
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.