[MUSIC] Hello, everyone. In the last lecture, Claire introduced a linear programming relaxation for the Maxcut program. In this lecture, we are going to see how far we can go using this LP. Remember, the linear programming introduced for Max-Cut has a set of constraints depending on triplets. The first one corresponds to triangular inequalities. Remember that the variables are one, if, the two vertices are in different sides of the cut. And the second set of constraints corresponds to cycle constraints, but a particular class of cycles, ear triangles, cycles of length three. So the linear program with these two sets of constraints. We know that we can construct, at least, an approximation algorithm satisfying that the optimal value and the value of the linear programming are not a way of a factor of two. But the question is, can we prove using this same linear program? In other words, can we construct an approximation algorithm having a factor less than two? Well unfortunately, the answer is no. We cannot construct such approximation algorithm because for each small value, let's say 0.0001, we can find the graph G such that the ratio between the linear program and the mascot in this graph is at least 2 minus this little bit. And then we cannot improve using this LP. But we do we prove a result like this? We need to find such a graph. In principle, might not be easy. Well, in order to prove this, we are going to introduce an extremely useful class of graphs. But first, let's see how could be the scheme in order to prove such a result. The graph we need to find will satisfy two properties. Property 1, the LP has at least 0.9999 edges. In other words, will be very close to the number of edges which is always an upper bound on the LP. On the second property, the Max-Cut has at most 0.51, the number of edges. In other words, it's very close to half the number of edges, which is always a lower bound on the Max-Cut of a graph. Therefore, we want to find the graph matching almost the upper bound for the LP, almost the lower bound for the Max-Cut. And that will give us a value, which is almost 2. So if we consider Property 1 with 0.99 and Property 2 with 0.51, we are going to obtain that graph for which the ratio between the LP and the Max-Cut is at least 1.94 and so on, which is very close to 2. So that's the scheme, that's the proof scheme. But we need to find this graph. So we need to answer that question before doing this. Well, as I said you before, we're going to use a very useful class of graphs. These will be the random graphs. What is a random graph? We will have two parameters, n and p. n is the number of nodes, p will be the probability that flipping a coin will give us a head, and 1-p is the probability that this coin will give us a tail. So, for each pair of vertices, we are going to repeat the following experiment. We flip this coin. If it is head, then we have a link between these two vertices. If this is a tail, then we don't have a link. For example, here we have four nodes. Then, six possible pairs. For each pair, we're going to flip a third coin, one-half head, one-half tail. And we can see for the pairs, (1,4), (4,2), (1,3) and for 3, we obtain a half and then we have a link. But for pairs (1,2) and (2,3), we obtained a tail so we don't have a link. In this experiment, we obtained a graph and four vertices and having four edges. So we are going to obtain graphs from this family. And we will see how to prove that there exists a graph satisfying property 1 and property 2. But before going to that, we are going to state a useful lemma. If we have a graph, not necessarily random graph, could be any graph. If we have a graph having large enough cycles, let's say of length at least this G. Then the value of the linear program for this graph would be at least 0.99 the number of edges. In other words, if we can find a graph satisfying this property of having large cycles, then we are sure that we are satisfying Property 1. Then what we are going to do is we are going to pick a graph from this random graph family. Then we are going to obtain a bound on how likely is to obtain a graph having many short cycles. We can prove that in fact with probability less than 0.5, if we draw a graph from this family, it will have more than a square root of then short cycles of length at most g-1 with probability less than one-half. And therefore, more than half of the graphs in this family will have large cycles, many large cycles. Then we obtained a graph here and with high probability, we can remove all these short cycles by removing at most the square root of n edges. And then the graph will obtain G' will satisfy the state of the previous lemma, which is to have only large cycles. So this graph G' will satisfy Property 1. So then half of the task is done. Now we have to ensure that there are graphs from this family that are also satisfied Property 2. Well, we can prove that if you draw a graph from this family, the Max-Cut of the graph G' we construct before by removing edges in case we have to will have a Max-Cut not greater than 0.51 the number of edges with probability at least 0.8. In other words, 80% of the graphs in this family will have a Max-Cut which is very close to half of the edges, which is what we want. So now we have graphs satisfying Property 1. We have graphs satisfying Property 2 in this family. But we need a graph satisfying both properties. Then we need to obtain a lower bound on the probability that a graph drawn from these random graph family will satisfy both properties. The probability that a graph in this family satisfies Property 1 and Property 2 is at least 1 minus the probability that G does not satisfy Property 1, which is 0.5. And minus the probability that G does not satisfy Property 2, which is at most 0.2. And then, the probability that G satisfies Property 1 and Property 2 is at least 0.3. Which is enough because then we know that at least 30% of the graphs in this family would satisfy both properties. Therefore, there exists a graph satisfying what we want which is a ratio very close to 2 between the value of the LP and the Max-Cut. In the next lecture, we're going to see how we can prove Property 1 by using a very useful inequality called the Markov's Inequality.