Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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|improve this answer
    
Thank you very much! Do you also have a reference for the first statement? –  Dune May 19 at 13:46
    
It follows from Whitney's theorem that a 3-connected graph is determined by its cycle space. –  Chris Godsil May 19 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 at 20:02
    
The first thing I can find on line is arxiv.org/pdf/math/0609219.pdf –  Chris Godsil May 20 at 2:23

Your Answer

 
discard

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.