Prove that every simple graph with $n$ vertices and $k$ edges has at least $n − k$ connected components (hint: induction on $k$). Proof 1. We proceed by induction. Fix $n\ge 1$ and let $P(k)$ be the statement that every simple graph with $n$ vertices and $k$ edges has at least $n-k$ connected components. We will show that $P(k)$ is true for all $k\ge 0$. Basis Step: $P(0)$ says that a graph with no edges has at least $n$ connected components, and this is true since each vertex is its own connected component. Inductive Step: Assume $P(k)$ is true. Let $G$ be a graph with $n$ vertices and $k+1$ edges. Let $e=uv$ be an arbitrary edge of $G$, and let $G'=G-e$ be the graph obtained by deleting $e$. Let $G_1,\ldots,G_\ell$ be the connected components of $G'$ and note that $\ell \ge n-k$ by the inductive hypothesis. Notice that if $u$ and $v$ are in the same connected component of $G'$, then adding it does not change the connected components, so in this case $G$ also has $\ell$ connected components.

Lecture 1: Propositional Logic A proposition is a declarative sentence that is either true or false but not both. A proposition has a truth value which is either $T$ or $F$. A letter used to denote a proposition is called a propositional variable. If $p$ is a proposition, the negation of $p$, denoted $\lnot p$, is the proposition "it is not the case that $p$". The truth value of $\lnot p$ is the opposite of that of $p$. If $p$ and $q$ are propositions, the conjunction of $p$ and $q$ (denoted $p\land q$) is the proposition "p and q." Its truth value is $T$ when both $p$ and $q$ are $T$, and it is $F$ otherwise. If $p$ and $q$ are propositions,he disjunction of $p$ and $q$ is the proposition "p or q". Its truth value is $T$ when at least one of $p$ or $q$ is $T$, and $F$ if both $p$ and $q$ are $F$. If $p$ and $q$ are propositions, the conditional $p\rightarrow q$ is the proposition "if $p$ then $q$". Its truth values are given by the following truth table (which lists its truth values in terms of those of $p$ and $q$): [see Table 5 in Rosen] The converse of $p\rightarrow q$ is $q\rightarrow p$. A compound proposition consists of logical operations (the four listed above) applied to propositions or propositional variables, possibly with parentheses. The truth value of a compound proposition can be mechanically determined given the truth values of its constituents. Lecture 2: Propositional Functions, Quantifiers, (begin) Rules of Inference

Lecture 14 Basic Terminology, Handshaking Theorem A graph is a pair $G=(V,E)$ where $V$ is a finite set of vertices and $E$ is a finite multiset of $2-$element subsets of $V$, called edges. If $E$ has repeated elements $G$ is called a multigraph, otherwise it is called a simple graph. We will not consider directed graphs or graphs with loops (edges from a vertex to itself). Two vertices $x,y\in V$ are adjacent if ${x,y}\in E$. An edge $e={x,y}$ is said to be incident with $x$ and $y$. The degree of a vertex $x$ is the number of edges incident with it. Theorem. In any graph $G=(V,E)$, $$ \sum_{v\in V} deg(v) = 2|E|.$$ Proof. Let $I={(e,v):e\in E,v\in V,\textrm{$e$ is incident with $v$ in $G$}}$ be the set of edge-vertex incidences in $G$. We will count the number of incidences in two ways: (i) Observe that every edge participates in exactly two incidences, and no incidence participates in more than one edge. Thus, the total number of incidences is $|I|=2|E|$.

The official schedule is posted at https://www.jointmathematicsmeetings.org/meetings/national/jmm2023/2270_program_ss94.html#title The Zoom link for virtual attendance/virtual talks is: https://berkeley.zoom.us/j/94982941411?pwd=RWRXeVdoZUNVTmdqK1FIMksrZFllZz09 Friday, January 6 (101 Hynes Convention Center) 1-2pm: Matt Colbrook, The foundations of infinite-dimensional spectral computations (Zoom) 2-3pm: Josué Tonelli-Cueto, Condition-based Low-Degree Approximation of Real Polynomial Systems

