Results 1 to 6 of 6

Math Help - Binary relation

  1. #1
    Newbie
    Joined
    Aug 2013
    From
    israel
    Posts
    3

    Binary relation

    Hi

    A is a set of 512 binary numbers of 9 bits each.
    We say that two elements in A are related if they differ from each other by no more then 2 bits.
    We should find a minimal subset of A that cover all A by this relation

    Please excuse my bad English
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,180
    Thanks
    767

    Re: Binary relation

    Hey shlosmem1.

    Your relation in this case is (Ai XOR Bi) = 1 for some bit position i for less than 2. Basically this is a combinatoric argument where you can have:

    0 difference (same numbers)
    1 difference (8 possible differences)
    2 difference (8C2 possible differences or 28 differences).

    This means that for every number you have 1 + 8 + 28 or 37 possible numbers for each input that are "similar".

    Can you take it from there?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2013
    From
    israel
    Posts
    3

    Re: Binary relation

    (9 bits not 8).

    This is embarrassing,
    Apparently I was breaking my head on an NPC problem.
    Vertex cover - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,180
    Thanks
    767

    Re: Binary relation

    Sorry: Change 8Cx with 9Cx and re-do the calculations.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Binary relation

    I am not a specialist in coding theory, but from my web search, this may indeed be a difficult problem. Wikipedia says: "The determination of the minimal size K_q(n,R) of a q-ary R-covering code of length n is a very hard problem. In many cases, only lower and upper bounds are known with a large gap between them." Tables here and here give 16 as the size of the smallest covering code for A, and they refer to research papers.

    Quote Originally Posted by shlosmem1
    We should find a minimal subset of A that cover all A by this relation
    By a "minimal subset", do you mean a subset from which no element can be removed, or a subset with the smallest possible number of elements? (Finding the first may be easier.)

    Quote Originally Posted by shlosmem1
    Apparently I was breaking my head on an NPC problem.
    Vertex cover - Wikipedia, the free encyclopedia
    Does not vertex cover correspond to the Hamming distance of 1 instead of 2? And even if it is an NPC problem, there may be an easy solution for this particlar graph.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Aug 2013
    From
    israel
    Posts
    3

    Re: Binary relation

    1. I meant a subset with the smallest possible number of elements. (According to my calculation the lowest bound is 12 also 16 will do it for my practical needs)
    2. You can convert the graph form distance of 2 to distance of 1. (when each vertex has 45 edges ).
    Last edited by shlosmem1; August 24th 2013 at 07:43 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. show a binary relation is well-defined
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 23rd 2010, 03:08 PM
  2. Recurrence Relation for a binary string
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 25th 2010, 03:55 PM
  3. Very simple Binary Relation definition needed
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 29th 2009, 04:18 AM
  4. Binary relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 3rd 2008, 12:58 PM
  5. binary relation
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 24th 2008, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum