2
$\begingroup$

Is there a non-complete ternary Cayley graph that is a core with $3^3 = 27$ vertices?

By a ternary Cayley graph, I mean a (simple, undirected) graph whose vertex set is $\mathbb{Z}_3^n := \bigoplus_{i = 1}^n \mathbb{Z}/3\mathbb{Z}$ for some nonnegative integer $n$, and whose edges are determined by a so-called connection set $C \subseteq \mathbb{Z}_3^n \setminus \{0\}$ that is closed under taking negation, i.e. $-C = C$. Namely, two vertices $x, y \in \mathbb{Z}_3^n$ are adjacent if and only if $x - y \in C$. Note that the condition $-C = C$ ensures that the adjacency relation is symmetric, thus the Cayley graph is undirected. That $C$ does not contain the zero vector ensures that there are no loops. The Cayley graph on $\mathbb{Z}_3^n$ with connection set $C$ is denoted by $\mathrm{Cay}(\mathbb{Z}_3^n, C)$.

A graph is a core if all its endomorphisms are automorphisms. An endomorphism of a graph is an endomap of its vertex set such that edges are sent to edges.

It can be shown that every ternary Cayley graph core with at most $3^2= 9$ vertices is necessarily complete. In fact it can be shown that any ternary Cayley graph with $3^3$ of degree $|C| \le 10$ is not a core. So the minimal example of a ternary Cayley graph core with $3^3$ vertices must have degree at least $12$. I conjecturely propose that the following Cayley graph with $3^3$ vertices of degree $12$ is a noncomplete core: $$\mathrm{Cay}(\mathbb{Z}_3^3, B \cup -B), \text{ where } B =\{i, j, k, i +j, i + k, i + j + k\}).$$ where $i = (1, 0, 0)$, $j = (0, 1, 0)$, $k = (0, 0, 1)$. However, I am happy to get any other construction on $3^3$ vertices.

P.S. I am reposting my question here from Math Stack Exchange. I put a bounty there, but have not got a response over 3 days. As the bounty is expiring in 3 days, I thought I might post my question here on Math Overflow, so that whoever would answer can win my bounty. If re-posting questions from MSE before the bounty is over is wrong etiquette, I stand corrected. I am happy for any answer posted here, or posted over at MSE to win my bounty.

$\endgroup$
4
  • $\begingroup$ “Its vertex set is isomorphic to $\mathbb{Z}_3^n$” just means it has $3^n$ vertices. You mean that it’s equal to that set (this also matches how you use the vertices later). $\endgroup$ Commented Nov 15 at 11:08
  • $\begingroup$ you may regard the vertex set as the underlying set of $\mathbb{Z}_3^n$. $\endgroup$
    – Colin Tan
    Commented Nov 15 at 12:39
  • $\begingroup$ however I require that the group be elementary abelian. I do not allow $\mathbb{Z}_{27}$, which also has $3^3$ vertices. $\endgroup$
    – Colin Tan
    Commented Nov 15 at 12:42
  • $\begingroup$ Sure. But right now your definitions are not saying that. Saying that a set is isomorphic to another is just saying that they have the same cardinality, which is much less than you want. Your new formulation has the same issue. It seems much easier to just say that you have a graph which is the Cayley graph of $\mathbb{Z}_3^n$ with respect to some symmetric generating set $C$. $\endgroup$ Commented Nov 15 at 13:40

1 Answer 1

4
$\begingroup$

There are two such graphs on $27$ vertices, one with degree $12$ and one with degree $14$.

To get the degree $14$ example, just add $j+k$ to the connection set of your degree $12$ example.

Both of these graphs have clique number $4$, hence they cannot have a complete core. So either they are cores, or they have a $9$-vertex core; we will rule out the second case.

By general theory, this hypothetical $9$-vertex core is a vertex-transitive graph with the same chromatic number as the original graph.

However these two graphs have chromatic number at least $7$, and there are no non-complete $9$-vertex vertex-transitive graphs with chromatic number more than $5$.

There are only $25$ connected Cayley graphs of $\mathbb{Z}_3^3$ and so it is not difficult to test them all.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .