4
$\begingroup$

I am trying to find a proof or (more likely) counterexample of the following problem:

Given a list of same sized unique sets produce a list of 2-tuple counts contained within.
Using the 2-tuple counts it is possible to reproduce the original sets?


For example...

The following same sized unique sets:

{1, 2, 3, 6}
{1, 2, 4, 5}
{1, 3, 4, 6}
{2, 3, 5, 6}
{2, 4, 5, 6}
{3, 4, 5, 6}

Contains these 2-tuple counts:

(1, 2) = 2 (2 sets contains both 1 & 2)
(1, 3) = 2 (2 sets contains both 1 & 3)
(1, 4) = 2 (etc)
(1, 5) = 1
(1, 6) = 2
(2, 3) = 2
(2, 4) = 2
(2, 5) = 3
(2, 6) = 3
(3, 4) = 2
(3, 5) = 2
(3, 6) = 4
(4, 5) = 3
(4, 6) = 3
(5, 6) = 3

Using these 2-tuple counts, there is only one possible list of sets which could occur (the original list of sets - found by brute force).


I have no idea where to begin with a proof, and am just trying random combinations hoping to find a counterexample.

Any assistance would be greatly appreciated.


EDIT:

As Petar Ivanov has identified, I am only concerned with sets of a known size (the same as the original).

  • 0
    Are you given the size of the first sets?2011-11-15
  • 0
    @JohnPS: Yes, size of the sets to reconstruct is known2011-11-15

1 Answers 1

6

Here is a counter example:

Family of sets 1:

{10, 1, 2}
{10, 3, 4}
{20, 1, 3}
{20, 2, 4}

Family of sets 2:

{10, 1, 3}
{10, 2, 4}
{20, 1, 2}
{20, 3, 4}

This example can easily be extended to arbitrary set sizes. E.g. for 4 just replace 10 with 10, 11 and 20 with 20, 21, etc.