Skip to main content
MathOverflow

Return to Answer

added 710 characters in body
Source Link
Peter Mueller
Peter Mueller
  • 22.6k
  • 1
  • 75
  • 107

As pointed out by Derek Holt, there is the easy upper bound $224$. There is a clique of size $222$ (which I don't write down heregiven below). I don't know ifAn integer linear program formulation, together with the solver gurobi, shows that there is ano clique of size $223$. UsingActually this is not a proven result, because the integer linear program solver gurobi one can showILP 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 of sizemeeting 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, an integer linear program formulation and gurobi tellquickly tells that the maximum clique size is $55$.

Strictly speaking thisHere is notthe 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 proven resultclique of size $222$ is given by $(1\,6\,8)(3\,4)$ and $(1\,6\,8)(2\,3)$, becausetogether with the ILP solvers rely on real number relaxations, and rounding errors could erroneously rule out possible solutions (which I never saw an example for$55\cdot4$ permutations 123-4, though)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.

There is a clique of size $222$ (which I don't write down here). I don't know if there is a clique of size $223$. Using the integer linear program solver gurobi one can show that there is no clique of size $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, an integer linear program formulation and gurobi tell that the maximum clique size is $55$.

Strictly speaking 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).

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.

Source Link
Peter Mueller
Peter Mueller
  • 22.6k
  • 1
  • 75
  • 107

There is a clique of size $222$ (which I don't write down here). I don't know if there is a clique of size $223$. Using the integer linear program solver gurobi one can show that there is no clique of size $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, an integer linear program formulation and gurobi tell that the maximum clique size is $55$.

Strictly speaking 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).