5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jul 10, 2012 at 21:01
  • $\begingroup$ 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. $\endgroup$ Jul 10, 2012 at 21:15
  • $\begingroup$ 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. $\endgroup$ Jul 11, 2012 at 3:52
  • $\begingroup$ 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? $\endgroup$ Jul 11, 2012 at 23:00

0

Your Answer

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

Browse other questions tagged or ask your own question.