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
    Commented 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
    Commented 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
    Commented Feb 20, 2016 at 11:58
  • 1
    $\begingroup$ Now I have one of size $218$. That's getting close! $\endgroup$
    – Derek Holt
    Commented 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
    Commented 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .