diff options
| -rw-r--r-- | app/Main.hs | 31 | ||||
| -rw-r--r-- | www/teaching/discrete20/index.html | 26 | ||||
| -rw-r--r-- | www/teaching/graphs2022/index.html | 189 | ||||
| -rw-r--r-- | www/teaching/index.md | 4 | ||||
| -rw-r--r-- | www/teaching/matrices2019/index.html | 6 |
5 files changed, 224 insertions, 32 deletions
diff --git a/app/Main.hs b/app/Main.hs index bce890b..ec508d4 100644 --- a/app/Main.hs +++ b/app/Main.hs @@ -36,6 +36,9 @@ main = do match "data/licenses.yaml" $ compile $ yamlCompiler @(AliasMap StrictText License_) match "data/journals.yaml" $ compile $ yamlCompiler @(AliasMap StrictText Journal_) + -- load any snippets + match "**/_*.html" $ compile getResourceBody + match "assets/**" $ do route $ dropParentRoute 1 compile copyFileCompiler @@ -83,6 +86,7 @@ main = do ] -- Remove me from the author list } getResourceBody >>= applyAsTemplate (mkPaperContext (personCtxt "data/people.yaml" <> journalCtxt "data/journals.yaml") fixedPapers) >>= applyTemplate defaultTemplate baseCtxt + match "www/teaching/index.md" $ do route $ dropParentRoute 1 `composeRoutes` setExtension ".html" -- compile $ myPandocCompiler >>= applyAsTemplate baseCtxt >>= applyTemplate defaultTemplate baseCtxt @@ -92,18 +96,27 @@ main = do route $ dropParentRoute 1 `composeRoutes` setExtension ".html" compile $ getResourceBody >>= applyAsTemplate baseCtxt >>= myRenderPandoc >>= applyTemplate defaultTemplate baseCtxt - match "www/contact/*.html" $ do - route $ dropParentRoute 1 - compile $ getResourceBody >>= applyAsTemplate baseCtxt >>= applyTemplate defaultTemplate baseCtxt + -- match "www/contact/*.html" $ do + -- route $ dropParentRoute 1 + -- compile $ getResourceBody >>= applyAsTemplate baseCtxt >>= applyTemplate defaultTemplate baseCtxt + -- + -- match "www/code/*.html" $ do + -- route $ dropParentRoute 1 + -- compile $ getResourceBody >>= applyAsTemplate baseCtxt >>= applyTemplate defaultTemplate baseCtxt + -- + -- match "www/credits/*.html" $ do + -- route $ dropParentRoute 1 + -- compile $ myPandocCompiler >>= applyTemplate defaultTemplate baseCtxt - match "www/code/*.html" $ do + -- compile any other html + match "www/**/*.html" $ do route $ dropParentRoute 1 - compile $ getResourceBody >>= applyAsTemplate baseCtxt >>= applyTemplate defaultTemplate baseCtxt + compile $ getResourceBody >>= applyTemplate defaultTemplate baseCtxt - match "www/credits/*.html" $ do - route $ dropParentRoute 1 - compile $ myPandocCompiler >>= applyTemplate defaultTemplate baseCtxt - pure () + -- just copy anything else hanging around + match "www/**" $ do + route idRoute + compile copyFileCompiler myPandocCompiler :: Compiler (Item String) diff --git a/www/teaching/discrete20/index.html b/www/teaching/discrete20/index.html index 127993c..d8bda32 100644 --- a/www/teaching/discrete20/index.html +++ b/www/teaching/discrete20/index.html @@ -72,19 +72,19 @@ I type these up quickly, so please let me know if you find any mistakes! <li><a href="./rec2.pdf">Recitation 2 — 01/21/20</a></li> <li>Recitation 3 — 01/21/20: I didn't have time to type detailed notes this week, but here's a list of what we covered: <ul> - <li> If $$H_n:=\sum_{k=1}^n{1\over k}$$, then $$H_n\approx\int_1^n{dx\over x}=\log n$$. ($$H_n$$ is known as the $$n$$th harmonic number) + <li> If $H_n:=\sum_{k=1}^n{1\over k}$, then $H_n\approx\int_1^n{dx\over x}=\log n$. ($H_n$ is known as the $n$th harmonic number) <ul> - <li>More precisely, we can bound $$\log(n+1)\leq H_n\leq\log n + 1$$.</li> - <li>Since $${1\over x}$$ is convex, the lower bound can be improved to $$H_n\geq\log n + {1\over 2}+{1\over 2n}$$ by using trapezoids instead of rectangles.</li> + <li>More precisely, we can bound $\log(n+1)\leq H_n\leq\log n + 1$.</li> + <li>Since ${1\over x}$ is convex, the lower bound can be improved to $H_n\geq\log n + {1\over 2}+{1\over 2n}$ by using trapezoids instead of rectangles.</li> </ul> </li> - <li>If $$d(n)$$ denotes the number of divisors of $$n$$, then $$\text{ave}_{k\in[n]}d(k)\approx\log n$$ (see Recitation 2).</li> - <li>Using the same ideas, for any $$d>-1$$, we have $$\sum_{k=1}^n k^d\approx {n^{d+1}\over d+1}$$.</li> + <li>If $d(n)$ denotes the number of divisors of $n$, then $\text{ave}_{k\in[n]}d(k)\approx\log n$ (see Recitation 2).</li> + <li>Using the same ideas, for any $d>-1$, we have $\sum_{k=1}^n k^d\approx {n^{d+1}\over d+1}$.</li> </ul> </li> <li><a href="./rec4.pdf">Recitation 4 — 02/04/20</a> <ul> - <li>We did not cover this in class, but these notes include proof that the number of derangements of $$[n]$$ is precisely the closest integer to $${n!\over e}$$, a fact that was mentioned in Recitation 2.</li> + <li>We did not cover this in class, but these notes include proof that the number of derangements of $[n]$ is precisely the closest integer to ${n!\over e}$, a fact that was mentioned in Recitation 2.</li> </ul> </li> <li><a href="./rec5.pdf">Recitation 5 — 02/11/20</a> (<a href="http://www.math.cmu.edu/~tbohman/21-228/review1.pdf">Review day</a>) @@ -105,16 +105,16 @@ I type these up quickly, so please let me know if you find any mistakes! <ul> <li>I made a remark in recitation about how Claim 1 in the notes changes if we require only pairwise independence instead of mutual independence. There was enough curiosity about this that I wrote up a <a href="./pairwise.pdf">proof</a>. - This proof can be modified to show that if $$A_1,\dots,A_n\subseteq\Omega$$ are nontrivial and have the property that any set of at most $$k$$ of them is independent, then $$|\Omega|\geq\sum_{j=0}^{\lfloor k/2\rfloor}{n\choose j}$$. + This proof can be modified to show that if $A_1,\dots,A_n\subseteq\Omega$ are nontrivial and have the property that any set of at most $k$ of them is independent, then $|\Omega|\geq\sum_{j=0}^{\lfloor k/2\rfloor}{n\choose j}$. <ul> <li>The proof here probably appears to be very ad hoc; this is not actually the case. - Once we learn about random variables (which are simply the elements of $$\mathbb{R}^{\Omega}$$) and expectations, it will be clear that $$\langle X,Y\rangle=\operatorname{\mathbb{E}}XY$$ is a natural inner product on $$\mathbb{R}^{\Omega}$$. - This is all that's going on in the proof, using the random variables $$X_i=\mathbf{1}_{A_i}-\operatorname{\mathbb{E}}\mathbf{1}_{A_i}$$ and $$X_0=1$$. + Once we learn about random variables (which are simply the elements of $\mathbb{R}^{\Omega}$) and expectations, it will be clear that $\langle X,Y\rangle=\operatorname{\mathbb{E}}XY$ is a natural inner product on $\mathbb{R}^{\Omega}$. + This is all that's going on in the proof, using the random variables $X_i=\mathbf{1}_{A_i}-\operatorname{\mathbb{E}}\mathbf{1}_{A_i}$ and $X_0=1$. In fact, the proof is much cleaner when phrased this way.</li> - <li>With this terminology, in order to prove the fact about $$k$$-wise independent events mentioned above, first define $$X_i=\mathbf{1}_{A_i}-\operatorname{\mathbb{E}}\mathbf{1}_{A_i}$$ for $$i\in[n]$$. - Then, for a set $$I\subseteq[n]$$ with $$|I|\leq k/2$$, define $$Y_I=\prod_{i\in I}X_i$$. - With just a bit of work, it can be shown that the $$Y_I$$'s are non-zero and pairwise orthogonal. - If $$k$$ is odd, then the bound can be improved slightly by considering also $$Z_I=X_n\prod_{i\in I}X_i$$ for $$I\in{[n-1]\choose\lfloor k/2\rfloor}$$.</li> + <li>With this terminology, in order to prove the fact about $k$-wise independent events mentioned above, first define $X_i=\mathbf{1}_{A_i}-\operatorname{\mathbb{E}}\mathbf{1}_{A_i}$ for $i\in[n]$. + Then, for a set $I\subseteq[n]$ with $|I|\leq k/2$, define $Y_I=\prod_{i\in I}X_i$. + With just a bit of work, it can be shown that the $Y_I$'s are non-zero and pairwise orthogonal. + If $k$ is odd, then the bound can be improved slightly by considering also $Z_I=X_n\prod_{i\in I}X_i$ for $I\in{[n-1]\choose\lfloor k/2\rfloor}$.</li> </ul> </li> </ul> diff --git a/www/teaching/graphs2022/index.html b/www/teaching/graphs2022/index.html index e72f84c..78be034 100644 --- a/www/teaching/graphs2022/index.html +++ b/www/teaching/graphs2022/index.html @@ -2,7 +2,6 @@ title: MATH 314 (Spring 2022) title_short: Graphs math: true - --- <h1>MATH 314: Graph Theory</h1> @@ -35,7 +34,7 @@ This will help me ensure I don't miss any submissions. </p> <p> -If you wish to write your assignments in $$\LaTeX$$, here's a basic <a href="/doc/hw.tex">homework template</a> you can use. +If you wish to write your assignments in $\LaTeX$, here's a basic <a href="/doc/hw.tex">homework template</a> you can use. </p> <h5>A note on pictures and proofs</h5> @@ -162,7 +161,7 @@ While sketches can be very helpful in understanding a problem and reasoning thro </tr> <tr> <td>Mar 29</td> - <td>Matchings, vertex- and edge-covers, $$\alpha,\alpha',\beta,\beta'$$, Kőnig's Theorem, <a href="./extra_03-29.pdf">extra notes</a></td> + <td>Matchings, vertex- and edge-covers, $\alpha,\alpha',\beta,\beta'$, Kőnig's Theorem, <a href="./extra_03-29.pdf">extra notes</a></td> <td><a href="./hw8.pdf">HW8</a> (<a href="./hw8.tex">.tex</a>)</td> </tr> <tr> @@ -180,7 +179,7 @@ While sketches can be very helpful in understanding a problem and reasoning thro </tr> <tr> <td>Apr 7</td> - <td>$$\chi(G)$$ vs $$\chi(\overline{G})$$, Discussion session #4, <a href="./extra_04-07.pdf">extra notes</a></td> + <td>$\chi(G)$ vs $\chi(\overline{G})$, Discussion session #4, <a href="./extra_04-07.pdf">extra notes</a></td> <td><a href="./ds4.pdf">DS4</a></td> </tr> <tr> @@ -248,4 +247,184 @@ While sketches can be very helpful in understanding a problem and reasoning thro <hr /> -$snippet(replaceFileName(path,"_notation.html"))$ +<h3>Quick notation</h3> +<p> +This list will grow throughout the semester. +</p> +<table> + <tr> + <th style="width: 25%">Notation</th> + <th>Meaning</th> + </tr> + <tr> + <td>$[n]$</td> + <td>$\{1,\dots,n\}$ (Note: $[0]=\varnothing$)</td> + </tr> + <tr> + <td>$2^X$ where $X$ is a set</td> + <td>power-set of $X$ (nb: if $X$ is finite, then $|2^X|=2^{|X|}$)</td> + </tr> + <tr> + <td>${X\choose k}$ where $X$ is a set</td> + <td>$\{S\in 2^X:|S|=k\}$ (nb: if $X$ is finite, then $|{X\choose k}|={|X|\choose k}$)</td> + </tr> + <tr> + <td>$A\sqcup B$</td> + <td>disjoint union of sets $A$ and $B$ (Note: this is identical to the standard union of sets, but we use it to enforce the idea that $A$ and $B$ are disjoint for the sake of brevity. That is to say, $A\sqcup B$ makes sense iff $A$ and $B$ are disjoint. If $A$ and $B$ aren't disjoint, but one still wants to treat them as such when taking their "union", there's a notion known as the co-product of sets, denoted by $A\amalg B$, but we won't use that in this class.)</td> + </tr> + <tr> + <td>$V(G)$</td> + <td>vertex set of $G$</td> + </tr> + <tr> + <td>$E(G)$</td> + <td>edge set of $G$</td> + </tr> + <tr> + <td>$K_n$</td> + <td>clique on $n$ vertices</td> + </tr> + <tr> + <td>$C_n$</td> + <td>cycle on $n$ vertices</td> + </tr> + <tr> + <td>$P_n$</td> + <td>path on $n$ vertices</td> + </tr> + <tr> + <td>$K_{m,n}$</td> + <td>complete bipartite graph with parts of sizes $m$ and $n$</td> + </tr> + <tr> + <td>$K_{n_1,n_2,\dots,n_t}$</td> + <td>complete $t$-partite graph with parts of sizes $n_1,n_2,\dots,n_t$</td> + </tr> + <tr> + <td>$\overline{G}$</td> + <td>complement of $G$</td> + </tr> + <tr> + <td>$G-v$ where $v$ is a vertex of $G$</td> + <td>remove the vertex $v$ along with any incident edges from $G$</td> + </tr> + <tr> + <td>$G-e$ where $e$ is an edge of $G$</td> + <td>remove the edge $e$ from $G$, but keep all vertices</td> + </tr> + <tr> + <td>$G+e$ where $e$ is an edge <em>not</em> in $G$</td> + <td>add the edge $e$ to $G$</td> + </tr> + <tr> + <td>$G-U$ where $U$ is either a set of vertices or a set of edges of $G$</td> + <td>If $U$ is a set of vertices, delete each of them from $G$ along with any incident edges. + If $U$ is a set of edges, delete each of them from $G$ but keep all vertices. + This notation is somewhat ambiguous since an edge $e$ is a set of vertices, so it conflicts with the earlier notation of $G-e$... + In other words, context is necessary when using this notation. + </td> + <tr> + <td>$G[X]$ where $X\subseteq V(G)$</td> + <td>subgraph of $G$ induced by $X$ (Note: $G[X]=G-(V(G)\setminus X)$)</td> + </tr> + <tr> + <td>$L(G)$</td> + <td>the line graph of $G$</td> + </tr> + <tr> + <td>$G\cup H$ or $G\sqcup H$</td> + <td>disjoint union of $G$ and $H$ (Note: I will always use $\sqcup$ since it reinforces the disjointness)</td> + </tr> + <tr> + <td>$G+H$ or $G\vee H$</td> + <td>join of $G$ and $H$</td> + </tr> + <tr> + <td>$G\mathbin\square H$ or $G\times H$</td> + <td>Cartesian product of $G$ and $H$ (Note: Usually $\times$ denotes a different graph product known as the categorical product, so be careful when reading other texts. I will always use $\square$.)</td> + </tr> + <tr> + <td>$d(u,v)$</td> + <td>distance between vertices $u$ and $v$</td> + </tr> + <tr> + <td>$N(v)$</td> + <td>neighborhood of $v$</td> + </tr> + <tr> + <td>$\deg v$</td> + <td>degree of the vertex $v$</td> + </tr> + <tr> + <td>$\Delta(G)$</td> + <td>maximum degree of $G$</td> + </tr> + <tr> + <td>$\delta(G)$</td> + <td>minimum degree of $G$</td> + </tr> + <tr> + <td>$\deg^+ v$ or $\operatorname{od}v$</td> + <td>out-degree of the vertex $v$ in a digraph (Note: I will <em>never</em> use $\operatorname{od}$ since that's just dumb)</td> + </tr> + <tr> + <td>$\deg^- v$ or $\operatorname{id}v$</td> + <td>in-degree of the vertex $v$ in a digraph (Note: I will <em>never</em> use $\operatorname{id}$ since that's just dumb)</td> + </tr> + <tr> + <td>$G\cong H$</td> + <td>$G$ and $H$ are isomorphic graphs</td> + </tr> + <tr> + <td>$\operatorname{Aut}(G)$</td> + <td>automorphism group of $G$</td> + </tr> + <tr> + <td>$\kappa(G)$</td> + <td>vertex-connectivity of $G$</td> + </tr> + <tr> + <td>$\lambda(G)$</td> + <td>edge-connectivity of $G$</td> + </tr> + <tr> + <td>$\alpha(G)$</td> + <td>independence number of $G$</td> + </tr> + <tr> + <td>$\omega(G)$</td> + <td>clique number of $G$</td> + </tr> + <tr> + <td>$\alpha'(G)$</td> + <td>matching number/edge-independence number of $G$, i.e. the largest matching in $G$</td> + </tr> + <tr> + <td>$\beta(G)$</td> + <td>vertex-cover number of $G$, i.e. min number of vertices that touch all edges</td> + </tr> + <tr> + <td>$\beta'(G)$</td> + <td>edge-cover number of $G$, i.e. min number of edges that touch all vertices</td> + </tr> + <tr> + <td>$\chi(G)$</td> + <td>chromatic number of $G$</td> + </tr> + <tr> + <td>$\chi'(G)$</td> + <td>edge-chromatic number/chromatic index of $G$, i.e. chromatic number of $L(G)$</td> + </tr> + <tr> + <td>$R(m,n)$</td> + <td>The Ramsey number of $K_m$ vs $K_n$, i.e. the smallest integer $N$ such that any red,blue-coloring of $E(K_N)$ contains either a red copy of $K_m$ or a blue copy of $K_n$</td> + </tr> +</table> + +<p> +This is a general notational trend in graph theory. +If, say, $\zeta(G)$ is some parameter of $G$ which is defined based mainly on the vertices of $G$ (what exactly this means varies from case-to-case), then generally $\zeta'(G)$ is the analogous parameter of $G$ defined based mainly on the edges of $G$ (again, what exactly this means varies from case-to-case). +Sometimes $\zeta'(G)=\zeta(L(G))$, e.g. $\alpha$ vs $\alpha'$, but not always, e.g. $\beta$ vs $\beta'$. +Also, this trend is broken often enough, e.g. $\kappa$ vs $\lambda$, but it is common enough to point out. +</p> + diff --git a/www/teaching/index.md b/www/teaching/index.md index 029d503..71a7c69 100644 --- a/www/teaching/index.md +++ b/www/teaching/index.md @@ -59,7 +59,7 @@ Fall 2020 Spring 2020 -- **[21-228: Discrete Mathematics](/teaching/discrete20)** (TA for Tom Bohman) +- **[21-228: Discrete Mathematics](/teaching/discrete20)** (TA for $personA("Tom Bohman")$) Summer 2019 @@ -87,7 +87,7 @@ Summer 2016 Spring 2016 -- **[21-228: Discrete Mathematics](/teaching/discrete2016**) (TA for $personA("Tom Bohman")$) +- **[21-228: Discrete Mathematics](/teaching/discrete2016)** (TA for $personA("Tom Bohman")$) Fall 2015 diff --git a/www/teaching/matrices2019/index.html b/www/teaching/matrices2019/index.html index 3541d94..52f94c0 100644 --- a/www/teaching/matrices2019/index.html +++ b/www/teaching/matrices2019/index.html @@ -15,8 +15,8 @@ math: true <dd>6201 Wean Hall</dd> <dd>MWF 12:00–2:00 p.m.</dd> <dt>Textbooks</dt> - <dd><a href="http://joshua.smcvt.edu/linearalgebra/">Linear Algebra</a> by Jim Hefferon (freely available under the terms of the $license("GFDL")$ or the $license("CC BY-SA 2.5")$)</dd> - <dd><a href="http://linear.ups.edu/download.html">A First Course in Linear Algebra</a> by Robert A. Beezer (freely available under the terms of the $license("GFDL")$)</dd> + <dd><a href="http://joshua.smcvt.edu/linearalgebra/">Linear Algebra</a> by Jim Hefferon (freely available under the terms of the GFDL or the CC BY-SA 2.5)</dd> + <dd><a href="http://linear.ups.edu/download.html">A First Course in Linear Algebra</a> by Robert A. Beezer (freely available under the terms of the GFDL)</dd> </dl> <br /> <hr /> @@ -126,7 +126,7 @@ Solutions will be posted after the lecture that day.</p> </tr> <tr> <td>July 23</td> - <td>Orthogonal matrices, isometries of $$\mathbb{R}^n$$</td> + <td>Orthogonal matrices, isometries of $\mathbb{R}^n$</td> <td><a href="hw7.pdf">HW7</a></td> </tr> <tr> |