Functional Analysis: Quotient Spaces; Dimension and Basis

Taken from Functional Analysis by Eidelman, Milman and Tsolomitis; Problem 1.6.1

PROBLEM
Consider the linear subspace $\hat{c}$ of double subsequences $x=(x_n)_{-\infty}^\infty$ such that the limits $b_1=\lim_{n\rightarrow\infty} x_n$ and $b_2=\lim_{n\rightarrow-\infty} x_n$ exist. Consider the subspace $\hat{c}_0$ of the sequences $y=(y_n)_{-\infty}^\infty$ such that $\lim_{n\rightarrow\pm\infty} y_n=0$. Find the dimension and a basis of the space $\hat{c}/\hat{c}_0$.

PROOF
For simplicity, we write $\hat{c}=c$ and $\hat{c}_0=c_0$. For any $x\in c$ we can write it as $x=(\dots, b_2+a_{-3}, b_2+a_{-2}, b_2+a_{-1}, b_1+a_{0},b_1+a_{1}, \dots)$ for $(a_n)_{-\infty}^\infty$ in $c$. We will denote this sequence as $a$.

Now consider the vectors $e_1$ which has all 0's before the 0th index, and all 1's after the 0th index, and $e_2$ with all 1's before the 0th index and all 0's after the 0th index.
So $x=b_1e_1+b_2 e_2+a$. If $e_1, e_2$ are linearly independent in $c_0$, then $e_1, e_2$ would form a basis for the quotient space $c/c_0$ and the dimension is then 2. 

Graph Theory: Crossing Numbers and Number of Subgraphs

PROBLEM

The counting method is the following: for a graph $G$, we count the number $n_{1,H}$ of subgraphs of $G$ that are isomorphic to $H$ and for every crossing of $G$ we are given a number $n_{2,H}$ such that in every drawing of $G$, every pair of crossing edges are contained in at most $n_{2,H}$ subgraphs isomorphic to $H$. It follows (by counting pairs of crossing edges and $H$-isomorphic subgraphs that contain this pair) that $n_{1,H}cr(H)\leq n_{2,H}cr(H)$. Use the counting method for $H=K_n$ and $G=K_{n+1}$ to show that $\displaystyle\frac{cr(K_n)}{{n\choose 4}}$ is an increasing sequence. Show that this sequence has a limit.

PROOF

 Let $n>4$. We first note that $n_{1,{K_n}}={n+1 \choose n}$; this follows from the fact that there are $n$ subgraphs $K_n$ in $K_{n+1}$. Next, we argue that $n_{2,{K_n}}={n-3 \choose n-4}$. We first fix a crossing using 4 vertices. Thus there are $n+1-4$ vertices left to choose a complete subgraph on $n-4$ vertices in $G$. So the claim is true. Now:

\begin{eqnarray*}
n_{1,{K_n}}cr(K_n)&\leq& n_{2,{K_n}}cr(K_{n+1})\\
{{n+1}\choose n}cr(K_n) &\leq& {{n+1}\choose n}cr(K_{n+1})\\
\displaystyle\frac{(n+1)!}{n!}cr(K_n)&\leq& \frac{(n-3)!}{(n-4)!}cr(K_{n+1})\\
\displaystyle\frac{(n+1)!}{4!n!}cr(K_n)&\leq& \frac{(n-3)!}{4!(n-4)!}cr(K_{n+1})\\
\displaystyle\frac{cr(K_n)}{{n\choose 4}}&\leq& \frac{cr(K_{n+1})}{{{n+1}\choose 4}}
\end{eqnarray*}
Thus the sequence is increasing.

Moreover, note that the largest possible number of crossings is ${n \choose 4}$ so $\displaystyle\frac{cr(K_n)}{{n\choose 4}}\leq 1$. Thus the sequence is bounded and monotonic, thus convergent. 

Measure Theory: Egorov's theorem on arbitrary measure spaces

Taken off University of South Carolina's Analysis PhD qualifying exam, January 1999

PROBLEM
Let $(X,\Sigma,\mu)$ be an arbitrary complete measure space and $L_0$ be the collection of all $\mu$-measurable functions from $X\rightarrow \mathbb{R}$, and$\{f_n\}$ be a sequence of functions from $L_0$ that converge almost everywhere to $f_0\in L_0$. Does $f_n\rightarrow f_0$ almost uniformly? (note that $X$ need not be finite).

