7
$\begingroup$

I am dealing with the following problem :

I need to create the smallest possible set $\{(x_i,y_i) \in [n]^2, x_i\neq y_i\}$ for $n$ given, such that :

$\forall p \in \mathcal{S}_n, \exists i,j$ such that $p(x_i)=x_j$ and $p(y_i)=y_j$.

What I tried to do was, for a given set, express the number of permutations covered by all the couples, but then I need to pick the couples so that I will minimize the intersections between the $(n-2)!$ permutations each time.

Has this problem been encountered before, or would you have any idea on how I could find the optimal set ? Sorry if I'm not being clear, I already have problems expressing the problem simply. Thank you in advance !

Edit : An example, for $n=3$ : With the set {(1,2),(2,1),(3,2),(1,3)}, I can cover all the permutations :

$e$ : (1,2) is sent to (1,2)

$(12)$ : (1,2) is sent to (2,1)

$(13)$ : (1,2) is sent to (3,2)

$(23):$ (1,2) is sent to (1,3)

$(123)$ : (1,3) is sent to (2,1)

$(132)$ : (1,3) is sent to (3,2)

And this is actually the smallest cardinality I can have to verify the condition.

Improve this question
$\endgroup$
7
  • $\begingroup$ @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. $\endgroup$
    – Alice J.
    Commented Apr 4, 2017 at 15:25
  • $\begingroup$ 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$? $\endgroup$
    – Zach Teitler
    Commented Apr 4, 2017 at 15:55
  • $\begingroup$ @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. $\endgroup$
    – Alice J.
    Commented Apr 4, 2017 at 16:03
  • 3
    $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Apr 4, 2017 at 18:33
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Apr 5, 2017 at 13:10

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .