Skip to main content
MathOverflow

Return to Answer

TeX quotes -> Unicode quotes, while this is on the front page
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

This code calculates the orbits, then forms the ``compatibility graph''“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$.

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$.

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$.

minor update for readability
Source Link
Gordon Royle
Gordon Royle
  • 12.7k
  • 1
  • 51
  • 73
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(a7el)), lambda i, j: el[i]^-1*el[j] in cset])
aut = g.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(a7)), lambda i, j: el[i]^-1*el[j] in cset])
aut = g.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()
Source Link
Gordon Royle
Gordon Royle
  • 12.7k
  • 1
  • 51
  • 73

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(a7)), 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.