Talk:Reconstruction conjecture
Latest comment: 5 years ago by Joel B. Lewis in topic two problems
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Isomorphism classes of graphs
editPlease, think there also about isomorphism classes of graphs. Канеюку (talk) 16:21, 11 November 2011 (UTC)
Definition of reconstructible
editThe article is a bit vague about what it means for a graph family to be reconstructible. In particular, it should distinguish between weakly reconstructible families (if you know a graph is in the family, you can reconstruct it from its deck), and families which are also recognizable (you can tell from the deck if a graph belongs to the family). A reconstructible family can then be defined as both recognizable and weakly reconstructible. 129.199.99.140 (talk) 10:03, 31 May 2013 (UTC)
two problems
edit- Every graph G is "reconstructible from its subgraphs" since G itself is the unique subgraph with the most vertices. So the informal conjecture is trivially true. If we avoid that by using "proper subgraphs" then the conjecture is trivially false due to K2 and its complement. Neither Kelly nor Ulam made these elementary errors, but we cite them as if they did.
- The formal definition does not properly explain the essential role of isomorphism in the conjecture. We write of hypomorphic graphs being isomorphic, but say only that a card is a subgraph. Actually, for the conjecture to make sense a card is not a subgraph but the isomorphism type of a subgraph. Alternatively, one can define "hypomorphic" to mean that the cards of the two decks are isomorphic in pairs. In either case the same type of equivalence relation is required between the cards as is used between the original graphs.
McKay (talk) 03:33, 18 January 2019 (UTC)
- In my opinion the first problem is not a problem, as the word "informally" announces that what follows is not to be treated as the exact formal statement of the conjecture. I think it is helpful to not overburden the very first sentences with technical details that obscure, rather than illuminate, the point.
- I believe that I have just resolved the second problem by the addition of the phrase "isomorphism classes of" in two places, but I would welcome double-checking. There is still no explanation of the significance of this extra phrase. --JBL (talk) 01:59, 21 January 2019 (UTC)