Gordian Knot

[Jonathan Post]

Wonderful!

On 12/8/06, Martin Fuller <martin_n_fuller at btinternet.com> wrote:
>
> Here are a couple of proposed sequences related to the
> reconstruction conjecture and taken from the web. I'd
> welcome some more references and comments, and a
> cross-check! Also can anyone explain A006652-A006655
> or give a link to the paper?
>
> %I A000001
> %S A000001 4, 8, 3, 34, 0, 0, 150, 4, 2, 0, 1044, 0,
> 0, 0, 0, 12334, 8, 2, 2, 0, 0, 274666, 0, 2, 0, 0, 0,
> 0, 12005156, 6, 4, 0, 2, 0, 0, 0
> %N A000001 Triangle T(n,k) of the number of unlabeled
> graphs on n nodes with existential reconstruction
> number k, 3<=k<=n. ERN(G) is the minimum number of
> vertex-deleted subgraphs of G required to uniquely
> reconstruct G up to isomorphism.
> %C A000001 The (vertex) Reconstruction Conjecture, due
> to Kelly and Ulam, states that every graph with three
> or more vertices is reconstructible up to isomorphism
> given the multiset of vertex deleted subgraphs.
> Equivalently, every graph has an ERN and so
> sum(k=3,n,T(n,k))==A000088(n) for all n>=3.
> %H A000001 B. McMullen, <a
> href="http://hdl.handle.net/1850/2773">Graph
> reconstruction numbers</a>.
> %H A000001 P. J. Kelly, <a
> href="http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674">A
> congruence theorem for trees</a>, Pacific J. Math., 7
> (1957), 961–968.
> %H A000001 Wikipedia, <a
> href="http://en.wikipedia.org/wiki/Reconstruction_conjecture
> ">Reconstruction
> conjecture</a>.
> %e A000001 Triangle begins
> 4
> 8, 3
> 34, 0, 0
> 150, 4, 2, 0
> 1044, 0, 0, 0, 0
> 12334, 8, 2, 2, 0, 0
> 274666, 0, 2, 0, 0, 0, 0
> 12005156, 6, 4, 0, 2, 0, 0, 0
> %Y A000001 A000002, A000088, A006652-A006655
> %O A000001 3
> %K A000001 ,hard,more,nice,nonn,tabl,
> %A A000001 Martin Fuller
> (martin_n_fuller at btinternet.com), Dec 08 2006
>
> %I A000002
> %S A000002 3, 2, 9, 7, 19, 8, 8, 56, 90, 2, 16, 496,
> 520, 12, 0, 266, 8308, 3584, 284, 4, 0, 45186, 199247,
> 28781, 1434, 20, 0, 0, 6054148, 5637886, 301530,
> 10686, 914, 4, 0, 0
> %N A000002 Triangle T(n,k) of the number of unlabeled
> graphs on n nodes with universal reconstruction number
> k, 3<=k<=n. URN(G) is the minimum size for which all
> multisubsets of vertex-deleted subgraphs of G can
> uniquely reconstruct G up to isomorphism.
> %C A000002 The (vertex) Reconstruction Conjecture, due
> to Kelly and Ulam, states that every graph with three
> or more vertices is reconstructible up to isomorphism
> given the multiset of vertex deleted subgraphs.
> Equivalently, every graph has an URN and so
> sum(k=3,n,T(n,k))==A000088(n) for all n>=3.
> %H A000002 B. McMullen, <a
> href="http://hdl.handle.net/1850/2773">Graph
> reconstruction numbers</a>.
> %H A000002 P. J. Kelly, <a
> href="http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674">A
> congruence theorem for trees</a>, Pacific J. Math., 7
> (1957), 961–968.
> %H A000002 Wikipedia, <a
> href="http://en.wikipedia.org/wiki/Reconstruction_conjecture
> ">Reconstruction
> conjecture</a>.
> %e A000002 Triangle begins
> 3
> 2, 9
> 7, 19, 8
> 8, 56, 90, 2
> 16, 496, 520, 12, 0
> 266, 8308, 3584, 284, 4, 0
> 45186, 199247, 28781, 1434, 20, 0, 0
> 6054148, 5637886, 301530, 10686, 914, 4, 0, 0
> %Y A000002 A000001, A000088, A006652-A006655
> %O A000002 3
> %K A000002 ,hard,more,nice,nonn,tabl,
> %A A000002 Martin Fuller
> (martin_n_fuller at btinternet.com), Dec 08 2006
>
> --- Jon Awbrey <jawbrey at att.net> wrote:
>
> >
> 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
> >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061208/0efc3ebd/attachment-0003.htm>