MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For $[n] := \{1,...,n\}$, let $G$ be the set of all $\lceil n/2\rceil$-subsets of $[n]$. For a permutation $\rho \in S_{n}$, and some $F \subset G$, define $\rho(F)$ in the natural way: apply $\rho$ to each element in every set in $F$ and let $\rho(F)$ be the set of these new subsets. For example, if $F = \{ \{1,2\}, \{3,4\} \}$, and $\rho = 3241$ (in one-line notation), then $\rho(F) = \{\{2,3\},\{1,4\}\}$. Obviously $|\rho(F)| = |F|$.

Fixing some integer $k$, is there anything we can say about $K(n,k) := \min_{F \subset G, |F| = k} \max_{\rho \in S_n} |F \cup \rho(F)|$?

By symmetry considerations, for a fixed $F$, every $\lceil n/2\rceil$-subsets of $[n]$ is contained in the same number of $\rho(F)$'s, so for an "average" $\rho$ we have $\frac{|F \cap \rho(F)|}{|F|} = \frac{|F|}{|G|}$. That is, we can always find a $\rho$ such that $|F \cap \rho(F)| \leq \frac{|F|^2}{|G|}$. Then, $K(n,k) \geq 2k - \frac{k^2}{n \choose \lceil n/2 \rceil}$.

The question is, can we always (ever?) do much better than this average?

share|cite|improve this question
I think K(5,5) = 9. I can come back in a few hours to explain that. You certainly can't do better (assuming you take the least integer larger than the RHS) when $k^2 < {n \choose \lceil n/2 \rceil}$, or when $F=G$, and possibly some other large cases like that. – Zack Wolske Jul 10 '12 at 21:01
Yes, we have the trivial upper bound that $K(n,k) \leq \min \{2k, {n \choose \lceil n/2 \rceil} \}$, which, as you point out, takes care of the cases when $k$ is large or small. In the context that this problem came up, $k \approx \frac{1}{2}{n \choose \lceil n/2 \rceil}$. Taking $k$ to be some fraction of the total number of $\lceil n/2 \rceil$-subsets is the interesting case. – Sam Hopkins Jul 10 '12 at 21:15
The details of the proof didn't work out as nicely as I'd hoped, but it is true that K(5,5) = 9. The method is ad-hoc, and you might get more insight doing it yourself, but I'll post it if you'd like. It essentially breaks down the different sets of 5 subsets of size 2 (these are the same as subsets of size 3 by taking complements) into generic cases by considering how you can write 10 as a sum of 5 integers, each counting the number of times a specific digit appears in the set. Then you pick a permutation for each of the five cases. – Zack Wolske Jul 11 '12 at 3:52
Perhaps working that case out would be instructive. But I'm more interested in the limiting behavior than exact values. For instance, by the above lower bound and the trivial upper bound, we have: $\frac{3}{4} {n \choose \lceil n/2 \rceil} \leq K(n,\frac{1}{2}{n \choose \lceil n/2 \rceil}) \leq {n \choose \lceil n/2 \rceil}$ Which side is right asymptotically? What is $\lim_{n \to \infty} K(n,\frac{1}{2}{n \choose \lceil n/2 \rceil})$? Does this limit even exist? – Sam Hopkins Jul 11 '12 at 23:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.