Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

By a $[n,k]_2$-code I mean a $k$-dimensional $\mathbb{F}_2$-subspace of $\mathbb{F}_2^n$. Such a code $C$ admits a symmetry $\sigma \in S_n$ if for any word $w \in C$ we also have $w^\sigma \in C$, where $(w_1, \dots, w_n)^\sigma$ is defined as $(w_{\sigma(1)}, \dots, w_{\sigma(n)})$. A code $C$ is said to be asymmetric if it admits only one symmetry (i.e. the identity).

It seems to be well known that for all sufficiently large $n$ and $k$ there always exist asymmetric $[n,k]_2$-codes, but I cannot find any reference. Does somebody know where this is proven?

I am particularly interested in a constructive proof. To be specific, I need for any sufficiently large integer $n$ (say $n \geq 13$) an asymmetric $[n,k]_2$-code, where $k$ may be arbitrary. Is there any construction known which yields asymmetric codes?

share|cite|improve this question
up vote 3 down vote accepted

In general if $X$ is a 3-connected graph and $B$ is its vertex-edge incidence matrix, then the automorphism group of the code formed by the row space of $B$ is the automorphism group of the graph. This makes it easy to construct asymmetric codes of length equal to $|E(X)|$.

There is also work on self-dual codes: MR1168157 (93b:94022) Oral, Haluk ; Phelps, Kevin T. Almost all self-dual codes are rigid. J. Combin. Theory Ser. A 60 (1992), no. 2, 264--276. Oral's thesis (google Haluk Oral SFU thesis) has more on self-dual codes.

share|cite|improve this answer
Thank you very much! Do you also have a reference for the first statement? – Dune May 19 '14 at 13:46
It follows from Whitney's theorem that a 3-connected graph is determined by its cycle space. – Chris Godsil May 19 '14 at 17:46
Unfortunately, I also cannot find any reference for this result of Whitney, but I am really interested in it. Do you know where this is proved? – Dune May 19 '14 at 20:02
The first thing I can find on line is – Chris Godsil May 20 '14 at 2:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.