Lesson 2

Advanced Problems.

1. (20 points) A uniformly random simple graph on \(n\) labeled vertices is chosen (each of the \(2^{\binom{n}{2}}\) graphs is equally likely). Prove that the probability the graph is disconnected tends to \(0\) as \(n\to\infty\).
   Hint:

   Consider the probability that the vertex set \(V\) can be partitioned into two non-empty disjoint sets \(S\) and \(V \setminus S\) such that there are no edges connecting them.
2. (20 points) Consider a formula \(F\) in \(3\)-CNF over \(n\) variables and \(m\) clauses and assume that each of its clauses has length three (and all three variables in every clause are different). It is not difficult to see that one can satisfy at least a fraction of \(7/8\) of all its clauses. Indeed, a random assignment satisfies every clause with probability \(7/8\), hence the expected number of clauses satisfied by such an assignment is \(7m/8\), thus there exists at least one assignment satisfying that many clauses. But how to construct it deterministically? One could enumerate all assignments, but there are \(2^{n}\) of them. Show that one can construct the required assignment in time polynomial in \(n\).
   Hint:

   Construct the required assignment variable by variable. Let \(\alpha\) be the number of clauses satisfied by a random assignment. Thus, \(\operatorname{E}[\alpha] \ge 7m/8\). Consider the expected value of \(\alpha\) conditioned on the event that the first \(k\) variables were assigned the given values \(a_{1}, \dotsc, a_{k} \in \{0,1\}\). Show that one can compute such expected values quickly (in time polynomial in \(n\)) and select the value for the next variable so that the expected value still has a high value.
3. (20 points) A fair coin is tossed repeatedly. What is the probability that the sequence \(HHT\) appears before the sequence \(HTT\)?
   Hint:

   Consider the state of the game after the first Head has appeared. Analyze what happens if the next toss is a Head versus a Tail.