Timeline for 3-coloring the alternating group graph
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 1, 2022 at 3:55 | history | edited | LSpice | CC BY-SA 4.0 |
TeX quotes -> Unicode quotes, while this is on the front page
|
| Jun 29, 2022 at 23:28 | comment | added | Gordon Royle | @vidyarthi Yes they are all independent sets, but they are all isomorphic. | |
| Jun 29, 2022 at 19:35 | comment | added | vidyarthi | @GordonRoyle so those 180 solutions are all the independent sets? I didnt quite get it | |
| Jun 29, 2022 at 13:15 | comment | added | Gordon Royle | @DavidESpeyer Because the graph is vertex-transitive, a $840$-coclique meets every triangle (maximum clique) in exactly one point. This can be written as a constraint satisfaction problem, with one variable per vertex and one constraint per triangle, and the CSP solver that I usually use (Minion) can find all 180 solutions in a couple of minutes. | |
| Jun 29, 2022 at 11:17 | comment | added | David E Speyer | How can you see that there are no other independent sets of 840 ? This seems like the hardest part of the (very nice) computation to justify to me. | |
| Jun 29, 2022 at 0:13 | comment | added | Gordon Royle | @vidyarthi I actually have no real sense as to what might happen in the long run, which makes this quite interesting to me. Probably the first thing to do is to verify that cocliques of size $n!/6$ always exist, and the most promising, perhaps only, way to tackle this is by analysing the group. The stabiliser of the 840-coclique is $\mathrm{PSL}(3,2) \times (C_5 : C_4)$ so understanding that might help. | |
| Jun 28, 2022 at 11:25 | comment | added | vidyarthi | So then, can we give an upper bound on the chromatic number of the graphs? This seems a strange phenomenon to me-for six cases straight, the chromatic number is $3$, for the next graph, the chromatic number increases! So is the chromatic number for $n$ is unbounded? | |
| Jun 28, 2022 at 11:11 | vote | accept | vidyarthi | ||
| Jun 28, 2022 at 11:10 | comment | added | vidyarthi | Your code works fine on SageMath, and gives the result of false. | |
| Jun 28, 2022 at 9:56 | history | edited | Gordon Royle | CC BY-SA 4.0 |
minor update for readability
|
| Jun 28, 2022 at 9:48 | history | answered | Gordon Royle | CC BY-SA 4.0 |