Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

migrated from stackoverflow.com Nov 15 '11 at 13:33

This question came from our site for professional and enthusiast programmers.

    
Are you given the size of the first sets? –  JohnPS Nov 15 '11 at 5:45
    
@JohnPS: Yes, size of the sets to reconstruct is known –  threenplusone Nov 15 '11 at 5:51

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
+1: Just checked, and it works out. –  bdares Nov 15 '11 at 6:12
    
Perfect, thank you. –  threenplusone Nov 15 '11 at 6:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.