4
$\begingroup$

Can someone calculate by computer or prove the subset of maximal order of pairwise non commuting elements in the set of conjugacy class containing $(123)(45)$ in $S_8$?

I mean a subset of conjugacy class containing $(123)(45)$ of maximal order all of its elements do not commute pairwisely.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ That sounds difficult! It is a maximal clique problem in a graph with $1120$ vertices, and the complexity of all known algorithms for finding maximal cliques appears to be exponential. By searching at random, I have found such a subset of size $188$, but maybe someone can beat that. $\endgroup$
    – Derek Holt
    Feb 19, 2016 at 13:48
  • 3
    $\begingroup$ Lovasz's theta upper bound shows that such a clique has size $\le224$, while mcqd (sicmm.org/konc/maxclique) quickly finds a clique of size $200$. $\endgroup$
    – Peter Mueller
    Feb 19, 2016 at 22:09
  • 1
    $\begingroup$ In fact it is not hard to prove the upper bound of $224$ directly because, for each of the $56$ triples $\{a,b,c\}$, you can choose at most $4$ pairwise non-commuting elements $(a,b,c)(x,y)$ and (as in JohnShareshian's answer), the only way to do this is to fix $x$ and use the four possible $y$. $\endgroup$
    – Derek Holt
    Feb 20, 2016 at 11:58
  • 1
    $\begingroup$ Now I have one of size $218$. That's getting close! $\endgroup$
    – Derek Holt
    Feb 20, 2016 at 15:36
  • 2
    $\begingroup$ While I understand the intent is to be polite, ultimately it may make the conversation for Derek Holt slightly less convenient that you use @Professor Holt as it will not show up in his inbox. To have notification what directly follows @ must match a beginning substring of username (without space). To follow what auto-complete suggests is simplest. If you feel you need to be formal I recommend: do not use an @ as part of the main text, and place the @username at the end or the start as an add-on. Put differently treat @username like an email-address that you cannot alter. $\endgroup$
    – user9072
    Feb 20, 2016 at 18:26

1 Answer 1

Reset to default
8
$\begingroup$

As pointed out by Derek Holt, there is the easy upper bound $224$. There is a clique of size $222$ (given below). An integer linear program formulation, together with the solver gurobi, shows that there is no clique of size $223$. Actually this is not a proven result, because the ILP solvers rely on real number relaxations, and rounding errors could erroneously rule out possible solutions (which I never saw an example for, though).

It is faster to see that there is no clique meeting the upper bound $224$: Consider the following graph with $280=56\cdot5$ vertices of the type $(A,a)$, where $A$ is a $3$-subset of $\{1,2,\dots,8\}$, and $a$ is in $\{1,2,\dots,8\}\setminus A$. Then $(A,a)$ and $(B,b)$ are adjacent if $A$ and $B$ are disjoint, and $a\in B$ or $b\in A$; or if $A$ and $B$ are distinct with a non-trivial intersection. Then a clique of size $224=56\cdot4$ in the original question would correspond to a clique of size $56$ in this graph (by the previous discussion by Shareshian and Holt). However, gurobi quickly tells that the maximum clique size is $55$.

Here is the clique of size $222$. Let abc-d denote the four permutations $(a\, b\, c)(d\, e)$ where $e\in\{1,2,\dots,8\}$ is different from $a,b,c,d$. Then a clique of size $222$ is given by $(1\,6\,8)(3\,4)$ and $(1\,6\,8)(2\,3)$, together with the $55\cdot4$ permutations 123-4, 124-6, 125-3, 126-4, 127-6, 128-4, 134-7, 135-6, 136-7, 137-6, 138-7, 145-6, 146-5, 147-5, 148-5, 156-3, 157-2, 158-3, 167-2, 178-2, 234-8, 235-7, 236-4, 237-4, 238-4, 245-3, 246-8, 247-5, 248-1, 256-3, 257-1, 258-3, 267-8, 268-4, 278-1, 345-7, 346-7, 347-8, 348-7, 356-8, 357-2, 358-1, 367-8, 368-7, 378-1, 456-8, 457-1, 458-1, 467-5, 468-5, 478-5, 567-2, 568-3, 578-2, 678-2.

Improve this answer
$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.