Affordable Access

Publisher Website

The double reconstruction conjecture about finite colored hypergraphs

Journal of Combinatorial Theory Series B
Publication Date
DOI: 10.1016/0095-8956(92)90066-7


Abstract A colored ((0, k)-) hypergraph is a triple, 〈 Σ, V, f〉, where Σ is a set of symbols called colors, V is a finite set of vertices, and f: P( V, 0, k) → Σ is a color function. Here P( V, 0, k) = { A ⊂ V | 0 ≤ # A ≤ k}. For any two colored hypergraphs G and G′ of order n and any 0 ≤ m ≤ n, this paper introduces the notion of a double m-hypomorphism from G onto G′, and poses a reconstruction conjecture which asserts that any two colored hypergraphs of order n are isomorphic iff they are doubly m-hypomorphic for some 0 ≤ m ≤ n. Several properties of this conjecture are presented among which are (1) the restricted version of this conjecture to simple graphs is equivalent to the Ulam's Reconstruction Conjecture, (2) any hypomorphic pair ( X n , Y n ), n = 2, 3, …, of 3-hypergraphs of W. L. Kocay ( J. Combin. Theory Ser. B 42, 1987, 46–63) does not satisfy the conditions in this conjecture, and (3) any two (0, k)-hypergraphs G = 〈 Σ, V, f〉 and G′ = 〈 Σ, V′, f′〉 are isomorphic if there exist a bijection α: V → V′ and an integer m, k ≤ m ≤ # V − k, such that for any k-subset W of V, G − W is isomorphic to G′ − α( W).

There are no comments yet on this publication. Be the first to share your thoughts.