\[
\newcommand{\undefined}{}
\newcommand{\hfill}{}
\newcommand{\qedhere}{\square}
\newcommand{\qed}{\square}
\newcommand{\bbA}{\mathbb A}
\newcommand{\bbB}{\mathbb B}
\newcommand{\bbC}{\mathbb C}
\newcommand{\bbD}{\mathbb D}
\newcommand{\bbE}{\mathbb E}
\newcommand{\bbF}{\mathbb F}
\newcommand{\bbG}{\mathbb G}
\newcommand{\bbH}{\mathbb H}
\newcommand{\bbI}{\mathbb I}
\newcommand{\bbJ}{\mathbb J}
\newcommand{\bbK}{\mathbb K}
\newcommand{\bbL}{\mathbb L}
\newcommand{\bbM}{\mathbb M}
\newcommand{\bbN}{\mathbb N}
\newcommand{\bbO}{\mathbb O}
\newcommand{\bbP}{\mathbb P}
\newcommand{\bbQ}{\mathbb Q}
\newcommand{\bbR}{\mathbb R}
\newcommand{\bbS}{\mathbb S}
\newcommand{\bbT}{\mathbb T}
\newcommand{\bbU}{\mathbb U}
\newcommand{\bbV}{\mathbb V}
\newcommand{\bbW}{\mathbb W}
\newcommand{\bbX}{\mathbb X}
\newcommand{\bbY}{\mathbb Y}
\newcommand{\bbZ}{\mathbb Z}
\newcommand{\sA}{\mathscr A}
\newcommand{\sB}{\mathscr B}
\newcommand{\sC}{\mathscr C}
\newcommand{\sD}{\mathscr D}
\newcommand{\sE}{\mathscr E}
\newcommand{\sF}{\mathscr F}
\newcommand{\sG}{\mathscr G}
\newcommand{\sH}{\mathscr H}
\newcommand{\sI}{\mathscr I}
\newcommand{\sJ}{\mathscr J}
\newcommand{\sK}{\mathscr K}
\newcommand{\sL}{\mathscr L}
\newcommand{\sM}{\mathscr M}
\newcommand{\sN}{\mathscr N}
\newcommand{\sO}{\mathscr O}
\newcommand{\sP}{\mathscr P}
\newcommand{\sQ}{\mathscr Q}
\newcommand{\sR}{\mathscr R}
\newcommand{\sS}{\mathscr S}
\newcommand{\sT}{\mathscr T}
\newcommand{\sU}{\mathscr U}
\newcommand{\sV}{\mathscr V}
\newcommand{\sW}{\mathscr W}
\newcommand{\sX}{\mathscr X}
\newcommand{\sY}{\mathscr Y}
\newcommand{\sZ}{\mathscr Z}
\newcommand{\sfA}{\mathsf A}
\newcommand{\sfB}{\mathsf B}
\newcommand{\sfC}{\mathsf C}
\newcommand{\sfD}{\mathsf D}
\newcommand{\sfE}{\mathsf E}
\newcommand{\sfF}{\mathsf F}
\newcommand{\sfG}{\mathsf G}
\newcommand{\sfH}{\mathsf H}
\newcommand{\sfI}{\mathsf I}
\newcommand{\sfJ}{\mathsf J}
\newcommand{\sfK}{\mathsf K}
\newcommand{\sfL}{\mathsf L}
\newcommand{\sfM}{\mathsf M}
\newcommand{\sfN}{\mathsf N}
\newcommand{\sfO}{\mathsf O}
\newcommand{\sfP}{\mathsf P}
\newcommand{\sfQ}{\mathsf Q}
\newcommand{\sfR}{\mathsf R}
\newcommand{\sfS}{\mathsf S}
\newcommand{\sfT}{\mathsf T}
\newcommand{\sfU}{\mathsf U}
\newcommand{\sfV}{\mathsf V}
\newcommand{\sfW}{\mathsf W}
\newcommand{\sfX}{\mathsf X}
\newcommand{\sfY}{\mathsf Y}
\newcommand{\sfZ}{\mathsf Z}
\newcommand{\cA}{\mathcal A}
\newcommand{\cB}{\mathcal B}
\newcommand{\cC}{\mathcal C}
\newcommand{\cD}{\mathcal D}
\newcommand{\cE}{\mathcal E}
\newcommand{\cF}{\mathcal F}
\newcommand{\cG}{\mathcal G}
\newcommand{\cH}{\mathcal H}
\newcommand{\cI}{\mathcal I}
\newcommand{\cJ}{\mathcal J}
\newcommand{\cK}{\mathcal K}
\newcommand{\cL}{\mathcal L}
\newcommand{\cM}{\mathcal M}
\newcommand{\cN}{\mathcal N}
\newcommand{\cO}{\mathcal O}
\newcommand{\cP}{\mathcal P}
\newcommand{\cQ}{\mathcal Q}
\newcommand{\cR}{\mathcal R}
\newcommand{\cS}{\mathcal S}
\newcommand{\cT}{\mathcal T}
\newcommand{\cU}{\mathcal U}
\newcommand{\cV}{\mathcal V}
\newcommand{\cW}{\mathcal W}
\newcommand{\cX}{\mathcal X}
\newcommand{\cY}{\mathcal Y}
\newcommand{\cZ}{\mathcal Z}
\newcommand{\bfA}{\mathbf A}
\newcommand{\bfB}{\mathbf B}
\newcommand{\bfC}{\mathbf C}
\newcommand{\bfD}{\mathbf D}
\newcommand{\bfE}{\mathbf E}
\newcommand{\bfF}{\mathbf F}
\newcommand{\bfG}{\mathbf G}
\newcommand{\bfH}{\mathbf H}
\newcommand{\bfI}{\mathbf I}
\newcommand{\bfJ}{\mathbf J}
\newcommand{\bfK}{\mathbf K}
\newcommand{\bfL}{\mathbf L}
\newcommand{\bfM}{\mathbf M}
\newcommand{\bfN}{\mathbf N}
\newcommand{\bfO}{\mathbf O}
\newcommand{\bfP}{\mathbf P}
\newcommand{\bfQ}{\mathbf Q}
\newcommand{\bfR}{\mathbf R}
\newcommand{\bfS}{\mathbf S}
\newcommand{\bfT}{\mathbf T}
\newcommand{\bfU}{\mathbf U}
\newcommand{\bfV}{\mathbf V}
\newcommand{\bfW}{\mathbf W}
\newcommand{\bfX}{\mathbf X}
\newcommand{\bfY}{\mathbf Y}
\newcommand{\bfZ}{\mathbf Z}
\newcommand{\rmA}{\mathrm A}
\newcommand{\rmB}{\mathrm B}
\newcommand{\rmC}{\mathrm C}
\newcommand{\rmD}{\mathrm D}
\newcommand{\rmE}{\mathrm E}
\newcommand{\rmF}{\mathrm F}
\newcommand{\rmG}{\mathrm G}
\newcommand{\rmH}{\mathrm H}
\newcommand{\rmI}{\mathrm I}
\newcommand{\rmJ}{\mathrm J}
\newcommand{\rmK}{\mathrm K}
\newcommand{\rmL}{\mathrm L}
\newcommand{\rmM}{\mathrm M}
\newcommand{\rmN}{\mathrm N}
\newcommand{\rmO}{\mathrm O}
\newcommand{\rmP}{\mathrm P}
\newcommand{\rmQ}{\mathrm Q}
\newcommand{\rmR}{\mathrm R}
\newcommand{\rmS}{\mathrm S}
\newcommand{\rmT}{\mathrm T}
\newcommand{\rmU}{\mathrm U}
\newcommand{\rmV}{\mathrm V}
\newcommand{\rmW}{\mathrm W}
\newcommand{\rmX}{\mathrm X}
\newcommand{\rmY}{\mathrm Y}
\newcommand{\rmZ}{\mathrm Z}
\newcommand{\paren}[1]{( #1 )}
\newcommand{\Paren}[1]{\left( #1 \right)}
\newcommand{\bigparen}[1]{\bigl( #1 \bigr)}
\newcommand{\Bigparen}[1]{\Bigl( #1 \Bigr)}
\newcommand{\biggparen}[1]{\biggl( #1 \biggr)}
\newcommand{\Biggparen}[1]{\Biggl( #1 \Biggr)}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\Abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\bigabs}[1]{\bigl\lvert #1 \bigr\rvert}
\newcommand{\Bigabs}[1]{\Bigl\lvert #1 \Bigr\rvert}
\newcommand{\biggabs}[1]{\biggl\lvert #1 \biggr\rvert}
\newcommand{\Biggabs}[1]{\Biggl\lvert #1 \Biggr\rvert}
\newcommand{\card}[1]{\lvert #1 \rvert}
\newcommand{\Card}[1]{\left\lvert #1 \right\rvert}
\newcommand{\bigcard}[1]{\bigl\lvert #1 \bigr\rvert}
\newcommand{\Bigcard}[1]{\Bigl\lvert #1 \Bigr\rvert}
\newcommand{\biggcard}[1]{\biggl\lvert #1 \biggr\rvert}
\newcommand{\Biggcard}[1]{\Biggl\lvert #1 \Biggr\rvert}
\newcommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\Norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\bignorm}[1]{\bigl\lVert #1 \bigr\rVert}
\newcommand{\Bignorm}[1]{\Bigl\lVert #1 \Bigr\rVert}
\newcommand{\biggnorm}[1]{\biggl\lVert #1 \biggr\rVert}
\newcommand{\Biggnorm}[1]{\Biggl\lVert #1 \Biggr\rVert}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\Iprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\bigiprod}[1]{\bigl\langle #1 \bigr\rangle}
\newcommand{\Bigiprod}[1]{\Bigl\langle #1 \Bigr\rangle}
\newcommand{\biggiprod}[1]{\biggl\langle #1 \biggr\rangle}
\newcommand{\Biggiprod}[1]{\Biggl\langle #1 \Biggr\rangle}
\newcommand{\set}[1]{\lbrace #1 \rbrace}
\newcommand{\Set}[1]{\left\lbrace #1 \right\rbrace}
\newcommand{\bigset}[1]{\bigl\lbrace #1 \bigr\rbrace}
\newcommand{\Bigset}[1]{\Bigl\lbrace #1 \Bigr\rbrace}
\newcommand{\biggset}[1]{\biggl\lbrace #1 \biggr\rbrace}
\newcommand{\Biggset}[1]{\Biggl\lbrace #1 \Biggr\rbrace}
\newcommand{\bracket}[1]{\lbrack #1 \rbrack}
\newcommand{\Bracket}[1]{\left\lbrack #1 \right\rbrack}
\newcommand{\bigbracket}[1]{\bigl\lbrack #1 \bigr\rbrack}
\newcommand{\Bigbracket}[1]{\Bigl\lbrack #1 \Bigr\rbrack}
\newcommand{\biggbracket}[1]{\biggl\lbrack #1 \biggr\rbrack}
\newcommand{\Biggbracket}[1]{\Biggl\lbrack #1 \Biggr\rbrack}
\newcommand{\ucorner}[1]{\ulcorner #1 \urcorner}
\newcommand{\Ucorner}[1]{\left\ulcorner #1 \right\urcorner}
\newcommand{\bigucorner}[1]{\bigl\ulcorner #1 \bigr\urcorner}
\newcommand{\Bigucorner}[1]{\Bigl\ulcorner #1 \Bigr\urcorner}
\newcommand{\biggucorner}[1]{\biggl\ulcorner #1 \biggr\urcorner}
\newcommand{\Biggucorner}[1]{\Biggl\ulcorner #1 \Biggr\urcorner}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\Ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\bigceil}[1]{\bigl\lceil #1 \bigr\rceil}
\newcommand{\Bigceil}[1]{\Bigl\lceil #1 \Bigr\rceil}
\newcommand{\biggceil}[1]{\biggl\lceil #1 \biggr\rceil}
\newcommand{\Biggceil}[1]{\Biggl\lceil #1 \Biggr\rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\bigfloor}[1]{\bigl\lfloor #1 \bigr\rfloor}
\newcommand{\Bigfloor}[1]{\Bigl\lfloor #1 \Bigr\rfloor}
\newcommand{\biggfloor}[1]{\biggl\lfloor #1 \biggr\rfloor}
\newcommand{\Biggfloor}[1]{\Biggl\lfloor #1 \Biggr\rfloor}
\newcommand{\lcorner}[1]{\llcorner #1 \lrcorner}
\newcommand{\Lcorner}[1]{\left\llcorner #1 \right\lrcorner}
\newcommand{\biglcorner}[1]{\bigl\llcorner #1 \bigr\lrcorner}
\newcommand{\Biglcorner}[1]{\Bigl\llcorner #1 \Bigr\lrcorner}
\newcommand{\bigglcorner}[1]{\biggl\llcorner #1 \biggr\lrcorner}
\newcommand{\Bigglcorner}[1]{\Biggl\llcorner #1 \Biggr\lrcorner}
\newcommand{\e}{\varepsilon}
\newcommand{\eps}{\varepsilon}
\newcommand{\from}{\colon}
\newcommand{\super}[2]{#1^{(#2)}}
\newcommand{\varsuper}[2]{#1^{\scriptscriptstyle (#2)}}
\newcommand{\tensor}{\otimes}
\newcommand{\eset}{\emptyset}
\newcommand{\sse}{\subseteq}
\newcommand{\sst}{\substack}
\newcommand{\ot}{\otimes}
\newcommand{\Esst}[1]{\bbE_{\substack{#1}}}
\newcommand{\vbig}{\vphantum{\bigoplus}}
\newcommand{\seteq}{\mathrel{\mathop:}=}
\newcommand{\defeq}{\stackrel{\mathrm{def}}=}
\newcommand{\bits}{\{0,1\}}
\newcommand{\sbits}{\{\pm 1\}}
\newcommand{\Mid}{\mathrel{}\middle|\mathrel{}}
\newcommand{\Ind}{\mathbf 1}
\newcommand{\R}{\mathbb R}
\newcommand{\Rnn}{\R_{\ge 0}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\mper}{\,.}
\newcommand{\mcom}{\,,}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\opt}{opt}
\DeclareMathOperator{\Opt}{Opt}
\DeclareMathOperator{\Val}{Val}
\DeclareMathOperator{\LP}{LP}
\DeclareMathOperator{\SDP}{SDP}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\Inf}{Inf}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\polylog}{polylog}
\DeclareMathOperator{\argmax}{arg\,max}
\DeclareMathOperator{\argmin}{arg\,min}
\DeclareMathOperator{\qpoly}{qpoly}
\DeclareMathOperator{\qqpoly}{qqpoly}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\Conv}{Conv}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\mspan}{span}
\DeclareMathOperator{\mrank}{rank}
\DeclareMathOperator{\E}{\mathbb E}
\DeclareMathOperator{\pE}{\tilde{\mathbb E}}
\DeclareMathOperator{\Pr}{\mathbb P}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\Cone}{Cone}
\DeclareMathOperator{\junta}{junta}
\DeclareMathOperator{\NSS}{NSS}
\DeclareMathOperator{\SA}{SA}
\DeclareMathOperator{\SOS}{SOS}
\hyperbaseurl{http://toc15.dsteurer.org/}
\notag
\]
Introduction
Recall that in Max3Sat, we are given a list of clauses, each the disjuntion of three boolean literals (either a boolean variable or the negation of one), and the goal is to find an assignment to the variables that satisfies as many of the clauses as possible.
Here is an example of a Max3Sat instance \(\varphi\): \[
\begin{gathered}
x_1 \lor x_2 \lor \neg x_3\,,\\
\neg x_3 \lor \neg x_5 \lor x_7\,,\\
x_2 \lor x_4 \lor x_8\,,\\
\vdots\\
\neg x_7 \lor x_8 \lor \neg x_9\,,\\
\end{gathered}
\]
Notation: For a Max3Sat instance \(\varphi\) and an assignment \(x\) to the variables of \(\varphi\), let \(\val(\varphi,x)\) be the fraction of clauses in \(\varphi\) satisfied by \(x\) and let \(\opt(\varphi)=\max_x \val(\varphi,x)\) be the maximum value of an assignment for \(\varphi\).
In these notes, we will discuss the PCP theorem and its applications to hardness of approximation.
PCP theorem: There exists a polynomial-time function \(f\) that maps every Max3Sat instance \(\varphi\) to a Max3Sat instance \(\varphi'\) with the following properties:
- YES case: if \(opt(\varphi) = 1\) then \(opt(\varphi') = 1\)
- NO case: if \(opt(\varphi) < 1\) then \(opt(\varphi') < 0.99\)
The PCP theorem shows that distinguishing between the cases \(opt(\varphi') = 1\) and \(opt(\varphi') <0.99\) is as hard as deciding 3Sat. in particular, the PCP theorem shows that if \({\mathrm P}\neq {\mathrm{NP}}\) no polynomial time algorithm can achieve approximation ratio 0.99 for Max3Sat.
Aside: For Max3Sat, there is a polynomial-time algorithm that achieves an approximation ratio of 7/8. Refinements of the PCP theorem also show that no polynomial-time algorithm achieves a better approximation ratio.
Aside: The pcp theorem is not just about 3Sat and Max3Sat. Instead of 3Sat, we could choose any NP-complete problem as a starting point. Similarly, instead of Max3Sat, we could choose from a wide range of optimization problems (for example, max-independent-set, see below).
Strategy for proof of PCP theorem
In this course we will discuss a proof of the PCP theorem due to Dinur. The key component of that proof is the following lemma.
Lemma (amplification): There exists a polynomial-time function \(g\) that maps every Max3Sat instance \(\varphi\) to a Max3Sat instance \(\varphi'\) with the following properties:
- YES case: If \(opt(\varphi) = 1\), then \(opt(\varphi')=1\)
- NO case: If \(opt(\varphi) < 1-\varepsilon\) for some \(\varepsilon > 0\), then \(opt(\varphi') < \max\{0.99, 1-2\varepsilon\}\)
- Efficiency: \(|\varphi'| \le O(1) \cdot |\varphi|\)
Assuming this lemma, we can prove the PCP theorem by iterating the function \(g\) a logarithmic number of times.
Proof of PCP theorem from amplification lemma
Let \(t\) be a positive integer to be determined later. Let \(g\) be the t-fold iteration of \(f\). Let \(\varphi\) be an arbitrary Max3Sat instance.
\[
f\from \underbrace{\varphi \mapsto_g \varphi_1 \mapsto_g \cdots \mapsto_g \varphi_t=f(\varphi)}_{\text{$t$ times}}
\]
YES case: First suppose that \(opt(\varphi)=1\). After \(t\) iterations of the function \(g\), we obtain a Max3Sat instance \(\varphi_t\) with optimal value \(\opt(\varphi_t)=1\).
NO case: Next suppose that \(opt(\varphi)<1\). Let \(n=|\varphi|\) be the length of the binary encoding of \(\varphi\). Since \(\varphi\) contains less then n clauses, its optimal value is less than \(opt(\varphi)<(n-1)/n=1-1/n\). Therefore, after \(t\) iterations of the function g, we obtain a Max3Sat instance \(\varphi_t\) with optimal value \(opt(\varphi_t) < \max\{0.99, 1-2^t/n\}\).
Running time: Since \(g\) is polynomial-time computable, the running time of its t-fold iteration \(f\) is polynomial in \(|\varphi|+|\varphi_1|+\dots+|\varphi_t|\). By the efficiency property of the function \(g\), each of these instances has size at most \(O(1)^t \cdot |\varphi_0|\). Therefore, the running time of f on input \(x\) is polynomial in \(t \cdot O(1)^t \cdot |x|\).
Putting it together: We choose \(t=\log n\). Then, in the NO case, we have \[opt(\varphi_t) < \max\{0.99, 1-2^t/n\} = \max\{0.99, 0\} = 0.99\] and the running time of \(g\) on inputs of length \(n\) is \(t \cdot O(1)^t \cdot n = n^{O(1)}\). \(\qed\)
Aside: The strong efficiency guarantee for \(g\) is crucial. If we had a weaker efficiency guarantee, say \(|g(\varphi)|\le \lvert \varphi \rvert^2\), we could only conclude \(\lvert \varphi_t \rvert\le \lvert \varphi \rvert^{2^t}\), which is an exponential blowup for the choice \(t=\log n\).
Hardness of approximation for independent set
Recall: We say a subset \(S\) of vertices is independent in a graph, if no edge of the graph has both endpoints in the set \(S\).
The independet set problem (IndSet) is, given a graph, to find an independent set in the graph that is as large as possible.
Notation: Let \(\alpha(G)\) denote maximum size of a independent set in G.
Theorem. Unless P=NP, there is no polynomial time algorithm that achieves approximation ratio 0.99 for independent set.
We show the theorem by proving the following lemma.
Lemma. There exists a polynomial time function \(f\) that maps every Max3Sat instance \(\varphi\) to a graph \(G\) with \(n\) vertices such that
- YES case: If \(opt(G)=1\), then \(\alpha(G)=\lvert n \rvert/7\)
- NO case: If \(\opt(G)<0.99\), then \(\alpha(G)< 0.99 \cdot \lvert n \rvert/7\)
Proof sketch of lemma. We let \(f\) be the standard NP-hardness reduction from 3Sat to IndSet. Let \(\varphi\) be a 3cnf formula with m clauses. Let \(G\) be the graph obtained by applying the reduction \(f\) to \(\varphi\).
The reduction \(f\) has the property that assignments for \(\varphi\) correspond to independent sets in \(G\) such that the value of the assignment is proportional to the size of the independent set.
Recall that \(G\) contains a “gadget” consisting of 7 vertices for each clause in \(\varphi\) (one vertex per satisfying assignment for the clauses). In particular, if \(\varphi\) consists of \(m\) clauses, then \(G\) has \(n=7m\) vertices. Every assignment \(\varphi\) corresponds to an independent set \(S\) that selects exactly one vertex out of every gadget for a satisfied clause, so that \(|S|=\val(\varphi,x)\cdot n/7\). Similarly, every independent set \(S\) in \(G\) corresponds to an assignment for \(\varphi\) that satisfies every clauses \(C\) such that \(S\) intersects the gadget of clause \(C\). In particular, \(\val(\varphi,x)\cdot n/7\ge |S|\).
It follows that \(\alpha(G)=\opt(\varphi)\cdot \lvert V(G) \rvert/7\), which implies the lemma. \(\qed\)
Gap amplification for independent set
The following theorem shows that if \({\mathrm P}\neq {\mathrm{NP}}\) then no polynomial time algorithm achieves approximation ratio \(0.001\) for independent set. There are refinements of this theorem that rule out approximation ratio \(n^{1-\varepsilon}\) for all constants \(\varepsilon >0\).
Theorem: For every k, there exists a polynomial time computable function \(f\) such that \(\alpha(f(G)) = \alpha(G)^k\) for every graph \(G\). In particular, for \(k=1000\), the function maps every graph \(G\) on \(n\) vertices to a graph \(H\) with the following properties:
- YES case: If \(\alpha(G)\ge n/7\), then \(\alpha(H)\ge (n/7)^k\).
- NO case: If \(\alpha(G)< 0.99\cdot n/7\), then \(\alpha(H)< 0.99^k \cdot (n/7)^k\le 0.001 \cdot (n/7)^k\).
Proof of theorem: Let \(G\) be a graph with vertex set \(V\). Construct \(H\) with vertex set \(V^k\) such that \((u_1 , \dots, u_k) \sim_H (v_1 , \dots, v_k)\) if \(u_i \sim_G v_i\) for at least one \(i\in [k]\). (This construction is sometimes called the \(k\)-fold OR-power of \(G\).)
For a set \(S \subseteq V^k\), let \(S_i \subseteq V\) be the vertices that appear in the \(i\)-th coordinate of \(S\).
By construction of \(H\), the following statements are equivalent for all \(S\subseteq V^k\):
- \(S\) is independent in
- \(S_1, ..., S_k\) are independent in \(G\)
- \(S_1\times \cdots \times S_k\supseteq S\) is independent in \(H\)
It follows that every maximum size independent set in \(H\) is obtained as the cartesian product of maximum size independent sets in \(G\). Therefore, \[
\alpha(H) = \alpha(G)^k\,.\qed
\]