随机算法 (Fall 2011)/Graph Coloring and W.D. Hamilton: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
m (Protected "随机算法 (Fall 2011)/Graph Coloring" ([edit=sysop] (indefinite) [move=sysop] (indefinite)))
 
imported>Macdonald-ross
(prose...)
 
Line 1: Line 1:
=Graph Colorings=
'''William Donald Hamilton''' [[Royal Society|FRS]] (1 August 1936 – 7 March 2000) was an [[English people|English]] [[evolutionary biology|evolutionary biologist]] whom [[Richard Dawkins]] praised as one of the greatest [[evolution]]ary theorists of the 20th century.<ref>[http://www.edge.org/3rd_culture/hamilton/hamilton_index.html Obituary by Richard Dawkins – ''The Independent'' – 10 March 2000]</ref>
A '''proper coloring''' of a graph <math>G(V,E)</math> is a mapping <math>f:V\rightarrow[q]</math> for some integer <math>q</math>, satisfying that <math>f(u)\neq f(v)</math> for all <math>uv\in E</math>.


We consider the problem of sampling a uniformly random proper coloring of a given graph. We will later see that this is useful for counting the number of proper colorings of a given graph, which is a fundamental combinatorial problem, having important applications in statistic physics.
Hamilton became famous through his [[Theory|theoretical]] work on [[kin selection]] and [[altruism]]. He explained its [[Genetics|genetic]] basis, and this was a key part of the gene-centered view of [[evolution]]. In doing this, he became one of the forerunners of [[sociobiology]], as popularized by [[E.O. Wilson]]. Hamilton was certainly a big influence on Dawkins. He also published important work on [[sex ratio]]s and the [[evolution of sex]]. From 1984 to his death in 2000, he was the [[Royal Society]] Research Professor at [[Oxford University]]. He died of [[malaria]] contracted in the [[Democratic Republic of the Congo]].


Let's first consider the decision version of the problem. That is, given as input a graph <math>G(V,E)</math>, decide whether there exists a proper <math>q</math>-coloring of <math>G</math>. Denote by <math>\Delta</math> the maximum degree of <math>G</math>.
== Hamilton's equation ==
* If <math>q\ge \Delta+1</math>, there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.<ref>Hamilton W.D. 1996. ''Narrow roads of geneland: the collected papers of W.D. Hamilton'', vol 1. Freeman, Oxford.</ref> The gene will spread if '''r'''x'''b''' is greater than '''c''':
* If <math>q=\Delta</math>, <math>G</math> has a proper coloring unless it contains a <math>(\Delta+1)</math>-clique or it is an odd cycle. ([http://en.wikipedia.org/wiki/Brooks'_theorem Brooks Theorem])
:<math>rb > c \ </math>    
* If <math>q<\Delta</math>, the problem is NP-hard.
where:
* <math>c \ </math> is the reproductive cost to the altruist,
* <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and
* <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".


Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when <math>q<\Delta</math>. The decision problem for the case <math>q=\Delta</math> is also nontrivial. Thus people are interested only in the case when <math>q\ge \Delta+1</math>.
== Collected papers ==
Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.


The following is a natural Markov chain for sampling proper colorings.
* Hamilton W.D. 1996. ''Narrow roads of gene land vol. 1: Evolution of social behaviour''. Freeman, Oxford. ISBN 0-7167-4530-5
* Hamilton W.D. 2002. ''Narrow roads of gene land vol. 2: Evolution of sex''. Oxford University Press, Oxford. ISBN 0-19-850336-9
* Hamilton W.D. 2005. ''Narrow roads of gene land, vol. 3: Last words'' (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5


{{Theorem|Markov Chain for Graph Coloring|
== References ==
:Start with a proper coloring of <math>G(V,E)</math>. At each step:
{{Reflist}}
# Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly at random.
# Change the color of <math>v</math> to <math>c</math> if the resulting coloring is proper; do nothing if otherwise.
}}


For a fixed graph <math>G(V,E)</math>, the state space of the above Markov chain is the set of all proper colorings of <math>G</math> with <math>q</math> colors.
{{DEFAULTSORT:Hamilton, William Donald}}
 
[[Category:1936 births]]
{{Theorem|Lemma|
[[Category:2000 deaths]]
The followings hold for the above Markov chain.
[[Category:English mathematicians]]
# Aperiodic.
[[Category:Geneticists]]
# The transition matrix is symmetric.
[[Category:English evolutionary biologists]]
# Irreducible if <math>q\ge \Delta+2</math>.
[[Category:Fellows of the Royal Society]]
}}
 
The followings are the two most important conjectures regarding the problem.
{{Theorem|Conjecture|
#The simple Markov chain defined above has mixing time <math>O(n\ln n)</math> whenever <math>q\ge\Delta+2</math>.
# Random sampling of proper graph colorings can be done in polynomial time whenever <math>q\ge\Delta+1</math>.
}}
 
These two conjectures are still open. People approach them by relax the requirement for the number of colors <math>q</math>. Intuitively, the larger the <math>q</math> is, the more freedom we have, the less dependency are there between non-adjacent vertices.
 
=Coupling: <math>q\ge 4\Delta+1</math>=
 
=Path Coupling: <math>q\ge 2\Delta+1</math> =

Latest revision as of 09:43, 22 December 2013

William Donald Hamilton FRS (1 August 1936 – 7 March 2000) was an English evolutionary biologist whom Richard Dawkins praised as one of the greatest evolutionary theorists of the 20th century.[1]

Hamilton became famous through his theoretical work on kin selection and altruism. He explained its genetic basis, and this was a key part of the gene-centered view of evolution. In doing this, he became one of the forerunners of sociobiology, as popularized by E.O. Wilson. Hamilton was certainly a big influence on Dawkins. He also published important work on sex ratios and the evolution of sex. From 1984 to his death in 2000, he was the Royal Society Research Professor at Oxford University. He died of malaria contracted in the Democratic Republic of the Congo.

Hamilton's equation

Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.[2] The gene will spread if rxb is greater than c:

[math]\displaystyle{ rb \gt c \ }[/math]

where:

  • [math]\displaystyle{ c \ }[/math] is the reproductive cost to the altruist,
  • [math]\displaystyle{ b \ }[/math] is the reproductive benefit to the recipient of the altruistic behavior, and
  • [math]\displaystyle{ r \ }[/math] is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".

Collected papers

Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.

  • Hamilton W.D. 1996. Narrow roads of gene land vol. 1: Evolution of social behaviour. Freeman, Oxford. ISBN 0-7167-4530-5
  • Hamilton W.D. 2002. Narrow roads of gene land vol. 2: Evolution of sex. Oxford University Press, Oxford. ISBN 0-19-850336-9
  • Hamilton W.D. 2005. Narrow roads of gene land, vol. 3: Last words (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5

References

Template:Reflist

  1. ↑ Obituary by Richard Dawkins – The Independent – 10 March 2000
  2. ↑ Hamilton W.D. 1996. Narrow roads of geneland: the collected papers of W.D. Hamilton, vol 1. Freeman, Oxford.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)/Graph_Coloring&oldid=7721"