Gordian Knot

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

yes, (though i think it's usually attributed to ulam), that
was part of the attraction, since pt-deleted subgraphs are
like taking derivatives, reconstruction is analogous to the
integration problem, and the holographic metaphor was there,
too, or radon-nikodym, and catscans, etc.  but it has to be
group orbits of matrices, so as not to be labeled graphs.

i will look up some old notes and try to
remember how the enumerative angle went.

ja

> 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

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