7
$\begingroup$

Consider the alternating group graph, here defined as a Cayley graph on the alternating group $A_n$ using the generating set $\{(1,2,3),(1,2,4),\dotsc,(1,2,n),(1,n,2),\dotsc,(1,4,2),(1,3,2)\}$. Note that when $n=3$, the graph reduces to a triangle.

Observing that the clique size is just $3$ (this can be seen by observing the structure around the identity), I propose that the graph is properly $3$-colorable for all $n$. But, can this be proved? I suppose using left cosets of $A_3$ with respect to $A_n$ would help us here. In fact, it helped in getting $3$-coloring for $A_4$. Whereas, I am struck even for $A_5$. The SageMath software gives me the expected result up to $A_6$. Any hints?

$\endgroup$

2 Answers 2

5
$\begingroup$

So I believe that $\chi(A_7) > 3$, but this relies on some computations that require verification.

But I will start by giving some SageMath code that computes the graph, finds an independent set of size $840$, and then shows that this independent set is not a colour class in any 3-colouring.

The code is a bit clunky and roundabout because I did not originally do the computations in this order, or using SageMath, but I want to give something that anyone can at least verify.

First construct the graph, using a7 as the group and cset as the connection set, and its automorphism group.

a7 = groups.permutation.Alternating(7)
cset = [a7([(1,2,3)]), a7([(1,2,4)]), a7([(1,2,5)]), a7([(1,2,6)]),a7([(1,2,7)])]
cset = cset + [x^-1 for x in cset]
el = list(a7)
g = Graph([range(len(el)), lambda i, j: el[i]^-1*el[j] in cset])
aut = g.automorphism_group()

Now (up to conjugacy) there is a unique subgroup of order $3360$ in the automorphism group with two orbits, one of length $840$ and the other of length $2 \times 840$.

I claim that the orbit of length $840$ is an independent set in the graph, and I also claim that the graph induced by the second orbit is not bipartite, thereby showing that this independent set is not a colour class in a 3-colouring.

Unfortunately, I do not know how to get SageMath to quickly find subgroups of a particular order, and the group aut is sufficiently large to cause my laptop to grind to a halt if I ask it to find all conjugacy classes of subgroups.

But let's attack it in a roundabout way. The group aut has order $604800$ and so it has a Sylow 7-subgroup $S$ of order $7$. The group $S$ has $360$ orbits of size $7$ and (I claim) a suitable collection of $120$ of these orbits is an independent set of size $840$.

s7 = aut.sylow_subgroup(7)
orbs = [Set(orb) for orb in s7.orbits()]
orbitgraph = Graph([range(len(orbs)), lambda i, j: i != j and g.subgraph(orbs[i].union(orbs[j])).num_edges() == 0])
clmax = orbitgraph.clique_maximum()
isetorbs = [orbs[i] for i in clmax]
iset = Set()
for orb in isetorbs:
    iset = iset.union(orb)
iset = sorted(iset)

This code calculates the orbits, then forms the “compatibility graph” on the orbits, where two orbits are connected by an edge if the two orbits can co-exist in an independent set. Then SageMath computes the maximum clique of this graph, and finally unpacks everything to get the independent set of size $840$.

Then just check that this is actually an independent set, and that its complement is not bipartite.

g.subgraph(iset).num_edges() == 0
g.subgraph([v for v in g.vertices() if v not in iset]).is_bipartite()

In fact, the complement of the 840-set has odd girth 9.

Finally, I believe that up to isomorphism there are no other independent sets of size 840 in $A_7$, and therefore there is no $3$-colouring. But I want to do some more double-checking before then.

$\endgroup$
7
  • $\begingroup$ Your code works fine on SageMath, and gives the result of false. $\endgroup$
    – vidyarthi
    Jun 28 at 11:10
  • $\begingroup$ 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? $\endgroup$
    – vidyarthi
    Jun 28 at 11:25
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 29 at 0:13
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 29 at 11:17
  • 2
    $\begingroup$ @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. $\endgroup$ Jun 29 at 13:15
5
$\begingroup$

It is easy to see that the chromatic number $\chi(G)$ of graph $G$ of order $n$ and the independence number $\alpha(G)$ are related by the inequality $\alpha(G)\geq n/\chi(G)$. Therefore if $\chi(G)=3$, the graph $G$ has an independent set of size $\geq n/3$.

The alternating group graph $AG_n$ is a Cayley graph of the alternating group $A_n$ given by $S=\{(1,2,k)^{\pm1}| k=3,\ldots,n\}$. Thus, $AG_n=\operatorname{Cay}(A_n,S)$ is the graph with vertex set $A_n$ and edge set $\{(\tau,\tau\sigma)\,\mid\,\tau\in A_n,\sigma\in S\}$.

Hence if $\chi(AG_n)=3$, then $\alpha(AG_n)\geq n!/6$.

However, we know that $\alpha(AG_3)=1$, $\alpha(AG_4)=4$, $\alpha(AG_5)=20$, and $\alpha(AG_6)=120$, but the value for $\alpha(AG_7)$ is apparently not known (Stan Wagon, pers. comm., June 27, 2022), (see also Alternating group graph).

Addendum.

To complete the picture, some simple remarks about the coloring of the graph $AG_n$ for $n=4,5,6$.

$n=4$. Let $V$ be a subgroup of Klein in $A_4$. The sets $V$, $V(123)$, and $V(132)$ are independent since $V$ does not contain cycles of length $3$.

$n=5$. Let $D=\operatorname{gr}((12345),(15)(24)$. The subgroup $D$ has order $10$ and obviously contains no cycles of length $3$. Also let $S=\{(12k)^{\pm1}\mid k=3,4,5\}$.

  1. Choose three elements $v,x,y$ in the group $A_5$ with the following properties:

$(i)$ $Dv\cap S=\varnothing$;

$(ii)$ $x^{-1}Tx\cap S$=$y^{-1}Ty\cap S=\varnothing$, where $T$ is a set cycles of length $3$ in $Dv$.

$(iii)$ $D,Dv,Dx,Dvx,Dy,Dvy$ is a complete set of right cosets of $D$ in $A_n$.

This requires a little computation. I have consistently found that one can take $v=(13)(25)$, $x=(12)(34)$, $y=(12)(45)$.

Note that following the GAP package we multiply permutations from left to right, that is, $(12)(13)=(123)$.

  1. Since $D$ contains no cycles of length $3$, the set $Da$ is independent for any permutation $a\in A_5$.

  2. The sets $V_1=D\cup Dv$, $V_2=Dx\cup Dvx$, and $V_3=Dy\cup Dvy$ are independent. Prove, for example, that $V_2$ is independent. If $(u,w)$ is an edge connecting vertices of $V_2$, then we can assume $u\in Dx$, $w\in Dvx$ and $u^{-1}w\in S$. If $u=ax$, $w=bvx$, then $u^{-1}w=x^{-1}a^{-1}bvx\in S$. Therefore $a^{-1}bv\in Dv$ is a cycle of length $3$ and we get a contradiction with 1$(i)$.

  3. We have $V_i$ are independent, $|V_i|=20$, and $A_5=\cup_i V_i$.

$n=6$. Let $H=\operatorname{gr}((12)(34), (134)(256)$. The subgroup $H$ is isomorphic to the group $A_5$ and contains no cycles of length $3$. Also let $S=\{(12k)^{\pm1}\mid k=3,4,5,6\}$. It turns out that we can choose three permutations satisfying the properties 1$(i,ii,iii)$: $v=(35)(46)$, $x=(12)(35)$, $y=(12)(36)$.

Then, by the same scheme as above, we can prove that
The sets $V_1=H\cup Hv$, $V_2=Hx\cup Hvx$, and $V_3=Hy\cup Hvy$ are independent and hence we can color our graph $AG_6$ in three colors. And of course $|V_i|=120$.

Addendum 2.

$n=7$. The chromatic number of the graph $AG_7$ is $4$.

Since we know, thanks to Gordon Royle, that $\chi(AG_7)>3$ we only need to establish that this graph can be properly colored in $4$ colors. My computation was based on similar considerations as for the graphs $AG_5$ and $AG_6$.

In the group $A_7$ there is a subgroup of order $168$, which does not contain any cycles of length $3$. Let us denote this group by $H$. We can check that $H=\operatorname{gr}((1,4)(2,3), (2,4,6)(3,5,7) )$.

Therefore each right coset $Hx$, $x\in A_7$ is an independent set.

Hence, in turn, it follows that to check the independence of the set $V=Hx\cup Hy\cup\ldots$ it is sufficient to check that $H\cap xSy^{-1}=\varnothing$ for each pair of coset representatives lying in $V$, where $S=\{(1,2,3),(1,2,4),(1,2,5),(1,2,6),(2,1,3),(2,1,4),(2,1,5),(2,1,6)\}$.

I have found a collection of $4$ independent disjoint sets in $A_7$, each of them is a union of several right cosets: \begin{eqnarray*} V_1 &=& H+H(4,5,6)+H(4,6)(5,7)+H(3,4,6,7,5)+H(3,5,4,6,7),\\ V_2 &=& H(5,6,7)+H(4,5)(6,7)+H(4,7,6)+H(3,4,7,6,5),\\ V_3 &=& H(5,7,6)+H(4,6,5)+H(4,7)(5,6),\\ V_4 &=& H(4,5,7)+H(4,6,7)+H(3,4,5). \end{eqnarray*} (Here I use $'+'$ instead of $'\cup'$.)

Already after I found these sets I realized that they could be computed by a complete enumeration of all subsets of the 15 right cosets of the subgroup $H$ in group $A_7$. The total number of such subsets is a little more than 30 thousand.

Here are commands from the GAP package, which allow you to check the independence of each of $V_i$ and that they do not overlap. And the cardinality of these sets are respectively: 840, 672, 504, 504.

  1. We compute the order of the subgroup $H$ and the fact that $H$ does not contain cycles of length $3$:
G:=AlternatingGroup(7);;
H:=Subgroup(G,[(1,4)(2,3), (2,4,6)(3,5,7)]);; 
Order(H);
Filtered(H,x->Order(x)=3 and Order(Centralizer( G, x ))>9);
  1. Check that $V_i$ are independent sets. Let $R_i$ be the representatives of the right cosets lying in $V_i$ (here for $V_1$, for $V_i$ we should replace Combinations(R1,2) by Combinations(R2,2) and so on):
R1:= [ (), (4,5,6), (4,6)(5,7), (3,4,6,7,5), (3,5,4,6,7)];;
R2:= [ (5,6,7), (4,5)(6,7), (4,7,6), (3,4,7,6,5) ];;
R3:= [ (5,7,6), (4,6,5), (4,7)(5,6) ];;
R4:= [ (4,5,7), (4,6,7), (3,4,5) ];;
S:=[(1,2,3),(1,2,4),(1,2,5),(1,2,6),(1,2,7),(2,1,3),(2,1,4),(2,1,5),(2,1,6),(2,1,7)];;     
for a in Combinations(R1,2) do
    x:=a[1];
    y:=a[2];
    q:=IsEmpty(Intersection2(H, x*S*y^-1));
    if not q then break; fi;
od;
q;
  1. We compute the cardinality of sets. It suffices to check that all cosets are pairwise distinct. At the same time we check that the sets do not overlap:
R:=Concatenation(R1,R2,R3,R4);;
V:=List(R,x->H*x);;
V:=AsSSortedList(V);;
Size(V);

Note. Apparently for the computation of independent sets the graph whose vertices are right cosets of $H$ in $A_7$ and two vertices are connected by an edge can be useful if there is at least one edge between the elements of these cosets in the graph $AG_7$. I will try to draw this graph and post it here.

Addendum 3. (01.07.2022)

And this is the above graph with its $4$-vertice colouring.

enter image description here

$\endgroup$
13
  • 1
    $\begingroup$ But, $\chi(AG_3)=\chi(AG_4)=3$ in spite of $\alpha(AG_3)=1$. Did you mean $3!$ in the denominator of independence number $\endgroup$
    – vidyarthi
    Jun 27 at 16:37
  • 1
    $\begingroup$ @vidyarthi Thanks, corrected the typos. I asked Professor Stan Wagon today. $\endgroup$
    – kabenyuk
    Jun 27 at 16:51
  • $\begingroup$ Well, that's great. I hope I found a proof somewhere on arxiv. If you are working on the same topic, could we communicate regarding the same? $\endgroup$
    – vidyarthi
    Jun 27 at 16:57
  • 1
    $\begingroup$ @DavidESpeyer Up to $A_5$ there are vectors shorter than the desired vectors. $\endgroup$ Jun 28 at 5:33
  • 1
    $\begingroup$ @kabenyuk Not to worry - it happens to all of us at some time or another. Just one remark - MO is more useful as a record of activity if edits that substantially alter the content of a post are explicitly highlighted in some way. As it stands, the old comments on your former post don't make much sense with respect to the edited post. $\endgroup$ Jun 28 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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