CSE 525: Randomized Algorithms and Probability Spring 2026 HW2 Submit to gradescope

Instructions

• You should think about each problem by yourself for at least an hour before choosing to collaborate with others.

• You are allowed to collaborate with fellow students taking the class in solving the problems. But you must write your solution on your own.

• You are not allowed to search for answers or hints on the web. You are encouraged to contact the instructor or the TAs for a possible hint.

• You cannot collaborate on Extra credit problems

• Solutions typeset in LATEX are preferred.

• Feel free to use the Discussion Board or email the instructor or the TAs if you have any questions or would like any clarifications about the problems.

• Please upload your solutions to Gradescope.

 

In solving these assignments, feel free to use these approximations:

$$1-x\approx e^{-x},\sqrt{1-x}\approx 1-x/2,n!\approx {(n/e)}^n,{\left(\frac{n}{k}\right)}^k\le \left(\genfrac{}{}{0pt}{}{n}{k}\right)\le {\left(\frac{en}{k}\right)}^k$$

1. Let $G$ be a 3-uniform hypergraph with n vertices and $m\ge n$ edges, i.e., every edge has exactly three vertices. Design a randomize that finds an independent set $I$ in $G$ of expected size at least $\mathrm{\Omega }(n^{3/2}/\sqrt{m})$-vertices. Note that $I\subseteq V$ is an independent set if it doesn’t contain all 3 vertices of any edge of $G$.

2. Show that there is a phase transition for connectivity in a $G(n,p)$ graph. Let $ℰ$ be the event that $G(n,p)$ is connected. Namely prove the following two facts:

   1. If $p\ll \frac{\log n}{n}$, then $\mathbb{P}\left[ℰ\right]\to 0$ as $n\to \mathrm{\infty }$.

      Hint: Let ${ℰ}^{\prime }$ be the event that $G(n,p)$ has an isolated vertex. Prove that $\mathbb{P}\left[{ℰ}^{\prime }\right]\to 1$ as $n\to \mathrm{\infty }$.

   2. If $p\gg \frac{\log n}{n}$, then $\mathbb{P}\left[ℰ\right]\to 1$ as $n\to \mathrm{\infty }$.