Prove that every simple graph with $n$ vertices and $k$ edges has at least $n − k$ connected components (hint: induction, or contradiction). Let $p\ge 3$ be a prime. Consider the graph $G=(V,E)$ with $V={0,1,2,\ldots, (p-1)}$ and $$E={{x,y}:x-y\equiv 2(mod p)\lor x-y\equiv -2 (mod p)}$$ Show that $G$ is connected. Does $G$ have an Euler circuit? Prove your answer. Let $n\ge 1$ be an integer and let $k\le n/2$. Consider the graph $G=(V,E)$ with $V={S\subseteq {1,2,\ldots,n}: |S|=k}$ and $$E = {{S,T}:|(S-T)\cup (T-S)|=1}.$$ What are the degrees of the vertices in $G$? Is $G$ connected? For which values of $n$ and $k$ does $G$ have an Eulerian circuit? For which values of $n$ and $k$ is $G$ $2-$colorable? Prove your answers.

Week 1 Discussion 101 and 102 (Scott) Problem 1 Let $p$ be the proposition "Scott is in the room."" Let $q$ be the proposition "Today is Friday." Let $r$ be the proposition "It is time for section." (a) Translate $\neg r \to (\neg p \lor q)$ into an English sentence.

$\chi$=characteristic poly (0) What is the smallest gap in eigenvalues of an $n\times n$ integer matrix with small entries? Can it be $2^{-n^2}$? (1) Prob ($\chi(A)= \chi(B)$) is small ($2^{-n^2}$)? ($A,B$ symmetric or non, Bernoulli, 0/1, ...) (1') How many different $\chi$'s are there for bounded height $n\times n$ matrices? Update: we can construct $2^{n^2}$ matrices of size $2n\times 2n$ with entries $0,1,2$ that have distinct $\chi$'s. It now seems we can construct $h^{n^2}$ matrices of height $h$ and size $2n\times 2n$ with distinct and nearly irreducible characteristic polys. This means we get lots of distinct eigenvalues and can force a small gap if we allow a block sum matrix. (1'') Can we make these matrices symmetric? Can we make them irreducible?

Suppose $G=(V,E)$ and $H=(V,F)$ with $G=H+e$ where $e={x,y}\notin F$. We will show that $\chi(G)\le \chi(H)+1$. Let $f:V\rightarrow {1,\ldots,\chi(H)}$ be a coloring of $H$. If $f$ is a valid coloring of $G$ then $\chi(G)=\chi(H)$. Otherwise, we must have $f(x)=f(y)$ since every other edge of $G$ belongs to $H$ and and has endpoints of different colors. Let $f':V\rightarrow{1\ldots,\chi(H)+1}$ be defined by $f'(z)=f(z)$ for all $z\neq x$, and $f'(x)=\chi(H)+1$. Then we have $f'(x)\neq f'(y)$ and $f'$ is a valid coloring of $G$, so $\chi(G)=\chi(H)+1$. Thus, we have shown that $\chi(H)$ is either $\chi(G)$ or $\chi(G)-1$, as desired. Let $x$ and $y$ be the two vertices of odd degree in $G$. Suppose there is no path from $x$ to $y$ in $G$. Then there must be two connected components $H_1$ and $H_2$ of $G$ such that $x\in H_1$, $y\in H_2$, and all other vertices of $H_1$ and $H_2$ have even degree (since the degree of every vertex in $H_1$ or $H_2$ is equal to its degree in $G$). But now $H_1$ has an odd number of vertices (one) with odd degree, which violates the handshaking lemma, a contradiction. Suppose $\pi_1$ and $\pi_2$ are two paths of maximum length in $G$. Let this length be $k$. Assume for contradiction that these paths do not share a common vertex. Let $$ t = \min{dist(x,y):x\in \pi_1, y\in \pi_2}$$ be the minimum distance between a vertex in $\pi_1$ and a vertex in $\pi_2$ and note that $t\ge 1$. Suppose this distance is achieved by vertices $x\in \pi_1$ and $y\in\pi_2$ (i.e., $dist(x,y)=t$) and call the shortest path connecting $x$ and $y$ in $G$ $\gamma$. Notice that $\gamma$ does not intersect $\pi_1$ or $\pi_2$ except possibly at its endpoints; if it did, then a strict subpath of $\gamma$ would connect endpoints in $\pi_1$ and $\pi_2$, contradicting our choice of $\gamma$. $$ $$ Let $s_1,t_1$ be the endpoints of $\pi_1$ and let $s_2,t_2$ be the endpoints of $\pi_2$. Consider the two subpaths of $\pi$ from $s_1$ to $x$ and from $t_1$ to $x$ and notice that one of these must have length greater than or equal to $k/2$, since the sum of the lengths is $k$; call this subpath $\pi_1'$. Similarly, choose a subpath $\pi_2'$ of $\pi_2$ with initial vertex $y$ of length at least $k/2$. Now consider the concatenated path $$P=\pi_1',\gamma,\pi_2'$$

Show that if $G$ is a simple graph and $H$ is obtained by deleting one edge from $G$, then either $\chi(H)=\chi(G)$ or $\chi(H)=\chi(G)-1$ (where $\chi$ denotes the chromatic number). Show that if $G$ has exactly two vertices of odd degree, then there must be a path from one to the other. Show that if $\pi_1$ and $\pi_2$ are two simple paths of maximum length (over all simple paths) in a simple graph $G$, then they must have a common vertex. Practice Final1 number 10.

Dhillon: In [136,p.329], Wilkinson notes that ‘The extreme sensitivity of the computed eigenvector to very small changes in λ [σ in our notation] may be turned to practical advantage and used to obtain independent eigenvectors corresponding to coincident or pathologically close eigenvalues’. Wilkinson proposed that such nearby eigenvalues be ‘artificially separated’ by a tiny amount. Shifted QR Submission 1 Introduction Numerical analysis, dynamical systems.

Question 1: Can one get strong concavity in one of Lieb's inequalities (the p'th power one or the exp-log one) under some conditions on the commutators of the matrices? Concretely, let us look at Lieb's concavity theorem for $p=1$: For all PD $A$, and Hermitian $K$, $f(A) = Tr(\sqrt{A}, K \sqrt{A}, K^\dagger)$ is a concave function of $A$. Conjecture/Question: For some function $\alpha:\mathbb{Z}+ \rightarrow (0,\infty)$, for all $K$, $f(A) = Tr(\sqrt{A}, K \sqrt{A}, K^\dagger)$ is strongly-concave in $A$ with $\nabla^2 f(A) \succeq \alpha_d Tr([A^{-1/2},K] [K^\dagger, A^{-1/2}]) \cdot I{d \otimes d}$. Sketch for derivative along identity: Fix $K$. Let us compute the Hessian of $f(A) = Tr(\sqrt{A}, K \sqrt{A}, K^\dagger)$ along $I_d$. That is, let $g(x) = f(A + x I_d)$. By Lieb's concavity theorem, $g$ is a concave function, and we want to say that $g''(0)$ is positive if $A,K$ do commute in a quantifiable way. Claim: Fix $A, K$ and let $g(x) = f(A + x I_d)$. Then, $g''(0) \geq (1/2) Tr([A^{-1/2},K] [K^\dagger, A^{-1/2}])$.

