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
    @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.