most recent 30 from http://mathoverflow.net 2013-05-23T08:50:59Z http://mathoverflow.net/feeds/question/89658 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89658/adjacency-matrices-of-graphs-as-parity-check-matrices-of-error-correcting-codes Alexander Chervov 2012-02-27T12:37:14Z 2012-02-27T13:45:39Z

<p>Consider <a href="http://en.wikipedia.org/wiki/Bipartite_graph" rel="nofollow">bipartite graph</a>. Consider its <a href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">adjacency matrix</a>. It will have a form </p> <p>0 A^t</p> <p>A 0</p> <p>Take matrix $A$. Consider the null-space $L$ of $A$ over $F_2^N$.</p> <p><strong>Question</strong> Can we say something about the $L$ from graph theoretic perspective ? For example to determine what is minimum <a href="http://en.wikipedia.org/wiki/Hamming_weight" rel="nofollow">Hamming weight</a> for vectors in $L$ ?</p> <p>In error correction codes community the following words are used: Original graph is called <a href="http://en.wikipedia.org/wiki/Tanner_graph" rel="nofollow">Tanner graph</a> for $A$. Matrix $A$ is called <a href="http://en.wikipedia.org/wiki/Parity-check_matrix" rel="nofollow">parity-check matrix</a>. Let dim(L)=k, any linear map $F_2^k \to L\subset F_2^N$ is called "encoder".</p>