$$\newcommand{\R}{\mathbb{R}}$$ $$\newcommand{\Ci}{C^\infty(\R)}$$ General Solution and IVP A second order homogeneous ODE is an equation of the form: $$ ay''(t)+by'(t)+cy(t)=0$$ where $y(t)$ is an unknown twice differentiable function from $\R$ to $\R$ and $a\neq 0, b, c$ are real constants. In this course, for simplicity we will further look for solutions which are infinitely differentiable. We will be interested in answering two kinds of questions about such an equation:

We defined orthogonal polynomials ${p_n}$ with respect to a weight function $\mu$ on an interval. We showed that they are an orthogonal basis of $L^2$ when the interval is finite (Weierstrass), and that they satisfy a three term recurrence $$ p_{n+1}(x) = (x-a_n)p_n(x) - b_np_{n-1}(x)$$ for some $a_n$ and $b_n>0$ called Jacobi coefficients (proof: just expand $xp_n(x)$ as a linear combination of $p_0,\ldots,p_{n+1}$ and notice that most terms vanish). We also showed that they have real, distinct roots and that the roots of $p_n$ interlace those of $p_{n+1}$, by recognizing that $p_n$ is the characteristic polynomial of an $n\times n$ tridiagonal matrix $J_n$ with diagonals $a_n$ and off-diagonals $\sqrt{b_n}$. This follows by writing the three-term recurrence in matrix form, evaluating the recurrence for $p_0,\ldots,p_{n-1}$ at the zeros $x_1,\ldots,x_n$ of $p_n(x)$, and applying a similarity by the diagonal matrix with entries $\sqrt{c_j}:=|p_j|$, using further that $b_j=c_j/c_{j-1}$. Lecture 23: Gauss Quadrature, Weights, Favard's Theorem Theorem. Let $x_1,\ldots,x_n$ be the zeros of $p_n(x)$ the $n$th OP with respect to a measure $\mu$. Then there are positive weights $w_i$ such that $$ \int q(x)d\mu(x) = \sum_{i} q(x_i)w_i$$ for every polynomial $f$ of degree at most $2n-1$.

