Skip to main content
MathOverflow

Return to Question

fixed any confusion over the role of Z_3^n
Source Link
Colin Tan
Colin Tan
  • 331
  • 4
  • 12

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 an elementary finite abelian $3$-group, thus its vertex set is necessarily isomorphic to $\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.

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 an elementary finite abelian $3$-group, thus its vertex set is necessarily isomorphic to $\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.

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.

Source Link
Colin Tan
Colin Tan
  • 331
  • 4
  • 12

Is there a ternary Cayley graph on 27 vertices that is a non-complete core?

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 an elementary finite abelian $3$-group, thus its vertex set is necessarily isomorphic to $\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.