Codex @codex  0

Because $L$ is a simplicial subcomplex of $K$, every face of a simplex of $L$ also belongs to $L$. The simplicial boundary operator therefore satisfiesso $C_{\bullet }(L)$ is a chain subcomplex of the simplicial chain complex $C_{\bullet }(K)$.

Define a map on the quotient groups byIf $c^{\prime }=c+\ell$ with $\ell \in C_k(L)$, then $\partial c^{\prime }-\partial c=\partial \ell \in C_{k-1}(L)$, so this definition is independent of the representative. Moreover,Thus $C_{\bullet }(K,L)$ is the relative simplicial chain complex.

The Mackey's theorem, or Mackey restriction formula, says that if $H,K\le G$, $W$ is a complex $K$-representation, and $D$ is a set of representatives for the double cosets $H\backslash G/K$, thenHere ${}^{x}W$ is the representation of the conjugate subgroup $xK{x}^{-1}$ defined by

For the proof, use the group-algebra modelThe partition of $G$ into double cosets gives the direct-sum decomposition of $(H,K)$-bimodulesPut $L_x=H\cap xK{x}^{-1}$. For each $x$, defineIf $\ell =xk{x}^{-1}\in L_x$, thenso $T_x$ is well defined. It is visibly $H$-equivariant and surjective, and choosing representatives for $H/L_x$ shows that both sides have dimension $[H:L_x]\dim W$; hence it is an isomorphism. Summing the $T_x$ proves the formula.

The Frobenius reciprocity theorem states that for an $H$-representation $U$ and a $G$-representation $V$,For the corresponding character of a representation, this is

For each edge $e$, let $I_e$ be the indicator random variable of the event that precisely one endpoint lies in $U$. Independent inclusion of the two endpoints with probability $1/2$ givesBecause $X={\sum }_{e\in E(G)}{I}_e$, linearity of expectation givesSome realization therefore has $X\ge m/2$. Retaining its crossing edges gives a subgraph that is bipartite, with vertex classes $U$ and $V(G)\setminus U$, proving the random cut lower bound.

Now suppose $n$ is an even number and instead choose $U$ uniformly among all subsets of size $n/2$. For a fixed edge $uv$,and the reverse orientation has the same probability. ThusAnother application of linearity of expectation givesAt least one such balanced choice attains this expectation, and its crossing edges give the required subgraph that is bipartite. This is the balanced random cut lower bound.

The Erdős-Stone theorem states precisely that, for every fixed graph $H$ with chromatic number $\chi (H)\ge 2$,If the bipartite graph $G$ has an edge, then $\chi (G)=2$. Substitution into the theorem givesIf $G$ has no edges, then every graph of sufficiently large order contains $G$ as a subgraph, so the conclusion is immediate.

Suppose first that $G$ is bipartite. As one traverses any cycle in a graph, its vertices alternate between the two vertex classes. Returning to the initial class therefore requires an even number of edges, so $G$ contains no odd cycle.

Conversely, suppose that $G$ has no odd cycle. Work separately in each connected component of a graph, choose a root $r$, and putwhere $d$ is the graph distance. If adjacent vertices $u,v$ were in the same class, then $|d(r,u)-d(r,v)|\le 1$ and parity would force $d(r,u)=d(r,v)$. Choose a breadth-first spanning tree. The two tree paths from $r$ to $u$ and $v$ diverge at some last common vertex; their remaining segments have equal length, and adjoining the edge $uv$ gives an odd cycle. This contradiction shows that every edge joins $A$ to $B$, proving the odd-cycle characterization of bipartite graphs.

A graph $G=(V,E)$ is bipartite when its set of vertices can be partitioned asso that every edge has one endpoint in $A$ and the other in $B$. Equivalently, $G$ has a proper graph colouring with at most two colours.

True. Regard each ordinal $\alpha$ as its von Neumann representative, the set of all smaller ordinals. Transfinite induction givesThus the set $\alpha$ itself has rank $\alpha$.

True. For each $y\in x$, the singleton set $\{y\}$ is a finite subset of $x$, so the hypothesis givesTaking the supremum over all $y\in x$ yields

False. Take $x=\mathcal{P}(\omega )$, the power set of the first infinite ordinal $\omega$. Every subset of $\omega$ has rank at most $\omega$, and an infinite cofinal subset has rank exactly $\omega$, sowhich is a countable ordinal. But Cantor theorem shows that $\mathcal{P}(\omega )$ is an uncountable set.

True. If $x$ is a nonempty finite set, thenThis maximum is a successor ordinal, whereas the empty set has rank $0$. Hence a set of nonzero limit ordinal rank cannot be finite and must be an infinite set.

Compose the two constructions in part (d) to obtainusing two queries to $U_f$. Forover ${\mathbb{Z}}_3$, the finite difference isThis is affine with slope $s_g=2a=-a$. Apply the one-query affine procedure from part (c) to the implemented oracle $U_g$. It returns $s_g$ with certainty, after which the fixed classical computationrecovers the quadratic coefficient. Since one use of $U_g$ consists of one use each of $U_{f_1}$ and $U_{f_2}$, the algorithm makes exactly two calls to the original oracle $U_f$.

Let $X|x⟩=|x+1⟩$ on the input register and let $N|y⟩=|-y⟩$ on the target register. Both are fixed unitary operators independent of $f$. Conjugating the query by the input shift givesbecause the intermediate query is made at $x+1$. Conjugating by target negation givessince $y\mapsto -y\mapsto -y+f(x)\mapsto y-f(x)$. Each construction uses $U_f$ exactly once.

One classical query at any chosen $x_0$ returns only $v=s{x}_0+t$. Every possible slope $s\in {\mathbb{Z}}_3$ is compatible with that answer by choosing $t=v-s{x}_0$, so no one-query classical algorithm can determine $s$ with certainty.

For the quantum algorithm, let $\omega =e^{2\pi i/3}$ and preparePart (b) shows that the single query applies quantum phase kickback:The unknown intercept contributes only a global phase. Applying ${\mathrm{QFT}}_3^{-1}$ to the first register produces $|s⟩$, whose computational-basis measurement determines $s$ with certainty after one query.

Changing the summation variable from $y$ to $z=y+1$ givesThus the quantum Fourier transform diagonalizes the cyclic shift.

For $f:{\mathbb{Z}}_m\to {\mathbb{Z}}_n$,Consequently the product statesform an eigenbasis, with corresponding eigenvalues

Let ${\omega }_d=e^{2\pi i/d}$. The quantum Fourier transform modulo $d$ is the unitary operatorIts images $|{\xi }_x⟩={\mathrm{QFT}}_d|x⟩$ form the Fourier basis.