COUNTEREXAMPLE
Egorov's theorem only holds for finite complete measure spaces. For example, consider $f_n=\chi_{\mathbb{R}\backslash [-n,n]}$ where $\chi$ is the indicator or characteristic function. $f_n\rightarrow 0$ everywhere but for all subsets $K$, $\mu(\mathbb{R}\backslash K)<\epsilon$. Hence $f_n$ does not converge to 0 uniformly. 

Group Theory: Proper subgroups of finite index have proper normal subgroups of finite index.

Taken off  University of South Carolina Algebra PhD Qualifying Exam, January 2007

PROBLEM

Prove that a group with a proper subgroup of finite index has a proper normal subgroup of finite index.

PROOF
Let $G$ be a group and $H$ be a subgroup of finite index. Then $G/H=\{gH\}$ has finitely many elements. Let $G$ act on $G/H$ by $g(xH)=gxH$. This action clearly is well defined and gives rise to the homomorphism $\varphi:G\rightarrow S(G/H)$ where $S(G/H)$ is the permutation group of the elements of $G/H$. So $G/ker \varphi\simeq Im(G)\leq S(G/H)$, which is finite. Since $ker \varphi \triangleleft G$, we have that $G$ has a normal sungroup of finite index.

Graph Theory: Line Graphs are Claw Free

PROBLEM
Prove that a line graph is claw-free.

PROOF

Let $G$ be a simple graph and denote $L(G)$ as it's line graph. We aim to show that $L(G)$ must be claw-free, where a claw is $K_{1,3}$, the complete bipartite graph where one partition has one vertex and the other partition has three vertices. Assume by way of contradiction that $L(G)$ does contain a claw. That would imply that there exists $e_1, e_2, e_3, e_4\in E(G)$ so that, without loss of generality, $e_1, e_2, e_3$ must all share an endpoint with $e_4$. But, $L(G)$ having a claw implied that $e_1,e_2,e_3,e_4$ only shared three common vertices. (that is, the common vertex of $e_4$ and $e_i$ is $v_i$,which is unique, so
we have at most $3$ such vertices. On the other hand, since $e_4$ has only $2$ vertices, two of these must be the same.)
Thus by the pigeonhole principle, it must be that at least two of $e_1,e_2,e_3$ are adjacent. This a contradiction. Thus $L(G)$ must be claw-free.

PDEs: Subdifferentials

Problem taken out of Evans, Partial Differential Equations, Chapter 3 Problem 11. (replace all the v's with q's)
PROBLEM
Let $H: \mathbb{R}^n\rightarrow\mathbb{R}^n$ be convex. We say that $q$ belongs to the subdifferential of $H$ at $p$,written $q\in \partial H(p)$ if $H(r)\geq H(p)+q\cdot(r-p)$ for all $r\in\mathbb{R}^n$.

Prove $q\in\partial H(p) $ if and only if $p\in \partial L(q)$ if and only if $p\cdot q = H(p)+L(q)$ where $L=H^*$, i.e. $L$ is the Legendre (Fenchel) transform of $H$.

PROOF

Assume first that $p\cdot q=H(p)+L(q)$. Clearly $H(p)=p\cdot q - L(q)$. Now observe that since $H(p)+L(r)\geq p\cdot r$ for all $r\in \mathbb{R}^n$ we have that $H(p)\geq p\cdot r - L(r)$. This implies that $p\cdot q - L(q)\geq p\cdot r - L(r)$, which when rearranged gives $L(r)\geq L(q)+p\cdot (r-q)$ for all $r$. So $p\in \partial L(q)$.

Again, assuming that $p\cdot q=H(p)+L(q)$, using a similar argument as above, we claim that $q\in \partial H(p)$. This follows since $L(q)=p\cdot q - H(p)$, and $H(r)+L(q)\geq q \cdot r$ for all $r\in\mathbb{R}^n$, we have that $p\cdot q - H(p)\geq q\cdot r - H(r)$, which when rearranged gives us $H(r)\geq H(p)+q\cdot (r-p)$ for all $r$, which shows the claim is true.

Conversely, assume, that $q\in \partial H(p)$. Then it follows that $H(r)\geq H(p)+q\cdot(r-p)$. Then
\begin{eqnarray*}
q\cdot p&\geq& H(p)+q\cdot r - H(r)\;\; \forall r\in \mathbb{R}^n\\
&\geq& H(p)+\displaystyle\sup_{r\in\mathbb{R}^n}[q\cdot r - H(r)]\\
&\geq& H(p)+L(q)
\end{eqnarray*}
By definition of $L$ and $H$, we have the reverse inequality$H(p)+L(q)\geq p\cdot q$. Hence $H(p)+L(q)=p\cdot q$. The case $p\in \partial L(q)$ is similar. This completes the proof.