# 191014K02 | Day 1 Lecture 1

## 191014K02: Day 1 Tutorial

## Definitions

## Problems

Generalize the mincut argument to c-approximate mincuts.

Generalize the mincut argument to min k-way cut.

Prove #min k-cuts is at most n^{O(k)}.

Show that G(n, 1/2) graphs have:

- many cliques of size 2 \log n-o(\log n) in expectation, and
- no cliques of size 2 \log n+o(\log n) in expectation (and with high probability).

Consider the following algorithm for finding a minimum cut. Assign a random score to each edge, and compute a minimum spanning tree. Removing the heaviest edge in the tree breaks it into two pieces. Argue that with probability \omega(1/n^2), those pieces will be the two sides of a minimum cut. Hint: relate this algorithm to the contraction algorithm we did in the class. Also think about Kruskal’s algorithm.

Show that for every n \geq 4, there is a simple graph G_n on n vertices that has at least {n \choose 2} distinct

*minimum*cuts.Show that for every n \geq 3, there is a simple graph G_n on n vertices such that the value of ILPOPT of the vertex cover ILP associated with G_n is at

*least*one less than twice the value of LPOPT of the vertex cover LP associated with G_n, i.e:

\text{ILPOPT}(G_n) \geq 2\cdot \text{LPOPT}(G_n) - 1.

Consider the Set Cover instance shown in the figure below.

- Show that all-half is the unique LPOPT for this instance.
- Show that if you include every set in \mathcal{F}^\prime with probability x_s, then the probability that \mathcal{F}^\prime covers U is at most 2^{-\Omega(n)}.