Mixing
![How does this series yield an irrational function [duplicate]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Are all n-dimensional hypercube graphs circulant and if so what is their circulant adjacency matrix?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Usually the adjacency matrix representation of the n-dimensional hypercube, $Q_n$, is given as
$$Q_n=beginbmatrixQ_n-1 & I \ I & Q_n-1 endbmatrix$$
where $Q_1$ is the adjacency matrix of $K_2$. Since the $1$-dimensional hypercube is $K_2$ and the $2$-dimensional hypercube is $C_4$ which are also circulant graphs I was wondering if all $n$-dimensional hypercubes are circulant graphs and if so what is the circulant matrix representation of their adjacency matrix.
graph-theory adjacency-matrix
asked Jul 21 at 3:07
amitsett
256
add a comment |Â
up vote
1
down vote
favorite
Usually the adjacency matrix representation of the n-dimensional hypercube, $Q_n$, is given as
$$Q_n=beginbmatrixQ_n-1 & I \ I & Q_n-1 endbmatrix$$
where $Q_1$ is the adjacency matrix of $K_2$. Since the $1$-dimensional hypercube is $K_2$ and the $2$-dimensional hypercube is $C_4$ which are also circulant graphs I was wondering if all $n$-dimensional hypercubes are circulant graphs and if so what is the circulant matrix representation of their adjacency matrix.
graph-theory adjacency-matrix
asked Jul 21 at 3:07
amitsett
256
What about $Q_3$? (the ordinary cube)
– Lord Shark the Unknown
Jul 21 at 3:10
I'm not sure. I thought no initially but according to a paper I was reading it is?
– amitsett
Jul 21 at 3:22
@LordSharktheUnknown $Q_3$ is not circulant. Thanks.
– amitsett
Jul 21 at 5:34
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Usually the adjacency matrix representation of the n-dimensional hypercube, $Q_n$, is given as
$$Q_n=beginbmatrixQ_n-1 & I \ I & Q_n-1 endbmatrix$$
where $Q_1$ is the adjacency matrix of $K_2$. Since the $1$-dimensional hypercube is $K_2$ and the $2$-dimensional hypercube is $C_4$ which are also circulant graphs I was wondering if all $n$-dimensional hypercubes are circulant graphs and if so what is the circulant matrix representation of their adjacency matrix.
graph-theory adjacency-matrix
asked Jul 21 at 3:07
amitsett
256
Usually the adjacency matrix representation of the n-dimensional hypercube, $Q_n$, is given as
$$Q_n=beginbmatrixQ_n-1 & I \ I & Q_n-1 endbmatrix$$
where $Q_1$ is the adjacency matrix of $K_2$. Since the $1$-dimensional hypercube is $K_2$ and the $2$-dimensional hypercube is $C_4$ which are also circulant graphs I was wondering if all $n$-dimensional hypercubes are circulant graphs and if so what is the circulant matrix representation of their adjacency matrix.
graph-theory adjacency-matrix
asked Jul 21 at 3:07
amitsett
256
edited Jul 23 at 5:45
asked Jul 21 at 3:07
amitsett
256
asked Jul 21 at 3:07
amitsett
256
asked Jul 21 at 3:07
amitsett
256
256
What about $Q_3$? (the ordinary cube)
– Lord Shark the Unknown
Jul 21 at 3:10
I'm not sure. I thought no initially but according to a paper I was reading it is?
– amitsett
Jul 21 at 3:22
@LordSharktheUnknown $Q_3$ is not circulant. Thanks.
– amitsett
Jul 21 at 5:34
add a comment |Â
What about $Q_3$? (the ordinary cube)
– Lord Shark the Unknown
Jul 21 at 3:10
I'm not sure. I thought no initially but according to a paper I was reading it is?
– amitsett
Jul 21 at 3:22
@LordSharktheUnknown $Q_3$ is not circulant. Thanks.
– amitsett
Jul 21 at 5:34
What about $Q_3$? (the ordinary cube)
– Lord Shark the Unknown
Jul 21 at 3:10
What about $Q_3$? (the ordinary cube)
– Lord Shark the Unknown
Jul 21 at 3:10
I'm not sure. I thought no initially but according to a paper I was reading it is?
– amitsett
Jul 21 at 3:22
I'm not sure. I thought no initially but according to a paper I was reading it is?
– amitsett
Jul 21 at 3:22
@LordSharktheUnknown $Q_3$ is not circulant. Thanks.
– amitsett
Jul 21 at 5:34
@LordSharktheUnknown $Q_3$ is not circulant. Thanks.
– amitsett
Jul 21 at 5:34
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
The $d$-cube is not a circulant if $dge3$. In fact something stronger is true.
Suppose $G$ is an abelian group acting regularly as a group of automorphisms of the $d$-cube $Q_d$. Then $Q_d$is a Cayley graph for $G$, with connection set $C$ (say).
Define two elements $g$ and $h$ of $G$ to be equivalent if they generate the same subgroup of $G$. It is known that if the eigenvalues of a Cayley graph for an abelian group are integers, $C$ must be a union of equivalence classes. (Bridges and Mena "Rational G-matrices with rational eigenvalues", JCT A, 32 (1982), 264-280.)
Assume now that the exponent of $G$ is $2^m$, where $mge3$. Since the $d$-cube is connected, $C$ must be a generating set for $G$ and hence it contains an element of order $2^m$, and hence $C$ contains all $2^m-1$
generators of some subgroup of order $2^m$. It follows that the $d$-cube must have an induced subgraph isomorphic to $K_2^m-1,2^m-1$ and, in particular contains a copy of $K_3,3$.
To complete the argument we show by induction on $d$ that $Q_d$ does not contains an induced subgraph isomorphic to $K_3,3$. The key is that we cannot disconnect $K_3,3$ by deleting the edges of a perfect matching (exercise: note that all perfect matchings are equivalent under the automorhism group). But the $d$-cube consists of two copies of the
$Q_d-1$-cube joined by a perfect matching, and so any copy of $K_3,3$ must lie in one of the copies of $Q_d-1$, which leads to a contradiction.
So the $d$-cube cannot be a Cayley group for an abelian group of exponent
greater than four. Note that if $d=2e$, then it is a Cayley graph for
$mathbbZ_4^e$.
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
The $d$-cube is not a circulant if $dge3$. In fact something stronger is true.
Suppose $G$ is an abelian group acting regularly as a group of automorphisms of the $d$-cube $Q_d$. Then $Q_d$is a Cayley graph for $G$, with connection set $C$ (say).
Define two elements $g$ and $h$ of $G$ to be equivalent if they generate the same subgroup of $G$. It is known that if the eigenvalues of a Cayley graph for an abelian group are integers, $C$ must be a union of equivalence classes. (Bridges and Mena "Rational G-matrices with rational eigenvalues", JCT A, 32 (1982), 264-280.)
Assume now that the exponent of $G$ is $2^m$, where $mge3$. Since the $d$-cube is connected, $C$ must be a generating set for $G$ and hence it contains an element of order $2^m$, and hence $C$ contains all $2^m-1$
generators of some subgroup of order $2^m$. It follows that the $d$-cube must have an induced subgraph isomorphic to $K_2^m-1,2^m-1$ and, in particular contains a copy of $K_3,3$.
To complete the argument we show by induction on $d$ that $Q_d$ does not contains an induced subgraph isomorphic to $K_3,3$. The key is that we cannot disconnect $K_3,3$ by deleting the edges of a perfect matching (exercise: note that all perfect matchings are equivalent under the automorhism group). But the $d$-cube consists of two copies of the
$Q_d-1$-cube joined by a perfect matching, and so any copy of $K_3,3$ must lie in one of the copies of $Q_d-1$, which leads to a contradiction.
So the $d$-cube cannot be a Cayley group for an abelian group of exponent
greater than four. Note that if $d=2e$, then it is a Cayley graph for
$mathbbZ_4^e$.
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
add a comment |Â
up vote
0
down vote
accepted
The $d$-cube is not a circulant if $dge3$. In fact something stronger is true.
Suppose $G$ is an abelian group acting regularly as a group of automorphisms of the $d$-cube $Q_d$. Then $Q_d$is a Cayley graph for $G$, with connection set $C$ (say).
Define two elements $g$ and $h$ of $G$ to be equivalent if they generate the same subgroup of $G$. It is known that if the eigenvalues of a Cayley graph for an abelian group are integers, $C$ must be a union of equivalence classes. (Bridges and Mena "Rational G-matrices with rational eigenvalues", JCT A, 32 (1982), 264-280.)
Assume now that the exponent of $G$ is $2^m$, where $mge3$. Since the $d$-cube is connected, $C$ must be a generating set for $G$ and hence it contains an element of order $2^m$, and hence $C$ contains all $2^m-1$
generators of some subgroup of order $2^m$. It follows that the $d$-cube must have an induced subgraph isomorphic to $K_2^m-1,2^m-1$ and, in particular contains a copy of $K_3,3$.
To complete the argument we show by induction on $d$ that $Q_d$ does not contains an induced subgraph isomorphic to $K_3,3$. The key is that we cannot disconnect $K_3,3$ by deleting the edges of a perfect matching (exercise: note that all perfect matchings are equivalent under the automorhism group). But the $d$-cube consists of two copies of the
$Q_d-1$-cube joined by a perfect matching, and so any copy of $K_3,3$ must lie in one of the copies of $Q_d-1$, which leads to a contradiction.
So the $d$-cube cannot be a Cayley group for an abelian group of exponent
greater than four. Note that if $d=2e$, then it is a Cayley graph for
$mathbbZ_4^e$.
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
The $d$-cube is not a circulant if $dge3$. In fact something stronger is true.
Suppose $G$ is an abelian group acting regularly as a group of automorphisms of the $d$-cube $Q_d$. Then $Q_d$is a Cayley graph for $G$, with connection set $C$ (say).
Define two elements $g$ and $h$ of $G$ to be equivalent if they generate the same subgroup of $G$. It is known that if the eigenvalues of a Cayley graph for an abelian group are integers, $C$ must be a union of equivalence classes. (Bridges and Mena "Rational G-matrices with rational eigenvalues", JCT A, 32 (1982), 264-280.)
Assume now that the exponent of $G$ is $2^m$, where $mge3$. Since the $d$-cube is connected, $C$ must be a generating set for $G$ and hence it contains an element of order $2^m$, and hence $C$ contains all $2^m-1$
generators of some subgroup of order $2^m$. It follows that the $d$-cube must have an induced subgraph isomorphic to $K_2^m-1,2^m-1$ and, in particular contains a copy of $K_3,3$.
To complete the argument we show by induction on $d$ that $Q_d$ does not contains an induced subgraph isomorphic to $K_3,3$. The key is that we cannot disconnect $K_3,3$ by deleting the edges of a perfect matching (exercise: note that all perfect matchings are equivalent under the automorhism group). But the $d$-cube consists of two copies of the
$Q_d-1$-cube joined by a perfect matching, and so any copy of $K_3,3$ must lie in one of the copies of $Q_d-1$, which leads to a contradiction.
So the $d$-cube cannot be a Cayley group for an abelian group of exponent
greater than four. Note that if $d=2e$, then it is a Cayley graph for
$mathbbZ_4^e$.
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
The $d$-cube is not a circulant if $dge3$. In fact something stronger is true.
Suppose $G$ is an abelian group acting regularly as a group of automorphisms of the $d$-cube $Q_d$. Then $Q_d$is a Cayley graph for $G$, with connection set $C$ (say).
Define two elements $g$ and $h$ of $G$ to be equivalent if they generate the same subgroup of $G$. It is known that if the eigenvalues of a Cayley graph for an abelian group are integers, $C$ must be a union of equivalence classes. (Bridges and Mena "Rational G-matrices with rational eigenvalues", JCT A, 32 (1982), 264-280.)
Assume now that the exponent of $G$ is $2^m$, where $mge3$. Since the $d$-cube is connected, $C$ must be a generating set for $G$ and hence it contains an element of order $2^m$, and hence $C$ contains all $2^m-1$
generators of some subgroup of order $2^m$. It follows that the $d$-cube must have an induced subgraph isomorphic to $K_2^m-1,2^m-1$ and, in particular contains a copy of $K_3,3$.
To complete the argument we show by induction on $d$ that $Q_d$ does not contains an induced subgraph isomorphic to $K_3,3$. The key is that we cannot disconnect $K_3,3$ by deleting the edges of a perfect matching (exercise: note that all perfect matchings are equivalent under the automorhism group). But the $d$-cube consists of two copies of the
$Q_d-1$-cube joined by a perfect matching, and so any copy of $K_3,3$ must lie in one of the copies of $Q_d-1$, which leads to a contradiction.
So the $d$-cube cannot be a Cayley group for an abelian group of exponent
greater than four. Note that if $d=2e$, then it is a Cayley graph for
$mathbbZ_4^e$.
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
answered Jul 22 at 18:51
Chris Godsil
11.1k21534
11.1k21534
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858208%2fare-all-n-dimensional-hypercube-graphs-circulant-and-if-so-what-is-their-circula%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
What about $Q_3$? (the ordinary cube)
– Lord Shark the Unknown
Jul 21 at 3:10
I'm not sure. I thought no initially but according to a paper I was reading it is?
– amitsett
Jul 21 at 3:22
@LordSharktheUnknown $Q_3$ is not circulant. Thanks.
– amitsett
Jul 21 at 5:34