2
$\begingroup$

Consider bipartite graph. Consider its adjacency matrix. It will have a form

0 A^t

A 0

Take matrix $A$. Consider the null-space $L$ of $A$ over $F_2^N$.

Question Can we say something about the $L$ from graph theoretic perspective ? For example to determine what is minimum Hamming weight for vectors in $L$ ?

In error correction codes community the following words are used: Original graph is called Tanner graph for $A$. Matrix $A$ is called parity-check matrix. Let dim(L)=k, any linear map $F_2^k \to L\subset F_2^N$ is called "encoder".

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What you have called the incidence matrix is actually the adjacency matrix (as will be clear if you read the article you've linked to). Your approach translates all coding theory questions into graph theory questions. It seems unlikely that much will be gained by the translation. Of course there are many papers studying the case when $A$ is sparse (LDPC codes). $\endgroup$
    – Chris Godsil
    Commented Feb 27, 2012 at 13:35
  • $\begingroup$ @Chris Thank You, I corrected ! Shame on me I am always mixing these matrices. Fields medalist G. Margulis constructed some "good" LDPC codes by Cayley graphs (???) of some groups GL(F,p) - as I heard but not really understand. There are lots of papers about "expanders" graphs which is probably related to this question... I just start learning these things so, may be question is not really good... $\endgroup$
    – Alexander Chervov
    Commented Feb 27, 2012 at 13:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .