Timeline for Size of union of a set of subsets and its permutations
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 11, 2012 at 23:00 | comment | added | Sam Hopkins | 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? | |
| Jul 11, 2012 at 3:52 | comment | added | Zack Wolske | 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. | |
| Jul 10, 2012 at 21:15 | comment | added | Sam Hopkins | 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. | |
| Jul 10, 2012 at 21:01 | comment | added | Zack Wolske | 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. | |
| Jul 10, 2012 at 20:20 | history | asked | Sam Hopkins | CC BY-SA 3.0 |