{"id":7217,"date":"2013-12-16T11:23:05","date_gmt":"2013-12-16T19:23:05","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=7217"},"modified":"2026-09-30T09:16:02","modified_gmt":"2026-09-30T17:16:02","slug":"examples","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/examples\/","title":{"rendered":"examples (Max Cut, Tur\u00e1n\u2019s theorem)"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<blockquote class=\"quote\"><p><center><em>Examples: 2-approximation for Max Cut; Tur\u00e1n\u2019s theorem<\/em><\/center><\/p><\/blockquote>\n<p><!--more--><\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000002\">Example: Max Cut<\/h1>\n<p> Given a graph <script type=\"math\/tex;\">G=(V,E)<\/script> with <script type=\"math\/tex;\">m<\/script> edges, the Max Cut problem is to color each vertex red or blue so as to maximize the number of edges with differently colored endpoints. (Say such an edge is \u201ccut\u201d.) The problem is NP-hard. <\/p>\n<p>Consider the following random experiment: <em> For each vertex <script type=\"math\/tex;\">v<\/script> independently, color <script type=\"math\/tex;\">v<\/script> red with probability <script type=\"math\/tex;\">1\/2<\/script>; otherwise color <script type=\"math\/tex;\">v<\/script> blue.<\/em> <\/p>\n<p>The probability that any given edge is cut is 1\/2. Thus, by linearity of expectation, in expectation half the edges are cut. Thus, by the existence principle above, <em> there exists a coloring that cuts at least half the edges<\/em>. Since no coloring can cut more than twice this many edges, such a coloring is a 2-approximate solution. <\/p>\n<p>This example apparently appeared first in a 1965 paper of Erd\u0151s\u00a0<span class=\"cite\">[<a href=\"#erdos1965some\">1<\/a>, Lemma 1]<\/span>. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000003\">Example: Tur\u00e1n\u2019s theorem<\/h1>\n<p> Here is a slightly more sophisticated example. An <em> independent set<\/em> in a graph <script type=\"math\/tex;\">G=(V,E)<\/script> is a subset <script type=\"math\/tex;\">S<\/script> of vertices such that no edge has both endpoints in <script type=\"math\/tex;\">S<\/script>. Tur\u00e1n\u2019s theorem is as follows: <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (Turan).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Any graph <script type=\"math\/tex;\">G<\/script> with <script type=\"math\/tex;\">n<\/script> nodes and average degree <script type=\"math\/tex;\">\\bar d<\/script> has an independent set <script type=\"math\/tex;\">S<\/script> of size at least <script type=\"math\/tex;\">n\/(\\bar d+1)<\/script>. <\/p>\n<\/div><\/div>\n<p>This bound is tight: consider the graph formed by the union of <script type=\"math\/tex;\">n\/(\\bar d + 1)<\/script> cliques, each of size <script type=\"math\/tex;\">\\bar d + 1<\/script>. Every vertex has degree <script type=\"math\/tex;\">\\bar d<\/script> and every independent set has size at most <script type=\"math\/tex;\">n\/(\\bar d + 1)<\/script>. <\/p>\n<div id=\"a0000000005\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\">  <b>Proof. <\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>To prove the theorem, consider the following random experiment: <\/p>\n<blockquote class=\"quote\"><p><em> Consider the vertices in random order. When considering a vertex <script type=\"math\/tex;\">v<\/script>, add it to the set <script type=\"math\/tex;\">S<\/script> if none of <script type=\"math\/tex;\">v<\/script>\u2019s neighbors have yet been added. Return <script type=\"math\/tex;\">S<\/script>.<\/em> <\/p><\/blockquote>\n<p>A vertex <script type=\"math\/tex;\">v<\/script> with <script type=\"math\/tex;\">d_v<\/script> neighbors has a <script type=\"math\/tex;\">1\/(d_v+1)<\/script> chance of being considered first among its neighbors, in which case <script type=\"math\/tex;\">v<\/script> will definitely be added. Hence, by linearity of expectation, the expected size of <script type=\"math\/tex;\">S<\/script> is therefore at least <script type=\"math\/tex;\">\\sum _{v\\in V} {1}\/{(d_v+1)}.<\/script> As a function of the <script type=\"math\/tex;\">d_v<\/script>\u2019s, this quantity is minimized for fixed <script type=\"math\/tex;\">\\sum _v d_v<\/script> when each <script type=\"math\/tex;\">d_v = \\bar d<\/script>. Thus, there exists an independent set <script type=\"math\/tex;\">S<\/script> of size at least <script type=\"math\/tex;\">n\/(\\bar d+1)<\/script>. <\/p>\n<\/div>\n<div style=\"float:right;border:1px solid #444;width:0.45em;height:0.45em\">\u00a0<\/div>\n<div style=\"clear:both\">\u00a0<\/div>\n<\/p><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000006\">On Wikipedia<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Max_cut\">Max Cut<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Tur\u00e1n%27s_theorem\">Tur\u00e1n\u2019s theorem<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"erdos1965some\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Erdos&quot;+intitle:&quot;+On+some+extremal+problems+in+graph+theory&quot;\">P.\u00a0Erd\u00f6s. On some extremal problems in graph theory. <em>Israel Journal of Mathematics<\/em>, 3(2):113\u2013116, 1965. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Examples: 2-approximation for Max Cut; Tur\u00e1n\u2019s theorem<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":901,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-7217","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/7217","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=7217"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/7217\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/901"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=7217"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}