Timeline for Smallest set of couples in [n] stable by permutations
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2017 at 15:03 | comment | added | domotorp | @Alice I'm just trying to understand why $2n-4$ and not $2n-2$ is the value you're trying to prove. If I understood your graph theory problem well, even there $2n-2$ seems to be the natural lower bound. Do you have a lower bound of size $2n-4$? Btw, if I were you, I would add this interesting connection to packing digraphs as a motivation to the question. | |
| Apr 5, 2017 at 14:46 | comment | added | Alice J. | @domotorp I'm trying to prove a graph theory conjecture saying that every digraph with less than $2n-4$ edges admits a packing with itself, and it's equivalent to say that every of those sets with cardinality $2n-4$ does not cover all the permutations, this is why only the minimum value is interesting in this case. I thought it would be easier to see it this way but I guess not. | |
| Apr 5, 2017 at 13:10 | comment | added | domotorp | Why are you trying to prove $2n-4$? The best general construction I see is to take $(1,i)$ and $(i,1)$ for each $i>1$, in total $2n-2$ pairs. This works because one can take $(1,p^{-1}(1))$ and $(p(1),1)$ if $p(1)\ne 1$, and $(1,p^{-1}(2))$ and $(1,2)$ otherwise. | |
| Apr 4, 2017 at 18:33 | comment | added | Gerhard Paseman | If you post as an answer what you believe minimal sets are for some n, you or someone else can look up in OEIS for possible earlier references. Gerhard "Indexing Concepts By Number Sequence" Paseman, 2017.04.04. | |
| Apr 4, 2017 at 16:03 | comment | added | Alice J. | @ZachTeitler Thanks. For $n=4$ the minimum is 4 too. I'm actually trying to prove that the minimal cardinality is greater than $2n-4$ $\forall n$. I wrote a script that was able to test it until $n=12$ only. | |
| Apr 4, 2017 at 15:55 | comment | added | Zach Teitler | Any set of size strictly greater than $(n^2-n)/2$ will work. (Pigeonhole: the sizes of the sets $A$ and $pA$ add up to more than $n^2-n$, so they have to intersect.) For $n=3$, any set of $4$ pairs will work; for $n=4$, any set of $7$ pairs will work. Do you know what is the actual smallest size for $n=4$? | |
| Apr 4, 2017 at 15:40 | history | edited | Alice J. | CC BY-SA 3.0 |
added 404 characters in body
|
| Apr 4, 2017 at 15:25 | comment | added | Alice J. | @coudy Sorry, the $x_i$ are not necessarily distinct, only the couples are. By [n] I mean the integers from 1 to $n$, and the smallest set is the set which has the smallest cardinality. | |
| Apr 4, 2017 at 15:13 | history | asked | Alice J. | CC BY-SA 3.0 |