Final exam (timed 1130AM) clarifications and corrections Whenever it says 'find a matrix with nonnegative entries (i.e., $\ge 0$)' this means that all the entries should be nonnegative Both questions are worth 5pts on the AM6 exam (there was a typo saying the second question was 1pt). Final Exam (36-hr part) clarifications and corrections If you did not submit the cheat sheet on time, you can still submit it late and receive a partial credit of $3/5$. Question 6c used to say "find a vector $x$..." but it now says "find a nonzero vector $x$...". In Question 2.10-11, a "function from $\mathbb{R}$ to $\mathbb{R}$" is the same thing as a function $f:\mathbb{R}\rightarrow\mathbb{R}$.

Fridays 1030am-noon in 732 Evans 2/7: Sidhanth, trickling down theorem for link HDX https://arxiv.org/abs/2001.02827 2/14: Theo, one-sided lossless expanders from extractors, https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf 2/21: Theo, continuation of previous week 2/28: Satyaki, Peng-Spielman Laplacian solver https://arxiv.org/abs/1311.3286, 10:30AM 3/6, Rikhav, Adversarial examples in deep learning 3/13, Jorge, Bordenave-Collins and Free Probability 3/20, Sidhanth, The linearization trick and its application to spectral norm bounds 4/3: Archit, Grushin Problems and Random Matrix Theory

# Homework 6 ### Due 12/17 (Tuesday of Finals week) 1. Prove that the Legendre polynomials normalized to have $P_n(1)=1$ satisfy the *Rodridgues Formula* $$p_n(x)=\frac{1}{2^nn!}\frac{d^n}{dx^n} (x^2-1)^n.$$ Use this to show that they satisfy the *Legendre Differential Equation* $$[(x^2-1)u']'=\lambda u,$$ with $\lambda=n(n+1)$. 2. Suppose $p_n(x)$ are monic OPRL on a finite interval $(-a,a)$ with even weight function $w(x)=w(-x)$. Show that the Jacobi coefficients $a_n=0$ for all $n$. 3. (Exe

# Lecture 20: Fourier Transform, The Wave Equation, and Weak Solutions In this lecture we defined the Fourier transform of a tempered distribution and proved that it satisfies the same good properties as the Fourier transform on Schwartz functions. We then used it to solve the IVP for the wave equation: $$ (\partial_t -\Delta_x)u = 0\quad u(0,x)=\phi(x)\quad \partial_t u(0,x)=\psi(x).$$ The development followed Andras Vasy's notes http://math.stanford.edu/~andras/172-5.pdf (see page 8 onwards

# Newsletter Todo List 1. Two relevant pics in data science article (Lin's matlab plots, bio image from Sethian) 2. Box article about 124 with MATH graphic. 3. Picture and color for front page. Sandpile picture? Ask Melanie V? 4. Photos for letter from chair:ask George 5. Distinguished lectures: shorten? 6. Faculty honors: easy, pull from SOD 7. New Faculty: Oh, Corteel, Wood, Lecturers?. (email them; send a link to 2017; ask for a hi res picture) 8. New Postdocs: figure out when they got PHD 9

# Lecture 16: Fourier Transform ###### tags: `224a` $\newcommand{\F}{\mathcal{F}}$ $\newcommand{\R}{\mathbb{R}}$ So far in the course, we studied differential operators on bounded intervals. We began with the Laplacian $-d^2/dx^2$ on $[a,b]$, which we "solved" using Fourier series, and then generalized this to Schrodinger operators of type $L=-d^2/dx^2+q(x)$ on $[a,b]$. The generalization involved developing the theory of compact operators, and then observing that the Green's function $(z-L)^{-1

# Lecture 19: Tempered Distributions ###### tags: `224a` Distributions are objects which are more general than functions. There are at least three motivations for studying them in the context of mathematical physics: 1. We would like objects which model "point" sources and "roughl" forcing functions. 2. We would like to be able to differentiate whatever these objects are, so we can put them in differential equations. 3. We would like to be able to take the Fourier transform of them. We will beg