2
$\begingroup$

Let $G_n$ denotes all graphs with $n$ nodes. For any graph $G$ in $G_n$, the adjacency matrix $A(G)$ can be viewed as a codeword of length $n^2$. Also, the codes arises from $G_n$ is a linear binary code.

Now, I want to see the RC conjecture as a coding problem. The Reconstruction conjecture (RC): we can reconstruct any $n$-vertex graph $G$ from the collection of all $(n−1)$-vertex graphs obtained by deleting one vertex of $G$ (together with all edges involving that vertex)

Let we have a code word (corresponding to the graph $G$ with $n$ vertices) and we send it in the channel. The channel is so wild and deletes and permutes some bits such that we receive a word of length $(n-1)^2$ (corresponding to the induced vertex deleted subgraph of the graph $G$) in the receiver. In our channel, we can request $n$-times for sending the original codeword, and all time we receive a word corresponding to the vertex deleted induced subgraph of the graph $G$ (all deck).

By this terminology, we have a decoding problem for Burst error channel with allowed request repetition.

My question is: Does it show that the RC problem is as hard as decoding problem?

One interesting advantage for this correspondence is in coding theory. By Alon's theorem, this type of coding has easy decoding with at most three time request.

$\endgroup$
3
  • $\begingroup$ you might as well tell us what the RC conjecture is. $\endgroup$
    – kodlu
    Feb 19, 2022 at 22:26
  • 3
    $\begingroup$ @kodlu, I believe it's the conjecture that you can reconstruct any $n$-vertex graph $G$ from the collection of all $n-1$-vertex graphs obtained by deleting one vertex of $G$ (together with all edges involving that vertex); I agree that OP should include this in the body of the question. $\endgroup$ Feb 19, 2022 at 23:56
  • $\begingroup$ @GerryMyerson Thanks for your comment. I will add your comment in the body of the question. $\endgroup$
    – Shahrooz
    Feb 20, 2022 at 22:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.