Gordian Knot

[Jonathan Post]

I was working on Harary's Graph Reconstruction Hypothesis while and
undergraduate at caltech, and wrote an internal grant proposal.  It has been
solved for bigger and bigger subsets of graphs, but is still unsolved in
general.  What seemed bizarre to me was the identical problem expressed in
terms of the adjacency matrices.  Given an nxn binary (0-1) matrix, one is
given the set of all (n-1)x(n-1) submatrices. Can one reconstruct the
original matrix?  If so, then (loosely speaking) all information in the
matrix is local.  If not, then in some weird holographic way, there is some
information in some matrices which is entirely global.

-- Jonathan Vos Post

On 12/7/06, Jon Awbrey <jawbrey at att.net> wrote:
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> speaking of hard problems to while away the idle hours ...
> there was an emumerative way of approaching the graph
> reconstruction conjecture -- has that been solved?
> i had to swear off it some years ago, doctor's orders --
> it had to do with showing two sequences identical or not,
> the enumerator of graphs and the enumerator of another
> defined family of structures that are derived from graphs.
>
> ja
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> inquiry e-lab: http://stderr.org/pipermail/inquiry/
> zhongwen wp: http://zh.wikipedia.org/wiki/User:Jon_Awbrey
> wikinfo: http://wikinfo.org/wiki.php?title=User:Jon_Awbrey
> meta: http://www.getwiki.net/wiki.php?title=User:Jon_Awbrey
> wp review: http://wikipediareview.com/index.php?showuser=398
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061207/8272434a/attachment-0002.htm>