Existence and construction of asymmetric codes

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?

-

1 Answer

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.

-
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 arxiv.org/pdf/math/0609219.pdf –  Chris Godsil May 20 '14 at 2:23