A Cayley graph challenge

Greg Cherlin showed that Henson’s graphs are Cayley graphs, so perhaps it is time to look again at the question:

Is Covington’s graph a Cayley graph?

Here, to start things off, is a simple fact:

Covington’s graph G is not a Cayley graph for the infinite cyclic group.

For suppose that it is. Then the vertices can be identified with integers, and there is a subset S of the natural numbers such that vertices x and y are joined if and only if |xy| ∈ S. Since G is isomorphic to its complement, we may without loss of generality suppose that 1 ∈ S. Let m be the smallest positive integer which is not in S.

Claim: If m does not divide x, then x ∈ S.

For suppose not, and let x be the smallest non-multiple of m which is not in S. Note that x > m. Consider the four vertices 0, x, m, xm. Since xm and x−2m (or 2mx) are in S, we see that {0,xm}, {xm,m} and {m,x} are edges. On the other hand, since x and m are not in S, {0,x}, {0,m} and {xm,x} are non-edges; so these four vertices induce a path, a contradiction.

So the claim is proved.

But now the complement of G is disconnected, since any two vertices lying in different congruence classes (mod m) are joined in G. But this contradicts the facts that G is connected and isomorphic to its complement.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s