Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Stable Set

  1. Apr 12, 2007 #1
    1. The problem statement, all variables and given/known data

    Show using a probabilistic method that a graph with average degree d has a stable set of cardinality at least n/(2d).

    I can't think of a probabilistic method that will do this.
  2. jcsd
  3. Apr 13, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What is a stable set?

    Work out the expected number of stable sets, I suppose - if all stable sets were of size less than n/2d, then that might be a bound on the expectation - show the bound is exceeded.

    But that is just a guess as to the style of how probabilistic graph theory works - I've never answered a question on it and read precisely on paragraph about it once, so don't trust me.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook