diff options
| author | Chris Wells <chris@mathematicaster.org> | 2026-02-08 18:53:16 -0600 |
|---|---|---|
| committer | Chris Wells <chris@mathematicaster.org> | 2026-02-08 18:53:16 -0600 |
| commit | ff65b3f82a5cdb84ef528ca9265d908c55f48902 (patch) | |
| tree | 233c6ddffc22a4813b412f4b4be08d7103bc56c2 | |
| parent | 055b445b7c9c5faccedf6858ba8c2c0c4993b349 (diff) | |
| download | main-ff65b3f82a5cdb84ef528ca9265d908c55f48902.tar main-ff65b3f82a5cdb84ef528ca9265d908c55f48902.tar.gz main-ff65b3f82a5cdb84ef528ca9265d908c55f48902.tar.bz2 main-ff65b3f82a5cdb84ef528ca9265d908c55f48902.tar.lz main-ff65b3f82a5cdb84ef528ca9265d908c55f48902.tar.xz main-ff65b3f82a5cdb84ef528ca9265d908c55f48902.tar.zst main-ff65b3f82a5cdb84ef528ca9265d908c55f48902.zip | |
Eventually each teaching site will be moved into its original repo, but that's for a later date...
178 files changed, 3105 insertions, 0 deletions
diff --git a/www/teaching/algmethods22/index.html b/www/teaching/algmethods22/index.html new file mode 100644 index 0000000..202fa41 --- /dev/null +++ b/www/teaching/algmethods22/index.html @@ -0,0 +1,24 @@ +--- +title: MATH 595 (Spring 2022) +title_short: Algebraic Methods +math: true + +--- + +<h1>MATH 595: Algebraic Methods in Combinatorics</h1> + +<p> +This is a graduate reading course, so there will not be any official homeworks nor assessments. +This page will simply be used for posting relevant materials. +</p> + +<hr /> + +<h3>Resources</h3> +<ul> + <li><a href="https://people.cs.uchicago.edu/~laci/CLASS/HANDOUTS-COMB/BaFrNew.pdf">Linear algebra methods in combinatorics</a> by Babai and Frankl</li> + <li><a href="https://kam.mff.cuni.cz/~matousek/la-ams.html">Thirty-three miniatures</a> by Jiří Matoušek</li> + <li><a href="https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/">A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound</a> by Terry Tao (blog post)</li> + <li><a href="./lovasz_shannon.pdf">On the Shannon capacity of a graph</a> by László Lovász</li> + <li><a href="https://arxiv.org/abs/2108.00074">Sharp density bounds on the finite field Kakeya problem</a> by Boris Bukh and Ting-Wei Chao</li> +</ul> diff --git a/www/teaching/algmethods22/lovasz_shannon.pdf b/www/teaching/algmethods22/lovasz_shannon.pdf Binary files differnew file mode 100644 index 0000000..021b4e2 --- /dev/null +++ b/www/teaching/algmethods22/lovasz_shannon.pdf diff --git a/www/teaching/calcI21/challenge1.pdf b/www/teaching/calcI21/challenge1.pdf Binary files differnew file mode 100644 index 0000000..857be98 --- /dev/null +++ b/www/teaching/calcI21/challenge1.pdf diff --git a/www/teaching/calcI21/challenge2.pdf b/www/teaching/calcI21/challenge2.pdf Binary files differnew file mode 100644 index 0000000..325db58 --- /dev/null +++ b/www/teaching/calcI21/challenge2.pdf diff --git a/www/teaching/calcI21/challenge3.pdf b/www/teaching/calcI21/challenge3.pdf Binary files differnew file mode 100644 index 0000000..0a5dfec --- /dev/null +++ b/www/teaching/calcI21/challenge3.pdf diff --git a/www/teaching/calcI21/index.html b/www/teaching/calcI21/index.html new file mode 100644 index 0000000..24c6c62 --- /dev/null +++ b/www/teaching/calcI21/index.html @@ -0,0 +1,28 @@ +--- +title: MATH 165 (spring 2021) +title_short: Calculus I +math: true + +--- + +<h1>MATH 165: Calculus I</h1> +<h4><a href="https://www.calc1.org/">Recorded lectures</a></h4> +<h4>Other materials available on <a href="https://canvas.iastate.edu/">Canvas</a></h4> +<dl> + <dt>Lecture</dt> + <dd>Gilman 1652</dd> + <dd>MRF 11:00–11:50am </dd> + <dt>Recitation</dt> + <dd>Gilman 1652</dd> + <dd>T 11:00–11:50am</dd> +</dl> +<br /> +<hr /> + +<h2>Challenge Problem Sets</h2> + +<ul> + <li><a href="challenge1.pdf">Challenge Set #1</a></li> + <li><a href="challenge2.pdf">Challenge Set #2</a></li> + <li><a href="challenge3.pdf">Challenge Set #3</a></li> +</ul> diff --git a/www/teaching/concepts2017/.htaccess b/www/teaching/concepts2017/.htaccess new file mode 100644 index 0000000..b7e9e10 --- /dev/null +++ b/www/teaching/concepts2017/.htaccess @@ -0,0 +1,10 @@ +AuthUserFile /var/www/htpass/concepts2017/solutions +AuthName "Homework Solutions" +AuthType Basic +<Files ".htaccess"> +order allow,deny +deny from all +</Files> +<FilesMatch ".*sol\.pdf$"> +require user concepts +</FilesMatch> diff --git a/www/teaching/concepts2017/.password b/www/teaching/concepts2017/.password new file mode 100644 index 0000000..0c66a6a --- /dev/null +++ b/www/teaching/concepts2017/.password @@ -0,0 +1 @@ +concepts:proveit! diff --git a/www/teaching/concepts2017/DSW2.pdf b/www/teaching/concepts2017/DSW2.pdf Binary files differnew file mode 100644 index 0000000..a9455fd --- /dev/null +++ b/www/teaching/concepts2017/DSW2.pdf diff --git a/www/teaching/concepts2017/DSW3.pdf b/www/teaching/concepts2017/DSW3.pdf Binary files differnew file mode 100644 index 0000000..3677576 --- /dev/null +++ b/www/teaching/concepts2017/DSW3.pdf diff --git a/www/teaching/concepts2017/DSW4.pdf b/www/teaching/concepts2017/DSW4.pdf Binary files differnew file mode 100644 index 0000000..8d3d285 --- /dev/null +++ b/www/teaching/concepts2017/DSW4.pdf diff --git a/www/teaching/concepts2017/DSW5.pdf b/www/teaching/concepts2017/DSW5.pdf Binary files differnew file mode 100644 index 0000000..35dbf05 --- /dev/null +++ b/www/teaching/concepts2017/DSW5.pdf diff --git a/www/teaching/concepts2017/NHW1.pdf b/www/teaching/concepts2017/NHW1.pdf Binary files differnew file mode 100644 index 0000000..8b8923f --- /dev/null +++ b/www/teaching/concepts2017/NHW1.pdf diff --git a/www/teaching/concepts2017/NHW10.pdf b/www/teaching/concepts2017/NHW10.pdf Binary files differnew file mode 100644 index 0000000..6ea8677 --- /dev/null +++ b/www/teaching/concepts2017/NHW10.pdf diff --git a/www/teaching/concepts2017/NHW10re.pdf b/www/teaching/concepts2017/NHW10re.pdf Binary files differnew file mode 100644 index 0000000..8b82127 --- /dev/null +++ b/www/teaching/concepts2017/NHW10re.pdf diff --git a/www/teaching/concepts2017/NHW11.pdf b/www/teaching/concepts2017/NHW11.pdf Binary files differnew file mode 100644 index 0000000..7a59181 --- /dev/null +++ b/www/teaching/concepts2017/NHW11.pdf diff --git a/www/teaching/concepts2017/NHW11re.pdf b/www/teaching/concepts2017/NHW11re.pdf Binary files differnew file mode 100644 index 0000000..2f9b05c --- /dev/null +++ b/www/teaching/concepts2017/NHW11re.pdf diff --git a/www/teaching/concepts2017/NHW12.pdf b/www/teaching/concepts2017/NHW12.pdf Binary files differnew file mode 100644 index 0000000..412a687 --- /dev/null +++ b/www/teaching/concepts2017/NHW12.pdf diff --git a/www/teaching/concepts2017/NHW12re.pdf b/www/teaching/concepts2017/NHW12re.pdf Binary files differnew file mode 100644 index 0000000..5f57cfc --- /dev/null +++ b/www/teaching/concepts2017/NHW12re.pdf diff --git a/www/teaching/concepts2017/NHW13.pdf b/www/teaching/concepts2017/NHW13.pdf Binary files differnew file mode 100644 index 0000000..8208b80 --- /dev/null +++ b/www/teaching/concepts2017/NHW13.pdf diff --git a/www/teaching/concepts2017/NHW13re.pdf b/www/teaching/concepts2017/NHW13re.pdf Binary files differnew file mode 100644 index 0000000..5c47c87 --- /dev/null +++ b/www/teaching/concepts2017/NHW13re.pdf diff --git a/www/teaching/concepts2017/NHW1re.pdf b/www/teaching/concepts2017/NHW1re.pdf Binary files differnew file mode 100644 index 0000000..f6271b5 --- /dev/null +++ b/www/teaching/concepts2017/NHW1re.pdf diff --git a/www/teaching/concepts2017/NHW2.pdf b/www/teaching/concepts2017/NHW2.pdf Binary files differnew file mode 100644 index 0000000..08cdba4 --- /dev/null +++ b/www/teaching/concepts2017/NHW2.pdf diff --git a/www/teaching/concepts2017/NHW2re.pdf b/www/teaching/concepts2017/NHW2re.pdf Binary files differnew file mode 100644 index 0000000..135fa2a --- /dev/null +++ b/www/teaching/concepts2017/NHW2re.pdf diff --git a/www/teaching/concepts2017/NHW3.pdf b/www/teaching/concepts2017/NHW3.pdf Binary files differnew file mode 100644 index 0000000..c8fe5b9 --- /dev/null +++ b/www/teaching/concepts2017/NHW3.pdf diff --git a/www/teaching/concepts2017/NHW3re.pdf b/www/teaching/concepts2017/NHW3re.pdf Binary files differnew file mode 100644 index 0000000..7171728 --- /dev/null +++ b/www/teaching/concepts2017/NHW3re.pdf diff --git a/www/teaching/concepts2017/NHW4.pdf b/www/teaching/concepts2017/NHW4.pdf Binary files differnew file mode 100644 index 0000000..694630b --- /dev/null +++ b/www/teaching/concepts2017/NHW4.pdf diff --git a/www/teaching/concepts2017/NHW4re.pdf b/www/teaching/concepts2017/NHW4re.pdf Binary files differnew file mode 100644 index 0000000..a07c726 --- /dev/null +++ b/www/teaching/concepts2017/NHW4re.pdf diff --git a/www/teaching/concepts2017/NHW5.pdf b/www/teaching/concepts2017/NHW5.pdf Binary files differnew file mode 100644 index 0000000..f196413 --- /dev/null +++ b/www/teaching/concepts2017/NHW5.pdf diff --git a/www/teaching/concepts2017/NHW5re.pdf b/www/teaching/concepts2017/NHW5re.pdf Binary files differnew file mode 100644 index 0000000..d41e140 --- /dev/null +++ b/www/teaching/concepts2017/NHW5re.pdf diff --git a/www/teaching/concepts2017/NHW6.pdf b/www/teaching/concepts2017/NHW6.pdf Binary files differnew file mode 100644 index 0000000..9d0b6ce --- /dev/null +++ b/www/teaching/concepts2017/NHW6.pdf diff --git a/www/teaching/concepts2017/NHW6re.pdf b/www/teaching/concepts2017/NHW6re.pdf Binary files differnew file mode 100644 index 0000000..920d648 --- /dev/null +++ b/www/teaching/concepts2017/NHW6re.pdf diff --git a/www/teaching/concepts2017/NHW7.pdf b/www/teaching/concepts2017/NHW7.pdf Binary files differnew file mode 100644 index 0000000..58ec984 --- /dev/null +++ b/www/teaching/concepts2017/NHW7.pdf diff --git a/www/teaching/concepts2017/NHW7re.pdf b/www/teaching/concepts2017/NHW7re.pdf Binary files differnew file mode 100644 index 0000000..652ec00 --- /dev/null +++ b/www/teaching/concepts2017/NHW7re.pdf diff --git a/www/teaching/concepts2017/NHW8.pdf b/www/teaching/concepts2017/NHW8.pdf Binary files differnew file mode 100644 index 0000000..4eac8c0 --- /dev/null +++ b/www/teaching/concepts2017/NHW8.pdf diff --git a/www/teaching/concepts2017/NHW8re.pdf b/www/teaching/concepts2017/NHW8re.pdf Binary files differnew file mode 100644 index 0000000..c15f90e --- /dev/null +++ b/www/teaching/concepts2017/NHW8re.pdf diff --git a/www/teaching/concepts2017/NHW9.pdf b/www/teaching/concepts2017/NHW9.pdf Binary files differnew file mode 100644 index 0000000..90cc837 --- /dev/null +++ b/www/teaching/concepts2017/NHW9.pdf diff --git a/www/teaching/concepts2017/NHW9re.pdf b/www/teaching/concepts2017/NHW9re.pdf Binary files differnew file mode 100644 index 0000000..aff2ac3 --- /dev/null +++ b/www/teaching/concepts2017/NHW9re.pdf diff --git a/www/teaching/concepts2017/Sullivan_Text.pdf b/www/teaching/concepts2017/Sullivan_Text.pdf Binary files differnew file mode 100644 index 0000000..996f55c --- /dev/null +++ b/www/teaching/concepts2017/Sullivan_Text.pdf diff --git a/www/teaching/concepts2017/WHW1.pdf b/www/teaching/concepts2017/WHW1.pdf Binary files differnew file mode 100644 index 0000000..b80ab46 --- /dev/null +++ b/www/teaching/concepts2017/WHW1.pdf diff --git a/www/teaching/concepts2017/WHW2.pdf b/www/teaching/concepts2017/WHW2.pdf Binary files differnew file mode 100644 index 0000000..9b974c4 --- /dev/null +++ b/www/teaching/concepts2017/WHW2.pdf diff --git a/www/teaching/concepts2017/WHW2re.pdf b/www/teaching/concepts2017/WHW2re.pdf Binary files differnew file mode 100644 index 0000000..35d7e1b --- /dev/null +++ b/www/teaching/concepts2017/WHW2re.pdf diff --git a/www/teaching/concepts2017/WHW3.pdf b/www/teaching/concepts2017/WHW3.pdf Binary files differnew file mode 100644 index 0000000..1e9624f --- /dev/null +++ b/www/teaching/concepts2017/WHW3.pdf diff --git a/www/teaching/concepts2017/WHW3re.pdf b/www/teaching/concepts2017/WHW3re.pdf Binary files differnew file mode 100644 index 0000000..d2ffbf2 --- /dev/null +++ b/www/teaching/concepts2017/WHW3re.pdf diff --git a/www/teaching/concepts2017/WHW4.pdf b/www/teaching/concepts2017/WHW4.pdf Binary files differnew file mode 100644 index 0000000..23fd6ef --- /dev/null +++ b/www/teaching/concepts2017/WHW4.pdf diff --git a/www/teaching/concepts2017/WHW4re.pdf b/www/teaching/concepts2017/WHW4re.pdf Binary files differnew file mode 100644 index 0000000..5b72b19 --- /dev/null +++ b/www/teaching/concepts2017/WHW4re.pdf diff --git a/www/teaching/concepts2017/WHW5.pdf b/www/teaching/concepts2017/WHW5.pdf Binary files differnew file mode 100644 index 0000000..ad91b26 --- /dev/null +++ b/www/teaching/concepts2017/WHW5.pdf diff --git a/www/teaching/concepts2017/WHW5re.pdf b/www/teaching/concepts2017/WHW5re.pdf Binary files differnew file mode 100644 index 0000000..59802c9 --- /dev/null +++ b/www/teaching/concepts2017/WHW5re.pdf diff --git a/www/teaching/concepts2017/index.html b/www/teaching/concepts2017/index.html new file mode 100644 index 0000000..914b45e --- /dev/null +++ b/www/teaching/concepts2017/index.html @@ -0,0 +1,198 @@ +--- +title: 21-127 (summer 2017) +title_short: Concepts of Math + +--- + +<h1>21-127: Concepts of Mathematics</h1> +<h4><a href="syllabus.pdf">Course Information</a></h4> +<dl> + <dt>Lecture</dt> + <dd>MTWRF 9:00-10:20</dd> + <dt>Office hours</dt> + <dd>MTWRF 1:30-2:30</dd> +</dl> + +<br /> +<hr /> + +<h2>Schedule and Assignments</h2> +<h4><a href="/doc/hw.tex">Homework Template</a></h4> +<p>Weekly assignments are due on the Friday of their respective weeks. <br /> +Nightly assignments are due on the date by which they are posted.</p> +<table class="cellpadding" style="width: 100%" > + <tr> + <td style="width: 15%"><b>Week #1</b></td> + <td colspan="2"><a href="WHW1.pdf">WHW1</a></td> + </tr> + <tr> + <td>July 3</td> + <td>Introduction to mathematical thinking and the need for formal arguments</td> + <td></td> + </tr> + <tr> + <td>July 4</td> + <td><b>No Class</b></td> + <td></td> + </tr> + <tr> + <td>July 5</td> + <td>Introduction to propositional logic</td> + <td style="width: 25%"></td> + </tr> + <tr> + <td>July 6</td> + <td>Propositional logic and elementary proof techniques</td> + <td><a href="NHW1.pdf">NHW1</a> | <a href="NHW1re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 7</td> + <td>Elementary proof techniques</td> + <td></td> + </tr> + <tr> + <td style="width: 15%"><b>Week #2</b></td> + <td colspan="2"><a href="WHW2.pdf">WHW2</a> | <a href="WHW2re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 10</td> + <td>Sets: set operations and containment arguments</td> + <td><a href="NHW2.pdf">NHW2</a> | <a href="NHW2re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 11</td> + <td>Sets: indexed operations</td> + <td><a href="NHW3.pdf">NHW3</a> | <a href="NHW3re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 12</td> + <td>Cartesian products and functions</td> + <td><a href="NHW4.pdf">NHW4</a> | <a href="NHW4re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 13</td> + <td>Functions: images and preimages</td> + <td></td> + </tr> + <tr> + <td>July 14</td> + <td><a href="DSW2.pdf">Discussion session</a></td> + <td></td> + </tr> + <tr> + <td style="width: 15%"><b>Week #3</b></td> + <td colspan="2"><a href="WHW3.pdf">WHW3</a> | <a href="WHW3re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 17</td> + <td>Induction to induction</td> + <td><a href="NHW5.pdf">NHW5</a> | <a href="NHW5re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 18</td> + <td>Induction: examples and pitfalls</td> + <td><a href="NHW6.pdf">NHW6</a> | <a href="NHW6re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 19</td> + <td>Induction: strong and weak induction</td> + <td><a href="NHW7.pdf">NHW7</a> | <a href="NHW7re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 20</td> + <td>Induction: more examples</td> + <td></td> + </tr> + <tr> + <td>July 21</td> + <td><a href="DSW3.pdf">Discussion session</a></td> + <td></td> + </tr> + <tr> + <td style="width: 15%"><b>Week #4</b></td> + <td colspan="2"><a href="WHW4.pdf">WHW4</a> | <a href="WHW4re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 24</td> + <td>Properties of the integers: divisibility and primes</td> + <td><a href="NHW8.pdf">NHW8</a> | <a href="NHW8re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 25</td> + <td>Properties of the integers: prime factorization and division algorithm</td> + <td><a href="NHW9.pdf">NHW9</a> | <a href="NHW9re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 26</td> + <td>Modular arithmetic</td> + <td><a href="NHW10.pdf">NHW10</a> | <a href="NHW10re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 27</td> + <td>Modular arithmetic: theorems and diophantine equations</td> + <td>Office hours in 6203</td> + </tr> + <tr> + <td>July 28</td> + <td><a href="DSW4.pdf">Discussion session</a>: introducing <a href="https://josephguybriggs.wordpress.com/">Joe Briggs</a>!</td> + <td>Office hours in 6203</td> + </tr> + <tr> + <td style="width: 15%"><b>Week #5</b></td> + <td colspan="2"><a href="WHW5.pdf">WHW5</a> | <a href="WHW5re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>July 31</td> + <td>Back to functions: meet George Jection</td> + <td><a href="NHW11.pdf">NHW11</a> | <a href="NHW11re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>Aug 1</td> + <td>Cardinality of sets</td> + <td><a href="NHW12.pdf">NHW12</a> | <a href="NHW12re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>Aug 2</td> + <td>Cardinality: to infinity and beyond</td> + <td><a href="NHW13.pdf">NHW13</a> | <a href="NHW13re.pdf">Rewrite</a></td> + </tr> + <tr> + <td>Aug 3</td> + <td>Counting with bijections</td> + <td></td> + </tr> + <tr> + <td>Aug 4</td> + <td><a href="DSW5.pdf">Discussion session</a></td> + <td></td> + </tr> + <tr> + <td style="width: 15%"><b>Week #6</b></td> + <td colspan="2">No homework this week. Focus on studying and rewriting assignments</td> + </tr> + <tr> + <td>Aug 7</td> + <td>The pigeonhole principle</td> + <td></td> + </tr> + <tr> + <td>Aug 8</td> + <td>Double counting proofs</td> + <td></td> + </tr> + <tr> + <td>Aug 9</td> + <td>Funzies: winning strategies for games, etc</td> + <td></td> + </tr> + <tr> + <td>Aug 10</td> + <td><a href="review.pdf">Review</a></td> + <td></td> + </tr> + <tr> + <td>Aug 11</td> + <td><b>Final Exam</b></td> + <td></td> + </tr> +</table> diff --git a/www/teaching/concepts2017/review.pdf b/www/teaching/concepts2017/review.pdf Binary files differnew file mode 100644 index 0000000..ebc3b03 --- /dev/null +++ b/www/teaching/concepts2017/review.pdf diff --git a/www/teaching/concepts2017/syllabus.pdf b/www/teaching/concepts2017/syllabus.pdf Binary files differnew file mode 100644 index 0000000..691014c --- /dev/null +++ b/www/teaching/concepts2017/syllabus.pdf diff --git a/www/teaching/discrete20/.htaccess b/www/teaching/discrete20/.htaccess new file mode 100644 index 0000000..4b0784f --- /dev/null +++ b/www/teaching/discrete20/.htaccess @@ -0,0 +1,19 @@ +AuthUserFile /var/www/htpass/discrete20/quizzes +AuthName "Quiz Solutions" +AuthType Basic +<Files ".htaccess"> +order allow,deny +deny from all +</Files> +<Files "quiz11sol.pdf"> +require user quiz11 +</Files> +<Files "quiz12sol.pdf"> +require user quiz12 +</Files> +<Files "quiz13sol.pdf"> +require user quiz13 +</Files> +<Files "quiz14sol.pdf"> +require user quiz14 +</Files> diff --git a/www/teaching/discrete20/.password b/www/teaching/discrete20/.password new file mode 100644 index 0000000..1752676 --- /dev/null +++ b/www/teaching/discrete20/.password @@ -0,0 +1,4 @@ +quiz11:bediscrete +quiz12:cediscrete +quiz13:g1mm3acc355 +quiz14:almostdone diff --git a/www/teaching/discrete20/extra.pdf b/www/teaching/discrete20/extra.pdf Binary files differnew file mode 100644 index 0000000..a23a683 --- /dev/null +++ b/www/teaching/discrete20/extra.pdf diff --git a/www/teaching/discrete20/hats.pdf b/www/teaching/discrete20/hats.pdf Binary files differnew file mode 100644 index 0000000..53446fd --- /dev/null +++ b/www/teaching/discrete20/hats.pdf diff --git a/www/teaching/discrete20/index.html b/www/teaching/discrete20/index.html new file mode 100644 index 0000000..127993c --- /dev/null +++ b/www/teaching/discrete20/index.html @@ -0,0 +1,157 @@ +--- +title: 21-228 (spring 2020) +title_short: Discrete Math +math: true + +--- + +<h1>21-228: Discrete Mathematics</h1> + +<h4><a href="http://www.math.cmu.edu/~tbohman/21-228/discrete.html">Official course webpage</a></h4> + +<p><b>Class meetings:</b></p> + +<table> + <tr> + <td><b>Lecture</b></td> + <td><b>§A</b></td> + <td><b>§B</b></td> + <td><b>§C</b></td> + </tr> + <tr> + <td>MWF 1:30–2:20</td> + <td>T 8:30–9:20</td> + <td>T 9:30–10:20</td> + <td>T 4:30–5:30</td> + </tr> + <tr> + <td>Hamerschlag B131</td> + <td>Posner 146</td> + <td>Scaife 219</td> + <td>Baker 235A</td> + </tr> +</table> + +<p><b>Office hours:</b></p> + +<table> + <tr> + <td><b>Tom</b></td> + <td><b>Chris</b></td> + <td><b>Sunny</b></td> + </tr> + <tr> + <td>W 2:30–4:30</td> + <td>R 12:30–2:30</td> + <td>R 4:30–5:30</td> + </tr> + <tr> + <td>Wean 6113</td> + <td>Wean 6201</td> + <td>Wean 6215</td> + </tr> +</table> + +<br /> + +<hr /> + +<h2>Recitation notes</h2> + +<p> +I'll do my best to write notes about what was covered in recitation each week and post them here. +However, due to my schedule, I'll likely be unable to do this some weeks and other weeks may have only very brief notes. +</p> + +<p> +I type these up quickly, so please let me know if you find any mistakes! +</p> + +<ul> + <li><a href="./rec1.pdf">Recitation 1 — 01/14/20</a></li> + <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) + <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> + </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> + </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> + </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>) + <ul> + <li>I'm out of town Mon–Wed this week</li> + </ul> + </li> + <li><a href="./rec6.pdf">Recitation 6 — 02/18/20</a> (These notes were scrapped last-minute so that we could focus on reviewing troublesome topics from the exam. However, since I'd already written them, they're here for your reading pleasure!) + <ul> + <li>I'm out of town Wed–Fri this week</li> + <li>Consequently, I'll be holding office hours instead on Mon 11:30–1:30</li> + </ul> + </li> + <li><a href="./rec7.pdf">Recitation 7 — 02/25/20</a></li> + <li><a href="./rec8.pdf">Recitation 8 — 03/03/20</a></li> + <li>03/17/20: Recitation is canceled this week as CMU transitions to remote teaching amid COVID-19 concerns</li> + <li><a href="./rec9.pdf">Recitation 9 — 03/24/20</a> + <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}$$. + <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$$. + 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> + </ul> + </li> + </ul> + </li> + <li><a href="./rec10.pdf">Recitation 10 — 03/31/20</a> + <ul> + <li>A few of you asked about the footnote remark in the exercise in these notes, so here's a <a href="./hats.pdf">proof sketch</a>. (Note: this has nothing to do with probability)</li> + </ul> + </li> + <li><a href="./rec11.pdf">Recitation 11 — 04/07/20</a> + <ul> + <li><a href="./quiz11.pdf">Quiz 11</a></li> + </ul> + </li> + <li><a href="./rec12.pdf">Recitation 12 — 04/14/20</a> + <ul> + <li><a href="./quiz12.pdf">Quiz 12</a></li> + </ul> + </li> + <li>Recitation 13 — 04/21/20 (<a href="http://www.math.cmu.edu/~tbohman/21-228/review3.pdf">Review day</a>) + <ul> + <li><a href="./quiz13.pdf">Quiz 13</a></li> + </ul> + </li> + <li>Recitation 14 — 04/28/20 (Last recitation! Exam review) + <ul> + <li><a href="./quiz14.pdf">Quiz 14</a></li> + <li><a href="./extra.pdf">Here</a> are some extra practice problems about spanning trees. + </ul> + </li> +</ul> + +<br /> +<hr /> + +<h5>Supplementary materials</h5> + +<ul> + <li><a href="./pie.pdf">Here</a> is yet another proof of the inclusion-exclusion formula and the Bonferonni inequalities. The proof is essentially identical to the one Tom gave in lecture; it is simply a different way to phrase that idea.</li> +</ul> diff --git a/www/teaching/discrete20/pairwise.pdf b/www/teaching/discrete20/pairwise.pdf Binary files differnew file mode 100644 index 0000000..599101d --- /dev/null +++ b/www/teaching/discrete20/pairwise.pdf diff --git a/www/teaching/discrete20/pie.pdf b/www/teaching/discrete20/pie.pdf Binary files differnew file mode 100644 index 0000000..ca487f4 --- /dev/null +++ b/www/teaching/discrete20/pie.pdf diff --git a/www/teaching/discrete20/quiz11.pdf b/www/teaching/discrete20/quiz11.pdf Binary files differnew file mode 100644 index 0000000..7c1531f --- /dev/null +++ b/www/teaching/discrete20/quiz11.pdf diff --git a/www/teaching/discrete20/quiz12.pdf b/www/teaching/discrete20/quiz12.pdf Binary files differnew file mode 100644 index 0000000..168d8c7 --- /dev/null +++ b/www/teaching/discrete20/quiz12.pdf diff --git a/www/teaching/discrete20/quiz13.pdf b/www/teaching/discrete20/quiz13.pdf Binary files differnew file mode 100644 index 0000000..5b642cb --- /dev/null +++ b/www/teaching/discrete20/quiz13.pdf diff --git a/www/teaching/discrete20/quiz14.pdf b/www/teaching/discrete20/quiz14.pdf Binary files differnew file mode 100644 index 0000000..bf181a6 --- /dev/null +++ b/www/teaching/discrete20/quiz14.pdf diff --git a/www/teaching/discrete20/rec1.pdf b/www/teaching/discrete20/rec1.pdf Binary files differnew file mode 100644 index 0000000..42761b7 --- /dev/null +++ b/www/teaching/discrete20/rec1.pdf diff --git a/www/teaching/discrete20/rec10.pdf b/www/teaching/discrete20/rec10.pdf Binary files differnew file mode 100644 index 0000000..cd649a2 --- /dev/null +++ b/www/teaching/discrete20/rec10.pdf diff --git a/www/teaching/discrete20/rec11.pdf b/www/teaching/discrete20/rec11.pdf Binary files differnew file mode 100644 index 0000000..8a4b99f --- /dev/null +++ b/www/teaching/discrete20/rec11.pdf diff --git a/www/teaching/discrete20/rec12.pdf b/www/teaching/discrete20/rec12.pdf Binary files differnew file mode 100644 index 0000000..f54f3d2 --- /dev/null +++ b/www/teaching/discrete20/rec12.pdf diff --git a/www/teaching/discrete20/rec2.pdf b/www/teaching/discrete20/rec2.pdf Binary files differnew file mode 100644 index 0000000..b96fae3 --- /dev/null +++ b/www/teaching/discrete20/rec2.pdf diff --git a/www/teaching/discrete20/rec4.pdf b/www/teaching/discrete20/rec4.pdf Binary files differnew file mode 100644 index 0000000..de2eba8 --- /dev/null +++ b/www/teaching/discrete20/rec4.pdf diff --git a/www/teaching/discrete20/rec5.pdf b/www/teaching/discrete20/rec5.pdf Binary files differnew file mode 100644 index 0000000..eee55aa --- /dev/null +++ b/www/teaching/discrete20/rec5.pdf diff --git a/www/teaching/discrete20/rec6.pdf b/www/teaching/discrete20/rec6.pdf Binary files differnew file mode 100644 index 0000000..d124151 --- /dev/null +++ b/www/teaching/discrete20/rec6.pdf diff --git a/www/teaching/discrete20/rec7.pdf b/www/teaching/discrete20/rec7.pdf Binary files differnew file mode 100644 index 0000000..408249b --- /dev/null +++ b/www/teaching/discrete20/rec7.pdf diff --git a/www/teaching/discrete20/rec8.pdf b/www/teaching/discrete20/rec8.pdf Binary files differnew file mode 100644 index 0000000..4ad894a --- /dev/null +++ b/www/teaching/discrete20/rec8.pdf diff --git a/www/teaching/discrete20/rec9.pdf b/www/teaching/discrete20/rec9.pdf Binary files differnew file mode 100644 index 0000000..651b04a --- /dev/null +++ b/www/teaching/discrete20/rec9.pdf diff --git a/www/teaching/discrete2016/disc_rec_1.pdf b/www/teaching/discrete2016/disc_rec_1.pdf Binary files differnew file mode 100644 index 0000000..b24d97c --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_1.pdf diff --git a/www/teaching/discrete2016/disc_rec_10.pdf b/www/teaching/discrete2016/disc_rec_10.pdf Binary files differnew file mode 100644 index 0000000..3782021 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_10.pdf diff --git a/www/teaching/discrete2016/disc_rec_11.pdf b/www/teaching/discrete2016/disc_rec_11.pdf Binary files differnew file mode 100644 index 0000000..b1ee3e7 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_11.pdf diff --git a/www/teaching/discrete2016/disc_rec_13.pdf b/www/teaching/discrete2016/disc_rec_13.pdf Binary files differnew file mode 100644 index 0000000..e6209b6 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_13.pdf diff --git a/www/teaching/discrete2016/disc_rec_14.pdf b/www/teaching/discrete2016/disc_rec_14.pdf Binary files differnew file mode 100644 index 0000000..3ab5dc6 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_14.pdf diff --git a/www/teaching/discrete2016/disc_rec_2.pdf b/www/teaching/discrete2016/disc_rec_2.pdf Binary files differnew file mode 100644 index 0000000..59bf43a --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_2.pdf diff --git a/www/teaching/discrete2016/disc_rec_3.pdf b/www/teaching/discrete2016/disc_rec_3.pdf Binary files differnew file mode 100644 index 0000000..bd54977 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_3.pdf diff --git a/www/teaching/discrete2016/disc_rec_4.pdf b/www/teaching/discrete2016/disc_rec_4.pdf Binary files differnew file mode 100644 index 0000000..a97b8b2 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_4.pdf diff --git a/www/teaching/discrete2016/disc_rec_6.pdf b/www/teaching/discrete2016/disc_rec_6.pdf Binary files differnew file mode 100644 index 0000000..5d7ee77 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_6.pdf diff --git a/www/teaching/discrete2016/disc_rec_7.pdf b/www/teaching/discrete2016/disc_rec_7.pdf Binary files differnew file mode 100644 index 0000000..7e29ce8 --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_7.pdf diff --git a/www/teaching/discrete2016/disc_rec_8.pdf b/www/teaching/discrete2016/disc_rec_8.pdf Binary files differnew file mode 100644 index 0000000..8e40e8a --- /dev/null +++ b/www/teaching/discrete2016/disc_rec_8.pdf diff --git a/www/teaching/discrete2016/index.html b/www/teaching/discrete2016/index.html new file mode 100644 index 0000000..2087c8f --- /dev/null +++ b/www/teaching/discrete2016/index.html @@ -0,0 +1,47 @@ +--- +title: 21-228 (spring 2016) +title_short: Discrete Math + +--- + +<h1>21-228: Discrete Mathematics</h1> +<h4><a href="http://www.math.cmu.edu/~tbohman/21-228/discrete.html">Official Course Webpage</a></h4> +<dl> + <dt>Lecture</dt> + <dd>MWF 11:30-12:20</dd> + <dt>Recitation for §A</dt> + <dd>T 8:30-9:20</dd> + <dt>Recitation for §B</dt> + <dd>T 9:30-10:20</dd> + <dt>Tom Bohman's office hours</dt> + <dd>W 1:30-3:00</dd> + <dt>My office hours</dt> + <dd>Th 1:00-3:00</dd> +</dl> +<br /> +<hr /> + +<h2>Recitation notes</h2> +<p>Please let me know if I have made any mistakes in writing these up.</p> +<ul> + <li><a href="disc_rec_1.pdf">Recitation 1 – 01/12/16</a></li> + <li><a href="disc_rec_2.pdf">Recitation 2 – 01/19/16</a></li> + <li><a href="disc_rec_3.pdf">Recitation 3 – 01/26/16</a></li> + <li><a href="disc_rec_4.pdf">Recitation 4 – 02/02/16</a></li> + <li><a href="http://www.math.cmu.edu/~tbohman/21-228/review1.pdf">Recitation 5 – 02/09/16</a> (review day)</li> + <li><a href="disc_rec_6.pdf">Recitation 6 – 02/16/16</a></li> + <li><a href="disc_rec_7.pdf">Recitation 7 – 02/23/16</a></li> + <li><a href="disc_rec_8.pdf">Recitation 8 – 03/01/16</a></li> + <li><a href="http://www.math.cmu.edu/~tbohman/21-228/review2.pdf">Recitation 9 – 03/15/16</a> (review day)</li> + <li><a href="disc_rec_10.pdf">Recitation 10 – 03/22/16</a></li> + <li><a href="disc_rec_11.pdf">Recitation 11 – 03/29/16</a></li> + <li><a href="http://www.math.cmu.edu/~tbohman/21-228/review3.pdf">Recitation 12 – 04/05/16</a> (review day)</li> + <li><a href="disc_rec_13.pdf">Recitation 13 – 04/12/16</a></li> + <li><a href="disc_rec_14.pdf">Recitation 14 – 04/19/16</a></li> + +</ul> +<br /> +<hr /> + +<p>For more information on the "matching method" for doing inclusion-exclusion, see the following resource, which refers to this method as "DIE." <br /> + <a href="https://www.math.hmc.edu/~benjamin/papers/DIE.pdf">An alternate approach to alternating sums: A method to DIE for.</a></p> diff --git a/www/teaching/graphs2022/.htaccess b/www/teaching/graphs2022/.htaccess new file mode 100644 index 0000000..722a33b --- /dev/null +++ b/www/teaching/graphs2022/.htaccess @@ -0,0 +1,10 @@ +AuthUserFile /var/www/htpass/graphs2022/solutions +AuthName "Homework Solutions" +AuthType Basic +<Files ".htaccess"> + order allow,deny + deny from all +</Files> +<FilesMatch "sol.*\.pdf$"> + require user graphs +</FilesMatch> diff --git a/www/teaching/graphs2022/_notation.html b/www/teaching/graphs2022/_notation.html new file mode 100644 index 0000000..01f7e2a --- /dev/null +++ b/www/teaching/graphs2022/_notation.html @@ -0,0 +1,180 @@ +<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/graphs2022/dilworth.pdf b/www/teaching/graphs2022/dilworth.pdf Binary files differnew file mode 100644 index 0000000..2683488 --- /dev/null +++ b/www/teaching/graphs2022/dilworth.pdf diff --git a/www/teaching/graphs2022/ds1.pdf b/www/teaching/graphs2022/ds1.pdf Binary files differnew file mode 100644 index 0000000..1180fc1 --- /dev/null +++ b/www/teaching/graphs2022/ds1.pdf diff --git a/www/teaching/graphs2022/ds2.pdf b/www/teaching/graphs2022/ds2.pdf Binary files differnew file mode 100644 index 0000000..10bcc75 --- /dev/null +++ b/www/teaching/graphs2022/ds2.pdf diff --git a/www/teaching/graphs2022/ds3.pdf b/www/teaching/graphs2022/ds3.pdf Binary files differnew file mode 100644 index 0000000..3955084 --- /dev/null +++ b/www/teaching/graphs2022/ds3.pdf diff --git a/www/teaching/graphs2022/ds4.pdf b/www/teaching/graphs2022/ds4.pdf Binary files differnew file mode 100644 index 0000000..bc1fd62 --- /dev/null +++ b/www/teaching/graphs2022/ds4.pdf diff --git a/www/teaching/graphs2022/ds5.pdf b/www/teaching/graphs2022/ds5.pdf Binary files differnew file mode 100644 index 0000000..2f2afc6 --- /dev/null +++ b/www/teaching/graphs2022/ds5.pdf diff --git a/www/teaching/graphs2022/ds6.pdf b/www/teaching/graphs2022/ds6.pdf Binary files differnew file mode 100644 index 0000000..189b080 --- /dev/null +++ b/www/teaching/graphs2022/ds6.pdf diff --git a/www/teaching/graphs2022/dyck.pdf b/www/teaching/graphs2022/dyck.pdf Binary files differnew file mode 100644 index 0000000..71cbd1e --- /dev/null +++ b/www/teaching/graphs2022/dyck.pdf diff --git a/www/teaching/graphs2022/extra_01-18.pdf b/www/teaching/graphs2022/extra_01-18.pdf Binary files differnew file mode 100644 index 0000000..184cdc6 --- /dev/null +++ b/www/teaching/graphs2022/extra_01-18.pdf diff --git a/www/teaching/graphs2022/extra_01-20.pdf b/www/teaching/graphs2022/extra_01-20.pdf Binary files differnew file mode 100644 index 0000000..f35dd5a --- /dev/null +++ b/www/teaching/graphs2022/extra_01-20.pdf diff --git a/www/teaching/graphs2022/extra_01-25.pdf b/www/teaching/graphs2022/extra_01-25.pdf Binary files differnew file mode 100644 index 0000000..13935d8 --- /dev/null +++ b/www/teaching/graphs2022/extra_01-25.pdf diff --git a/www/teaching/graphs2022/extra_01-27.pdf b/www/teaching/graphs2022/extra_01-27.pdf Binary files differnew file mode 100644 index 0000000..04a6a6d --- /dev/null +++ b/www/teaching/graphs2022/extra_01-27.pdf diff --git a/www/teaching/graphs2022/extra_02-01.pdf b/www/teaching/graphs2022/extra_02-01.pdf Binary files differnew file mode 100644 index 0000000..498d20f --- /dev/null +++ b/www/teaching/graphs2022/extra_02-01.pdf diff --git a/www/teaching/graphs2022/extra_02-08.pdf b/www/teaching/graphs2022/extra_02-08.pdf Binary files differnew file mode 100644 index 0000000..b689f2c --- /dev/null +++ b/www/teaching/graphs2022/extra_02-08.pdf diff --git a/www/teaching/graphs2022/extra_02-10.pdf b/www/teaching/graphs2022/extra_02-10.pdf Binary files differnew file mode 100644 index 0000000..f087b4b --- /dev/null +++ b/www/teaching/graphs2022/extra_02-10.pdf diff --git a/www/teaching/graphs2022/extra_02-24.pdf b/www/teaching/graphs2022/extra_02-24.pdf Binary files differnew file mode 100644 index 0000000..74d8c0b --- /dev/null +++ b/www/teaching/graphs2022/extra_02-24.pdf diff --git a/www/teaching/graphs2022/extra_03-01.pdf b/www/teaching/graphs2022/extra_03-01.pdf Binary files differnew file mode 100644 index 0000000..2877516 --- /dev/null +++ b/www/teaching/graphs2022/extra_03-01.pdf diff --git a/www/teaching/graphs2022/extra_03-03.pdf b/www/teaching/graphs2022/extra_03-03.pdf Binary files differnew file mode 100644 index 0000000..c6f8000 --- /dev/null +++ b/www/teaching/graphs2022/extra_03-03.pdf diff --git a/www/teaching/graphs2022/extra_03-22.pdf b/www/teaching/graphs2022/extra_03-22.pdf Binary files differnew file mode 100644 index 0000000..63ad3a0 --- /dev/null +++ b/www/teaching/graphs2022/extra_03-22.pdf diff --git a/www/teaching/graphs2022/extra_03-29.pdf b/www/teaching/graphs2022/extra_03-29.pdf Binary files differnew file mode 100644 index 0000000..d7ce789 --- /dev/null +++ b/www/teaching/graphs2022/extra_03-29.pdf diff --git a/www/teaching/graphs2022/extra_03-31.pdf b/www/teaching/graphs2022/extra_03-31.pdf Binary files differnew file mode 100644 index 0000000..1f7aeb3 --- /dev/null +++ b/www/teaching/graphs2022/extra_03-31.pdf diff --git a/www/teaching/graphs2022/extra_04-05.pdf b/www/teaching/graphs2022/extra_04-05.pdf Binary files differnew file mode 100644 index 0000000..28a35cc --- /dev/null +++ b/www/teaching/graphs2022/extra_04-05.pdf diff --git a/www/teaching/graphs2022/extra_04-07.pdf b/www/teaching/graphs2022/extra_04-07.pdf Binary files differnew file mode 100644 index 0000000..bfb08ea --- /dev/null +++ b/www/teaching/graphs2022/extra_04-07.pdf diff --git a/www/teaching/graphs2022/extra_04-12.pdf b/www/teaching/graphs2022/extra_04-12.pdf Binary files differnew file mode 100644 index 0000000..4624e16 --- /dev/null +++ b/www/teaching/graphs2022/extra_04-12.pdf diff --git a/www/teaching/graphs2022/extra_04-14.pdf b/www/teaching/graphs2022/extra_04-14.pdf Binary files differnew file mode 100644 index 0000000..47072d7 --- /dev/null +++ b/www/teaching/graphs2022/extra_04-14.pdf diff --git a/www/teaching/graphs2022/extra_04-19.pdf b/www/teaching/graphs2022/extra_04-19.pdf Binary files differnew file mode 100644 index 0000000..23b78b0 --- /dev/null +++ b/www/teaching/graphs2022/extra_04-19.pdf diff --git a/www/teaching/graphs2022/extra_04-26.pdf b/www/teaching/graphs2022/extra_04-26.pdf Binary files differnew file mode 100644 index 0000000..dfb0e2b --- /dev/null +++ b/www/teaching/graphs2022/extra_04-26.pdf diff --git a/www/teaching/graphs2022/extra_04-28.pdf b/www/teaching/graphs2022/extra_04-28.pdf Binary files differnew file mode 100644 index 0000000..ba0ce2e --- /dev/null +++ b/www/teaching/graphs2022/extra_04-28.pdf diff --git a/www/teaching/graphs2022/extra_05-03.pdf b/www/teaching/graphs2022/extra_05-03.pdf Binary files differnew file mode 100644 index 0000000..6fe7d53 --- /dev/null +++ b/www/teaching/graphs2022/extra_05-03.pdf diff --git a/www/teaching/graphs2022/fun.pdf b/www/teaching/graphs2022/fun.pdf Binary files differnew file mode 100644 index 0000000..a9a34ec --- /dev/null +++ b/www/teaching/graphs2022/fun.pdf diff --git a/www/teaching/graphs2022/hw1.pdf b/www/teaching/graphs2022/hw1.pdf Binary files differnew file mode 100644 index 0000000..dfea1fb --- /dev/null +++ b/www/teaching/graphs2022/hw1.pdf diff --git a/www/teaching/graphs2022/hw1.tex b/www/teaching/graphs2022/hw1.tex new file mode 100644 index 0000000..1f0b532 --- /dev/null +++ b/www/teaching/graphs2022/hw1.tex @@ -0,0 +1,126 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#1} +\def\assignlink{hw1.tex} +\def\due{Jan 25} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\noindent\textbf{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[2 pts] + Let $S$ be a finite set of integers and let $G$ be the graph on vertex set $S$ where for any $x,y\in S$, $xy\in E(G)$ if and only if $x+y$ is odd. + \begin{enumerate} + \item Prove that $G$ is a bipartite graph for any such $S$. + \item If $S=[100]$, what is $\abs{E(G)}$? Justify your answer. + \end{enumerate} +\end{problem} + + +\begin{problem}[2 pts] + Suppose that $(u=v_0,v_1,\dots,v_k=v)$ is a $u$-$v$ geodesic. + Prove that $d(u,v_i)=i$ for all $i\in\{0,\dots,k\}$. +\end{problem} + + +\begin{problem}[2 pts]\label{abpath} + Let $G$ be a graph. + For two non-empty subsets $A,B\subseteq V(G)$, an $A$-$B$ path is a path in $G$ which connects some vertex of $A$ to some vertex of $B$. + Prove that if $P$ is a minim\textbf{al} $A$-$B$ path, then $P$ contains exactly one vertex from $A$ and contains exactly one vertex from $B$. +\end{problem} + + +\begin{problem}[2 pts] + Let $G$ be a connected graph. + Prove that any two maxim\textbf{um} paths in $G$ must share some vertex. +\end{problem} + + +\begin{problem}[2 pts] + Prove that a graph $G$ is bipartite if and only if every subgraph $H$ of $G$ has an independent set consisting of at least half of $V(H)$. + (recall that an independent set is a set of vertices which induce no edges) +\end{problem} + + +\end{document} diff --git a/www/teaching/graphs2022/hw10.pdf b/www/teaching/graphs2022/hw10.pdf Binary files differnew file mode 100644 index 0000000..3655b55 --- /dev/null +++ b/www/teaching/graphs2022/hw10.pdf diff --git a/www/teaching/graphs2022/hw10.tex b/www/teaching/graphs2022/hw10.tex new file mode 100644 index 0000000..abb54fc --- /dev/null +++ b/www/teaching/graphs2022/hw10.tex @@ -0,0 +1,193 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#10} +\def\assignlink{hw10.tex} +\def\due{Apr 12} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} +\DeclareMathOperator{\disc}{disc} +\DeclareMathOperator{\comp}{comp} +\DeclareMathOperator{\defect}{defect} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[2pts] + Let $G$ be a graph on $n\geq 2$ vertices with $\delta(G)\geq n/2$. + Show that: + \begin{enumerate} + \item If $n$ is even, then $G$ has a perfect matching. + \item If $n$ is odd, then $G-v$ has a perfect matching for every $v\in V(G)$. + \end{enumerate} +\end{problem} + + +\begin{problem}[2pts] + Let $G$ be a $k$-regular bipartite graph. + Prove that we can partition the edges of $G$ into $k$ perfect matchings. + That is, show that we can can partition $E(G)=M_1\sqcup\dots\sqcup M_k$ where each $M_i$ is a perfect matching in $G$. +\end{problem} + + +\begin{problem}[2pts]\label{harmonic} + Let $G$ be a bipartite graph with parts $A,B$. + Prove that if + \[ + \sum_{a\in A}{1\over\deg a}\leq 1, + \] + then $G$ contains a matching which saturates $A$. + Here, we employ the convention that ${1\over 0}=+\infty$. + + Hint: Recall the following two ``tricks'' used in class for a somewhat similar problem: + \begin{itemize} + \item Silly sizes: If $X$ is a non-empty finite set, then $\abs X=\sum_{x\in X}1$ and $1=\sum_{x\in X}{1\over\abs X}$. + \item Switching the order of summation: Fix finite sets $X,Y$ and suppose that $\Omega\subseteq X\times Y$. + For any function $f\colon X\times Y\to\R$, + \[ + \sum_{(x,y)\in\Omega}f(x,y)=\sum_{x\in X}\sum_{\substack{y\in Y:\\(x,y)\in\Omega}}f(x,y)=\sum_{y\in Y}\sum_{\substack{x\in X:\\(x,y)\in\Omega}}f(x,y). + \] + \end{itemize} +\end{problem} + + +\begin{problem}[2pts] + Fix any non-negative integers $n,k$ such that $k\leq(n-1)/2$. + Prove that there exists an injection + \[ + f\colon{[n]\choose k}\to{[n]\choose k+1} + \] + with the property that $X\subseteq f(X)$ for all $X\in{[n]\choose k}$. + + Note: you do not need to actually define the injection; it is enough to simply show that it exists. +\end{problem} + + +\begin{problem}[2pts] + Let $G$ be a bipartite graph with parts $A,B$ wherein no vertex of $A$ is isolated. + Show that if all vertices in $A$ have distinct degrees, then $G$ contains a matching which saturates $A$. + + Hint: If $S\subseteq[n]$ is non-empty, how do $\abs S$ and $\max S$ (the largest element in $S$) compare? +\end{problem} + + + +\begin{problem}[1 bonus point] + Fix positive integers $m,n$ and let $X$ be a set of size $mn$. + Also, fix any two partitions $X=A_1\sqcup\dots\sqcup A_n$ and $X=B_1\sqcup\dots\sqcup B_n$ where $\abs{A_i}=\abs{B_i}=m$ for all $i\in[n]$. + Prove that there exists a bijection $\pi\colon[n]\to[n]$ (i.e.\ a permutation on $[n]$) such that $A_i\cap B_{\pi(i)}\neq\varnothing$ for all $i\in[n]$. + + This problem will be graded all-or-nothing. + + (Also, I won't lie to you: notation gets really annoying here; as long as your notation is well explained, you'll be fine, even if your notation is somewhat ambiguous.) +\end{problem} + + +\begin{problem}[2 bonus points] + Sportsball is a game played between two teams that cannot end in a tie, so one of these two teams wins the game and the other loses, no matter what. + We have a sportsball league with $2n$ teams for some integer $n\geq 1$. + Over a season of $2n-1$ days, every team plays every other team at most once. + Furthermore, each team plays at most one game per day. + + We have $2n-1$ trophies to hand out, one for each day of the season. + Reasonably, a trophy for a particular day must go to one of the winning teams on that day. + We seek to hand out as many trophies as possible so that each team gets at most one trophy. + We hand out the trophies at the end of the season, so we can take into account the full results of the season before making our decision. + + Let $T$ be the set of all teams. + For each team $t\in T$, let $p(t)\subseteq T\setminus\{t\}$ denote the set of teams that team $t$ played over the course of the season. + Prove that we can hand out at least + \[ + \min_{R\subsetneq T}\ \max_{t\in T\setminus R}\ \abs{R\cup p(t)} + \] + of the trophies.\footnote{There are instances in which strictly more of the trophies can be handed out. For example, if at most one game is played per day and each team plays exactly once, then we can hand out $n$ trophies, yet the stated expression evaluates to $1$. I'd be interested to know if you can derive a better lower bound without taking into account the actual results of any game. I'm more than happy to dish out even more bonus points for such a result, though send any such argument to me separately from your homework.} + \vskip5pt + + This problem will be essentially graded all-or-nothing, except you can get \textbf{one of the two bonus points for proving the following special case}: + + If each team plays every other team \emph{exactly} once over the course of the season (i.e.\ $p(t)=T\setminus\{t\}$ for all $t\in T$), then we can hand out all $2n-1$ trophies. +\end{problem} + + + +\end{document} diff --git a/www/teaching/graphs2022/hw11.pdf b/www/teaching/graphs2022/hw11.pdf Binary files differnew file mode 100644 index 0000000..1b0be88 --- /dev/null +++ b/www/teaching/graphs2022/hw11.pdf diff --git a/www/teaching/graphs2022/hw11.tex b/www/teaching/graphs2022/hw11.tex new file mode 100644 index 0000000..b18793b --- /dev/null +++ b/www/teaching/graphs2022/hw11.tex @@ -0,0 +1,162 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#11} +\def\assignlink{hw11.tex} +\def\due{Apr 19} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} +\DeclareMathOperator{\disc}{disc} +\DeclareMathOperator{\comp}{comp} +\DeclareMathOperator{\defect}{defect} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[2pts] + Let $G$ be any graph. + Prove that + \[ + \abs{E(G)}\geq{\chi(G)\choose 2}. + \] +\end{problem} + + + + +\begin{problem}[1pt] + Generalize Theorem 1 from 04-07: + + Let $G=(V,E)$ be any graph and consider coloring the edges of $G$ red and blue (formally, we have a function $f\colon E\to\{\text{red},\text{blue}\}$). + Let $G_r$ be the graph formed by the red edges and let $G_b$ be the graph formed by the blue edges (formally, $G_r=\bigl(V,f^{-1}(\text{red})\bigr)$ and $G_b=\bigl(V,f^{-1}(\text{blue})\bigr)$). + Prove that + \[ + \chi(G_r)\cdot\chi(G_b)\geq\chi(G). + \] +\end{problem} + + + +\begin{problem}[1pt] + For every pair of positive integers $m,n$, construct a graph $G$ with the following properties: + \begin{itemize} + \item $G$ has $m\cdot n$ many vertices, and + \item $\chi(G)=m$, and + \item $\chi(\wbar G)=n$. + \end{itemize} +\end{problem} + + + +\begin{problem}[2pts] + Prove that $G$ is $3$-critical if and only if $G\cong C_{2n+1}$ for some positive integer $n$. +\end{problem} + + +\begin{problem}[2pts]\label{neighborchi} + Fix any integer $k\geq 1$. + Prove that if $G$ is an $n$-vertex graph wherein + \[ + \chi\bigl(G[N(v)]\bigr)\leq k,\quad\text{for every }v\in V(G), + \] + then $\chi(G)\leq\sqrt{2kn}$. + + (Hint: Take motivation from our proof that $\chi(G)\leq\sqrt{2n}$ if $G$ is triangle-free. Be warned, though, there are a couple steps which require more care.) + + (Hint: If $0\leq x\leq y$, then $x\leq\sqrt{xy}$.) +\end{problem} + + +\begin{problem}[2pts] + For graphs $G,H$, the graph $G$ is said to be $H$-free if $G$ does not contain a copy of $H$. + + Fix any integer $k\geq 3$. + Prove that if $G$ is a $C_k$-free graph on $n$ vertices, then $\chi(G)\leq\sqrt{2(k-2)n}$. + + (Hint: Problem~\ref{neighborchi}) +\end{problem} + + + + +\end{document} diff --git a/www/teaching/graphs2022/hw12.pdf b/www/teaching/graphs2022/hw12.pdf Binary files differnew file mode 100644 index 0000000..d4be075 --- /dev/null +++ b/www/teaching/graphs2022/hw12.pdf diff --git a/www/teaching/graphs2022/hw12.tex b/www/teaching/graphs2022/hw12.tex new file mode 100644 index 0000000..9a5abf9 --- /dev/null +++ b/www/teaching/graphs2022/hw12.tex @@ -0,0 +1,140 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#12} +\def\assignlink{hw12.tex} +\def\due{Apr 26} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} +\DeclareMathOperator{\disc}{disc} +\DeclareMathOperator{\comp}{comp} +\DeclareMathOperator{\len}{len} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + + +\begin{problem}[2 + 2 + 2 pts] + \phantom{hi} + \begin{enumerate} + \item Let $G$ be a bipartite graph with parts $A,B$ where $\abs A=\abs B=n\geq 1$. + Prove that if $\abs{E(G)}>n(n-1)$, then $G$ has a perfect matching. + + (It may be easier to rely on K\H{o}nig here instead of on Hall, but it's up to you. You could even just induct on $n$.) + + \item Let $G$ be a bipartite graph with parts $A,B$ and fix an integer $n\geq 1$. + Let $A=A_1\sqcup\dots\sqcup A_n$ and $B=B_1\sqcup\dots\sqcup B_n$ be any partitions (some of the $A_i$'s or $B_j$'s may be empty). + Note that $\abs A$ and $\abs B$ have nothing to do with $n$; $n$ is just the number of pieces in each partition. + + Prove that if $\abs{E(G)}<n$, then there is a bijection $\pi\colon[n]\to[n]$ such that $G$ has no edges between $A_i$ and $B_{\pi(i)}$ for each $i\in[n]$. + + You are free to use part 1 as a black-box even if you haven't proved it. + \item For each positive integer $t$, prove that if $G$ is a $t$-critical graph, then $\lambda(G)\geq t-1$. + + (Hint: Consult the notes from 03-01. Use part 2 to ``merge independent sets''.) + + You are free to use parts 1 and/or 2 as a black-box even if you haven't proved then. + + N.b.\ Vertex-connectivity is a very different story... + In particular, the obvious analogue for vertex-connectivity is false (in general). + The ``Moser spindle'' is a counter-example when $t=4$, and there are many, many others. + \end{enumerate} +\end{problem} + + +\begin{problem}[2pts] + Let $g\geq 2$ be an integer and let $G$ be a connected plane graph on $n$ vertices wherein every face is bounded by a cycle of $G$. + Prove that if $G$ has no cycles of length $g$ or smaller, then + \[ + \abs{E(G)}\leq {g+1\over g-1}(n-2). + \] +\end{problem} + + + +\begin{problem}[2pts] + Prove a special case of the $4$-color theorem: If $G$ is a planar, triangle-free graph, then $\chi(G)\leq 4$. +\end{problem} + + +\end{document} diff --git a/www/teaching/graphs2022/hw13.pdf b/www/teaching/graphs2022/hw13.pdf Binary files differnew file mode 100644 index 0000000..972b6fe --- /dev/null +++ b/www/teaching/graphs2022/hw13.pdf diff --git a/www/teaching/graphs2022/hw13.tex b/www/teaching/graphs2022/hw13.tex new file mode 100644 index 0000000..f254b2d --- /dev/null +++ b/www/teaching/graphs2022/hw13.tex @@ -0,0 +1,155 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#13} +\def\assignlink{hw13.tex} +\def\due{May 3} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} +\DeclareMathOperator{\disc}{disc} +\DeclareMathOperator{\comp}{comp} +\DeclareMathOperator{\len}{len} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[2pts] + The 3-color Ramsey number $R(m,n,p)$ is the smallest integer $N$ such that every 3-coloring of $E(K_N)$ (say with colors red, blue and green) contains either a red copy of $K_m$, a blue copy of $K_n$ or a green copy of $K_p$. + \vskip5pt + + Prove that $R(3,3,3)\leq 17$. + \vskip5pt + + N.b.\ It turns out that $R(3,3,3)=17$, but I'm not asking you to prove the lower bound. +\end{problem} + + +\begin{problem}[2pts] + Prove that $R(3,n)\leq n^2$ for every positive integer $n$. + + (Hint: It's probably best if you just think about $G$ vs $\wbar G$ instead of red,blue-colorings here.) + + (Hint: Review the \emph{silly} upper and lower bounds that we proved on chromatic numbers on 04-05.) +\end{problem} + + +\begin{problem}[2pts] + Consider coloring the numbers in $[17]$ red and blue, i.e.\ we have a function $f\colon[17]\to\{\text{red},\text{blue}\}$. + Prove that there exist $a\neq b\in[17]$ such that $f(a)=f(b)=f(a+b)$. + (Note that no integers outside of $[17]$ receive any color, so it must be the case that also $a+b\in[17]$ in order for this to happen.) + + (Hint: Create a red,blue-coloring of $E(K_{18})$ (thinking of $V(K_{18})=[18]$) based on the differences between the points.) + + (Hint: $(x-y)+(z-x)=z-y$.) + \vskip5pt + + \textbf{You can receive 1.25pts/2 if you prove a simplified version of the claim where you allow $a=b$.} (such a proof could completely ignore the hint if you so choose and can also be accomplished when $17$ replaced by $5$, but you don't have to) + \vskip5pt + + I'm not schur if 17 is the smallest integer for which the claim is true. + I'll hand out \textbf{1 bonus point} if you can determine (with proof) the smallest integer for which the claim is still true. +\end{problem} + + + +\begin{problem}[2 + 2 pts] + Let $n$ be a positive integer and set $N=3n-1$. + \begin{enumerate} + \item Prove that every red,blue-coloring of $E(K_N)$ contains a monochromatic matching with $n$ edges.\footnote{ + Fun fact (if you care). + Suppose that the red,blue-coloring of $E(K_N)$ was initially hidden from you and, one by one, you're allowed to ask about the color of whichever edges you desire. + How many edges do you have to ask about in order to actually find a monochromatic matching with $n$ edges? + Of course, you can find the matching by asking about about the color of all ${N\choose 2}$ edges thanks to this problem; however, you can do much, much better. + It turns out that you can actually get away with asking about only $N-1$ of the edges! + The general case (more than two colors) is still open, though, if you care to think about it :) + The relevant papers are \url{https://arxiv.org/abs/1904.00246} and \url{https://arxiv.org/abs/2010.04113}.} + + (Hint: Show that there exists an incident red- and blue-edge unless every edge gets the same color) + \item Construct a red,blue-coloring of $E(K_{N-1})$ which \emph{does not} contain a monochromatic matching with $n$ edges. + + (Hint: Break $V(K_{N-1})$ into two pieces, one of size $2n-1$ and the other of size $n-1$, and color the edges based on how they intersect these two pieces) + \end{enumerate} +\end{problem} + + +\end{document} diff --git a/www/teaching/graphs2022/hw2.pdf b/www/teaching/graphs2022/hw2.pdf Binary files differnew file mode 100644 index 0000000..b33ff75 --- /dev/null +++ b/www/teaching/graphs2022/hw2.pdf diff --git a/www/teaching/graphs2022/hw2.tex b/www/teaching/graphs2022/hw2.tex new file mode 100644 index 0000000..1032470 --- /dev/null +++ b/www/teaching/graphs2022/hw2.tex @@ -0,0 +1,134 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#2} +\def\assignlink{hw2.tex} +\def\due{Feb 1} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\noindent\textbf{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[1 pt] + Recall that a \emph{directed graph} (or digraph) is a pair $D=(V,E)$ where $V$ is a set and $E\subseteq V^2$. + For $u,v\in V$, a $u$-$v$ diwalk in $D$ is a sequence $(u=v_0,\dots,v_k=v)$ such that $(v_i,v_{i+1})\in E$ for all $i\in\{0,\dots,k-1\}$. + + Consider the relation $R$ on $V$ where $u\mathbin R v$ iff there is a $u$-$v$ diwalk. + Give an example of a digraph $D$ where $R$ is \textbf{not} an equivalence relation. + Justify your answer. + (Feel free to draw a picture of $D$) +\end{problem} + + +\begin{problem}[2 pts] + Let $G$ be a connected graph and consider a function $f\colon V(G)\to X$ where $X$ is some arbitrary set. + Prove that if $f$ is \emph{not} a constant function, then there is an edge $uv\in E(G)$ such that $f(u)\neq f(v)$. +\end{problem} + + + +\begin{problem}[2 pts] + Prove that every graph on at least two vertices has a pair of vertices with the same degree. +\end{problem} + + +\begin{problem}[2 pts] + Prove that if $G$ is a graph with $\delta(G)\geq 2$, then $G$ must contain a cycle. +\end{problem} + + +\begin{problem}[3 pts] + Let $G$ be a graph and let $A$ be an independent set of $G$. + Prove that + \[ + \sum_{v\in A}\deg v \leq\abs{E(G)} + \] + with equality if and only if $G$ is bipartite with parts $A$ and $V(G)\setminus A$. + + \noindent (Especially in this problem, be sure to carefully justify all steps in your argument) +\end{problem} + + + + +\end{document} diff --git a/www/teaching/graphs2022/hw3.pdf b/www/teaching/graphs2022/hw3.pdf Binary files differnew file mode 100644 index 0000000..f2f1a63 --- /dev/null +++ b/www/teaching/graphs2022/hw3.pdf diff --git a/www/teaching/graphs2022/hw3.tex b/www/teaching/graphs2022/hw3.tex new file mode 100644 index 0000000..3f83d09 --- /dev/null +++ b/www/teaching/graphs2022/hw3.tex @@ -0,0 +1,130 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#3} +\def\assignlink{hw3.tex} +\def\due{Feb 8} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + + +\begin{problem}[2 pts] + Let $G$ be a graph on $n$ vertices. + Prove that if $\Delta(G)+\delta(G)\geq n-1$ then $G$ is connected. +\end{problem} + + + +\begin{problem}[2 pts] + Let $G$ be a graph with the property that $\deg u+\deg v\equiv 1\pmod 2$ for every $uv\in E(G)$. + Prove that $\abs{E(G)}$ is even. +\end{problem} + + +\begin{problem}[2 pts] + Let $G$ be a connected graph and suppose that $f\colon V(G)\to\Z$ is a function with the property that $f(u)+f(v)\equiv 0\pmod 3$ for every $uv\in E(G)$. + Prove that if $G$ is \emph{not} bipartite, then $f(v)\equiv 0\pmod 3$ for every $v\in V(G)$. +\end{problem} + + +\begin{problem}[2 pts] + Let $G$ be a graph on $n$ vertices. + Prove that $\delta(G)+\delta(\wbar G)\leq n-1$ with equality if and only if $G$ is regular. +\end{problem} + + +\begin{problem}[1 + 1 pts] + Determine whether or not the following sequences are graphical. + If the sequence is graphical, draw a picture of a graph with that degree sequences. + If the sequence is not graphical, prove this. + \begin{enumerate} + \item $5,3,3,3,3,2,2,2,1$ + \item $6,5,5,4,3,2,1$ + \end{enumerate} +\end{problem} + + + +\end{document} diff --git a/www/teaching/graphs2022/hw4.pdf b/www/teaching/graphs2022/hw4.pdf Binary files differnew file mode 100644 index 0000000..dab44ac --- /dev/null +++ b/www/teaching/graphs2022/hw4.pdf diff --git a/www/teaching/graphs2022/hw4.tex b/www/teaching/graphs2022/hw4.tex new file mode 100644 index 0000000..e678650 --- /dev/null +++ b/www/teaching/graphs2022/hw4.tex @@ -0,0 +1,129 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#4} +\def\assignlink{hw4.tex} +\def\due{Feb 8} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + + +\begin{problem}[2 pts] + Let $G$ and $H$ be graphs. + A \emph{graph homomorphism} from $G$ to $H$ is a function $f\colon V(G)\to V(H)$ such that $\{f(u),f(v)\}\in E(H)$ whenever $\{u,v\}\in E(G)$.\footnote{Note that a graph homomorphism does \emph{not} need to be a bijection and that it could be the case that $\{f(u),f(v)\}\in E(H)$ even though $\{u,v\}\notin E(G)$.} + + Prove that a graph $G$ is bipartite if and only if there is a graph homomorphism from $G$ to $K_2$. +\end{problem} + + +\begin{problem}[2 pts] + A graph $G$ is called \emph{self-complementary} if $G\cong\wbar G$. + For example, $P_4$ and $C_5$ are self-complementary. + + Prove that if $G$ is a self-complementary graph on $n$ vertices, then $n$ is congruent to either $0$ or $1$ modulo $4$. +\end{problem} + + +\begin{problem}[2 pts] + Prove that a graph $G$ on $n$ vertices with $\delta(G)\geq 3$ must contain a cycle of length at most $\lfloor n/2\rfloor+1$. +\end{problem} + + +\begin{problem}[2 pts]\label{paths} + Let $T$ be a tree on $n$ vertices with $\Delta(T)\leq 2$. + Prove that $T\cong P_n$. +\end{problem} + + + +\begin{problem}[2 pts] + Determine (with proof) all trees $T$ (up to isomorphism) on $n\geq 2$ vertices such that $\wbar T$ is also a tree. + (Note: we do not require that $T\cong\wbar T$.) +\end{problem} + + + +\end{document} diff --git a/www/teaching/graphs2022/hw5.pdf b/www/teaching/graphs2022/hw5.pdf Binary files differnew file mode 100644 index 0000000..b9f5bb6 --- /dev/null +++ b/www/teaching/graphs2022/hw5.pdf diff --git a/www/teaching/graphs2022/hw5.tex b/www/teaching/graphs2022/hw5.tex new file mode 100644 index 0000000..067511e --- /dev/null +++ b/www/teaching/graphs2022/hw5.tex @@ -0,0 +1,131 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#5} +\def\assignlink{hw5.tex} +\def\due{Feb 8} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + + +\begin{problem}[0.5 + 0.5 + 1 pts] + For a fixed integer $k\geq 3$, a graph $G$ is said to have property $\mcal C_k$ if every subgraph of $G$ with at least $k$ edges contains a cycle. + For a fixed integer $k\geq 4$, a graph $G$ is said to have property $\mcal E_k$ if every subgraph of $G$ with at least $k$ edges contains an even cycle. + \begin{enumerate} + \item For each $k\geq 3$, construct a graph $G$ which has property $\mcal C_k$ and has $\abs{E(G)}={k\choose 2}$. + \item For each $k\geq 4$, construct a graph $G$ which has property $\mcal E_k$ and has $\abs{E(G)}=\lceil k/2\rceil\lfloor k/2\rfloor$. + \item Prove that if $G$ is a connected graph with property $\mcal C_k$, then $\abs{E(G)}\leq{k\choose 2}$. + \end{enumerate} +\end{problem} + + +\begin{problem}[3 pts] + This problem expands on the observation that trees on at least two vertices have at least two leaves. + + Let $T$ be a tree on at least two vertices. + Let $\ell(T)$ denote the number of leaves of $T$ and define $D_{\geq 2}=\{v\in V(T):\deg v\geq 2\}$. + Prove that + \[ + \ell(T)=2+\sum_{v\in D_{\geq 2}}(\deg v-2) + \] +\end{problem} + + + +\begin{problem}[3 pts] + Fix an integer $n\geq 2$. + Prove that a sequence of integers $d_1,\dots,d_n$ is the degree sequence of some tree if and only if $d_i\geq 1$ for all $i\in[n]$ and $\sum_{i=1}^n d_i=2n-2$. +\end{problem} + + + +\begin{problem}[2 pts] + Let $G$ be a connected graph and let $w\colon E(G)\to\R$ be a weight function. + Show that if all weights are distinct (that is $w(e)\neq w(s)$ for all distinct $e,s\in E(G)$), then $G$ has a \emph{unique} minimum spanning tree. +\end{problem} + + +\end{document} diff --git a/www/teaching/graphs2022/hw6.pdf b/www/teaching/graphs2022/hw6.pdf Binary files differnew file mode 100644 index 0000000..3874514 --- /dev/null +++ b/www/teaching/graphs2022/hw6.pdf diff --git a/www/teaching/graphs2022/hw6.tex b/www/teaching/graphs2022/hw6.tex new file mode 100644 index 0000000..c787ccd --- /dev/null +++ b/www/teaching/graphs2022/hw6.tex @@ -0,0 +1,170 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#6} +\def\assignlink{hw6.tex} +\def\due{Mar 1} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[0.5 + 0.5 pts] + Determine the Pr\"ufer code of the following trees (using the standard ordering of the integers). + \begin{enumerate} + \item \phantom{hi} + \begin{center} + \begin{tikzpicture}[main/.style = {draw, circle}, scale = 1.5] + \node[main] (1) at (0,0) {1}; + \node[main] (2) at (-1,0) {2}; + \node[main] (3) at (2,0) {3}; + \node[main] (4) at (1,1) {4}; + \node[main] (5) at (1,-1) {5}; + \node[main] (6) at (0,-1) {6}; + \node[main] (7) at (1,0) {7}; + \node[main] (8) at (0,1) {8}; + \draw (2)--(1)--(7)--(3); + \draw (8)--(1)--(6); + \draw (4)--(7)--(5); + \end{tikzpicture} + \end{center} + \item \phantom{hi} + \begin{center} + \begin{tikzpicture}[main/.style = {draw, circle}, scale = 1.5] + \node[main] (1) at (0,0) {1}; + \node[main] (2) at (2,1) {2}; + \node[main] (3) at (1,1) {3}; + \node[main] (4) at (1,0) {4}; + \node[main] (5) at (4,0) {5}; + \node[main] (6) at (3,0) {6}; + \node[main] (7) at (4,1) {7}; + \node[main] (8) at (5,0) {8}; + \node[main] (9) at (2,0) {9}; + \draw (1)--(4)--(9)--(6)--(5)--(8); + \draw (3)--(2)--(9); + \draw (7)--(5); + \end{tikzpicture} + \end{center} + \end{enumerate} +\end{problem} + + +\begin{problem}[0.5 + 0.5 pts] + For the following sequences, draw a picture of the (labeled) tree which has that sequence as its Pr\"ufer code (using the standard ordering of the integers). + Your tree should have vertex-set $[n]$ for some integer $n$. + \begin{enumerate} + \item $(5,7,5,1,3,5,5)$ + \item $(4,4,1,2,1,2,3)$ + \end{enumerate} +\end{problem} + + +\begin{problem}[1 pts] + Determine (with proof) all trees $T$ (up to isomorphism) on $n\geq 2$ vertices whose Pr\"ufer code uses each element of $V(T)$ at most once (under any arbitrary ordering of $V(T)$). +\end{problem} + + +\begin{problem}[2 pts] + (HW5.3 revisited) + Fix an integer $n\geq 2$ and let $d_1,\dots,d_n$ be a sequence of positive integers with $\sum_{i=1}^nd_i=2n-2$. + Use Pr\"ufer codes to show that there is a tree with degree sequence $d_1,\dots,d_n$. +\end{problem} + + +\begin{problem}[2 pts] + For a graph $G$, define the relation $R$ on $V(G)$ by $u\mathbin R v$ if and only if $u=v$ or there is a cycle in $G$ containing both $u$ and $v$. + Find a graph $G$ wherein $R$ is \emph{not} an equivalence relation on $V(G)$. + (You are welcome to define $G$ via a picture, though, of course, you must still demonstrate that $R$ is not an equivalence relation on this $G$) +\end{problem} + + +\begin{problem}[3 pts] + For a graph $G$, define the relation $R$ on $E(G)$ by $e\mathbin R s$ if and only if $e=s$ or there is a cycle in $G$ containing both $e$ and $s$. + Prove that $R$ is an equivalence relation on $E(G)$. +\end{problem} + + + + +\end{document} diff --git a/www/teaching/graphs2022/hw7.pdf b/www/teaching/graphs2022/hw7.pdf Binary files differnew file mode 100644 index 0000000..271f38d --- /dev/null +++ b/www/teaching/graphs2022/hw7.pdf diff --git a/www/teaching/graphs2022/hw7.tex b/www/teaching/graphs2022/hw7.tex new file mode 100644 index 0000000..c4380ba --- /dev/null +++ b/www/teaching/graphs2022/hw7.tex @@ -0,0 +1,143 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#7} +\def\assignlink{hw7.tex} +\def\due{Mar 22} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[2pts] + For infinitely many integers $n$, construct a graph $G$ with the following properties: + \begin{itemize} + \item $G$ is connected and has $n$ vertices, and + \item $G$ is \emph{not} a tree, and + \item Every $v\in V(G)$ which is not a leaf of $G$ is a cut-vertex of $G$. + \end{itemize} + ``For infinitely many integers $n$...'' means the following: Pick your favorite infinite subset $A\subseteq\N$ and, for each $n\in A$, build the desired graph for that $n$. + For instance, maybe you pick $A$ to be the set of even naturals, or maybe you pick $A$ to be the set of integers of the form $2^k$, or maybe you pick $A$ to be the set of all primes larger than $100^{100^{100^{100}}}$, etc. + As long as $A$ is infinite, you're fine. +\end{problem} + + +\begin{problem}[1 + 1 pts]\label{spanning} + Let $G$ be a graph and suppose that $H$ is any spanning subgraph of $G$. + \begin{enumerate} + \item Prove that $\lambda(G)\geq\lambda(H)$. + \item Prove that $\kappa(G)\geq\kappa(H)$. + \end{enumerate} +\end{problem} + + + +\begin{problem}[1 + 2 pts]\label{delete_edge} + Let $G=(V,E)$ be a graph with at least one edge and fix any $e\in E$. + \begin{enumerate} + \item Prove that $\lambda(G)\geq\lambda(G-e)\geq\lambda(G)-1$. + \item Prove that $\kappa(G)\geq\kappa(G-e)\geq\kappa(G)-1$. + \end{enumerate} +\end{problem} + + +\begin{problem}[1 pts] + For each non-negative integer $k$, find an example of a graph $G$ with $\kappa(G)=\lambda(G)=1$, yet there is some vertex $v\in V(G)$ such that $\kappa(G-v)=\lambda(G-v)=k$. + + That is to say, the natural analogue of Problem~\ref{delete_edge} fails when deleting vertices instead of edges. +\end{problem} + + +\begin{problem}[2 pts] + Let $G$ be a graph. + The \emph{$k$th power of $G$} is the graph $G^k$ which has the same vertex-set as $G$ and $uv\in E(G^k)$ iff $d_G(u,v)\leq k$. + + Prove that if $G$ is a connected graph on at least $k+1$ vertices, then $G^k$ is $k$-connected. + + (You don't have to turn this is, but you should convince yourself that it's true: $G^k$ is a clique if and only if $\diam(G)\leq k$.) +\end{problem} + + + +\end{document} diff --git a/www/teaching/graphs2022/hw8.pdf b/www/teaching/graphs2022/hw8.pdf Binary files differnew file mode 100644 index 0000000..c946dd4 --- /dev/null +++ b/www/teaching/graphs2022/hw8.pdf diff --git a/www/teaching/graphs2022/hw8.tex b/www/teaching/graphs2022/hw8.tex new file mode 100644 index 0000000..c2243b4 --- /dev/null +++ b/www/teaching/graphs2022/hw8.tex @@ -0,0 +1,139 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#8} +\def\assignlink{hw8.tex} +\def\due{Mar 29} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} +\DeclareMathOperator{\disc}{disc} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +We say that a graph is \emph{even-regular} if every vertex has even degree, and we say that a graph is \emph{odd-regular} if every vertex has odd degree. + +\begin{problem}[2pts] + In the second week of class (01-27), we used the handshaking lemma to prove the following fact: + If $G$ is a connected even-regular graph, then $G$ has no bridges. + + Give an alternative proof of this fact using what we now know about Eulerian circuits. +\end{problem} + + +\begin{problem}[2 + 2 pts] + A digraph $D$ is said to be \emph{oriented} if $(u,v)\in E(D)\implies(v,u)\notin E(D)$, i.e.\ $D$ has no directed cycles of length $1$ or $2$. + + For a digraph $D$ with no loops, the \emph{underlying simple graph} of $D$ is the (simple) graph $G$ with $V(G)=V(D)$ and $uv\in E(G)$ if and only if $(u,v)\in E(D)$ or $(v,u)\in E(D)$. + In other words, the underlying simple graph is formed by simply forgetting about the directions of the edges. + + For a (simple) graph $G$, an \emph{orientation} of $G$ is an oriented digraph whose underlying simple graph is $G$. + In other words, an orientation of $G$ is formed by assigning a direction to each edge of $G$. + Note that a graph generally has many orientations. + \begin{enumerate} + \item Prove that if $G$ is a (simple) even-regular graph, then $G$ has an orientation wherein $\deg^+ v=\deg^- v$ for all vertices $v$. + \item Prove that if $G$ is any (simple) graph, then $G$ has an orientation wherein $\abs{\deg^+ v-\deg^- v}\leq 1$ for all vertices $v$. + + You are free use part 1 as a black-box even if you haven't proved it. + \end{enumerate} +\end{problem} + + +\begin{problem}[2 + 2 pts] + For graphs $G,H$, the \emph{Cartesian product} of $G$ and $H$ is the graph $G\mathbin\square H$ which has vertex set $V(G)\times V(H)$ and $\{(u_1,v_1),(u_2,v_2)\}\in E(G\mathbin\square H)$ if and only if either $u_1=u_2$ and $v_1v_2\in E(H)$ or $u_1u_2\in E(G)$ and $v_1=v_2$.\footnote{N.b.\ We like the notation $\square$ here since $K_2\mathbin\square K_2\cong C_4$, which looks like a $\square$. Note that your book uses $\times$ in place of $\square$; this is okay, but not desirable since generally $\times$ denotes a different graph product known as the categorical product, in which $K_2\times K_2\cong K_2\sqcup K_2$, which can be made to look like an $\times$.} + + Suppose that $G$ and $H$ are any graphs. + \begin{enumerate} + \item Prove that $G\mathbin\square H$ is connected if and only if both $G$ and $H$ are connected. + \item Prove that $G\mathbin\square H$ is Eulerian if and only if both $G$ and $H$ are connected and also: + \begin{enumerate} + \item Both $G$ and $H$ are even-regular, or + \item Both $G$ and $H$ are odd-regular. + \end{enumerate} + You are free to use part 1 as a black-box even if you haven't proved it. + \end{enumerate} +\end{problem} + + + +\end{document} diff --git a/www/teaching/graphs2022/hw9.pdf b/www/teaching/graphs2022/hw9.pdf Binary files differnew file mode 100644 index 0000000..bec538b --- /dev/null +++ b/www/teaching/graphs2022/hw9.pdf diff --git a/www/teaching/graphs2022/hw9.tex b/www/teaching/graphs2022/hw9.tex new file mode 100644 index 0000000..7429f34 --- /dev/null +++ b/www/teaching/graphs2022/hw9.tex @@ -0,0 +1,151 @@ +\documentclass[11pt]{article} +\usepackage[margin=1in]{geometry} +\usepackage{amsfonts,amsmath,amssymb,amsthm} + +\PassOptionsToPackage{obeyspaces}{url} +\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref} +\usepackage{tikz} + +\usepackage{enumitem} +\setlist{itemsep=0.5em} + +%% header definitions +\def\course{MATH 314} +\def\courselink{https://mathematicaster.org/teaching/graphs2022} +\def\assign{HW \#9} +\def\assignlink{hw9.tex} +\def\due{Apr 5} +\def\doctype{This homework is from} + +%% environments +% theorem style +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{claim}[theorem]{Claim} +\newtheorem{defn}[theorem]{Definition} + +% definition style +\theoremstyle{definition} +\newtheorem{problem}{Problem} + +% custom +\newenvironment{solution}{\paragraph{Solution.}}{\qed} + +%% custom commands +\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link +\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality +\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality +\newcommand*{\eps}{\varepsilon} % prettier epsilon +\newcommand*{\R}{\mathbb{R}} % real numbers +\newcommand*{\C}{\mathbb{C}} % complex numbers +\newcommand*{\Q}{\mathbb{Q}} % rational numbers +\newcommand*{\Z}{\mathbb{Z}} % integers +\newcommand*{\N}{\mathbb{N}} % natural numbers +\newcommand*{\F}{\mathbb{F}} % field +\newcommand*{\family}{\mathcal{F}} % family +\newcommand*{\GL}{\mathbf{GL}} % general linear group +\newcommand*{\what}[1]{\widehat{#1}} % wider hat +\newcommand*{\wbar}[1]{\overline{#1}} % wider bar +\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal +\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf +\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb + +% operators +\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability +\DeclareMathOperator*{\E}{\mathbb{E}} % expectation +\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance +\DeclareMathOperator*{\Span}{span} % span +\DeclareMathOperator{\tr}{tr} % trace +\DeclareMathOperator{\rank}{rank} % rank +\DeclareMathOperator{\supp}{supp} % support +\DeclareMathOperator{\diam}{diam} +\DeclareMathOperator{\Aut}{Aut} +\DeclareMathOperator{\disc}{disc} +\DeclareMathOperator{\comp}{comp} + + + +\begin{document} +\pagestyle{empty} + +\noindent +\begin{minipage}{.33\textwidth} + \flushleft {\bf \course} +\end{minipage} +\begin{minipage}{.33\textwidth} + \centering {\bf \assign} +\end{minipage} +\begin{minipage}{.33\textwidth} + \flushright {\bf \due} +\end{minipage} +\vskip3pt +\hrule\hrule\hrule +\vskip5pt + +\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}} +\vskip10pt + +\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof. +You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. +} + +\vskip20pt + +\begin{problem}[1 + 2 pts] + Fix any integer $n\geq 3$. + \begin{enumerate} + \item Construct an $n$-vertex graph $G$ with ${n-1\choose 2}+1$ many edges such that $G$ is \emph{not} Hamiltonian. + + (Note: You must construct such a graph for \emph{every} $n\geq 3$.) + \item Prove that if $G$ is an $n$-vertex graph with at least ${n-1\choose 2}+2$ many edges, then $G$ is Hamiltonian. + \end{enumerate} +\end{problem} + + +\begin{problem}[0.5 + 0.5 pts] + Recall that $K_{n_1,n_2,n_3}$ is the complete tripartite graph with parts of sizes $n_1,n_2,n_3$. + + Fix any positive integer $n$. + \begin{enumerate} + \item Prove that $K_{n,2n,3n}$ is Hamiltonian. + \item Prove that $K_{n,2n,3n+1}$ is not Hamiltonian. + \end{enumerate} +\end{problem} + + +\begin{problem}[2pts] + Let $G$ be a graph on $n\geq 4$ vertices with the property that $N(u)\cup N(v)\supseteq V(G)\setminus\{u,v\}$ for every $u\neq v\in V(G)$. + Prove that $G$ is Hamiltonian. + + (Hint: $\abs{A\cup B}=\abs A+\abs B-\abs{A\cap B}$ for finite sets $A,B$.) + + (Hint: The problem and first hint suggest attempting a proof similar to our proof of Bondy--Chv\'atal, i.e.\ extending a Hamiltonian path to a Hamiltonian cycle. While such a proof is possible, it's more difficult than a more direct proof using only Ore's condition. This is just my opinion and maybe you disagree; I just don't want to lead you down the wrong path.) +\end{problem} + + + +\begin{problem}[2pts] + Let $G$ be a graph on $n$ vertices. + In class, we showed that $\alpha'(G)+\beta'(G)=n$ provided $G$ has no isolated vertices; this exercise exists to establish the natural (and easier to prove) vertex-version of this fact. + + Recall that the independence number of $G$, denoted by $\alpha(G)$, is the size of a largest independent set of $G$. + Recall also that the vertex-cover number of $G$, denoted by $\beta(G)$, is the size of a smallest vertex-cover of $G$. + + Prove that $\alpha(G)+\beta(G)=n$ for any $n$-vertex graph $G$. + + (Note: You don't need to know anything about matchings to prove this.) +\end{problem} + + +\begin{problem}[2 pts] + We have an $m\times n$ matrix $M\in\{0,1\}^{m\times n}$. + We refer to the columns and rows of this matrix as \emph{lines} (so a line is either one of the $m$ rows or one of the $n$ columns of $M$). + Prove that the minimum number of lines needed to contain all $1$'s of $M$ is precisely the maximum number of $1$'s in $M$ that one can select so that no two of these selected $1$'s live in any common line. +\end{problem} + + + + + +\end{document} diff --git a/www/teaching/graphs2022/index.html b/www/teaching/graphs2022/index.html new file mode 100644 index 0000000..e72f84c --- /dev/null +++ b/www/teaching/graphs2022/index.html @@ -0,0 +1,251 @@ +--- +title: MATH 314 (Spring 2022) +title_short: Graphs +math: true + +--- + +<h1>MATH 314: Graph Theory</h1> +<h4><a href="./syllabus.pdf">Syllabus</a></h4> +<dl> + <dt>Lecture</dt> + <dd>196 Carver Hall</dd> + <dd>TR 11:00am–12:15pm</dd> + <dt>Office hours</dt> + <dd>408C Carver Hall</dd> + <dd>M 12:00pm–1:00pm</dd> + <dd>R 2:00pm–4:00pm</dd> + <dt>Textbook</dt> + <dd><b>A first course in graph theory</b> by Gary Chartrand and Ping Zhang</dd> + <dd>Other materials will be distributed as necessary</dd> +</dl> +<br /> +<hr /> + +<h2>Schedule and Assignments</h2> +<p> +Homework assignments are due by the end of lecture on the date by which they are posted. +If you cannot attend class when an assignment is due, you are responsible for emailing your assignment to me: this email must be in my inbox by the end of lecture, and your submission must be a <tt>.pdf</tt> file. +Late submissions (be they submitted in-person or by email) incur a 1% (as in percentage point) penalty per <b>minute</b> of being late, e.g. an assignment submitted at 12:27pm which would have received an 80% will instead receive a 68%. +</p> + +<p> +<b>If you email your homework to me, please include "MATH 314" and the homework number in the subject line.</b> +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. +</p> + +<h5>A note on pictures and proofs</h5> +<p> +Oftentimes it is tempting to use a sketch of a graph (or some piece of a graph) as a part of your proof. +While sketches can be very helpful in understanding a problem and reasoning through its solution, sketches can be misleading and generally should not be included in a proof. +<b>Unless explicitly requested by a problem, none of your proofs should include sketches.</b> +</p> + +<table class="cellpadding" style="width: 100%" > + <tr> + <td colspan="3"><b>January</b></td> + </tr> + <tr> + <td style="width: 10%">Jan 18</td> + <td>Basic definitions and important jargon, walks, paths, cycles, connectivity, <a href="./extra_01-18.pdf">extra notes</a></td> + <td style="width:25%"></td> + </tr> + <tr> + <td>Jan 20</td> + <td>Connectivity (continued), bipartite graphs, <a href="./extra_01-20.pdf">extra notes</a></td> + <td></td> + </tr> + <tr> + <td>Jan 25</td> + <td>Special graphs, complements, friends of graphs, vertex degrees, handshaking lemma, <a href="./extra_01-25.pdf">extra notes</a></td> + <td><a href="./hw1.pdf">HW1</a> (<a href="./hw1.tex">.tex</a>)</td> + </tr> + <tr> + <td>Jan 27</td> + <td>Degrees and connectivity, regular graphs, <a href="./extra_01-27.pdf">extra notes</a></td> + <td></td> + </tr> + <tr> + <td colspan="3"><b>February</b></td> + </tr> + <tr> + <td>Feb 1</td> + <td>Degree sequences, Havel–Hakimi Theorem, Erdős–Gallai Theorem (one direction), <a href="./extra_02-01.pdf">extra notes</a></td> + <td><a href="./hw2.pdf">HW2</a> (<a href="./hw2.tex">.tex</a>)</td> + </tr> + <tr> + <td>Feb 3</td> + <td>Graph isomorphisms and automorphisms, Discussion session #1</td> + <td><a href="./ds1.pdf">DS1</a></td> + </tr> + <tr> + <td>Feb 8</td> + <td>Introduction to trees, <a href="./extra_02-08.pdf">extra notes</a></td> + <td><a href="./hw3.pdf">HW3</a> (<a href="./hw3.tex">.tex</a>)</td> + </tr> + <tr> + <td>Feb 10</td> + <td>More about trees and forests, spanning trees, <a href="./extra_02-10.pdf">extra notes</a></td> + <td></td> + </tr> + <tr> + <td>Feb 15</td> + <td>Minimum spanning trees, Kruskal's algorithm, Prim's algorithm <a href="./extra_02-15.pdf">extra notes</a></td> + <td><a href="./hw4.pdf">HW4</a> (<a href="./hw4.tex">.tex</a>)</td> + </tr> + <tr> + <td>Feb 17</td> + <td>Trees are everywhere, Discussion session #2, <a href="./extra_02-17.pdf">extra notes</a></td> + <td><a href="./ds2.pdf">DS2</a></td> + </tr> + <tr> + <td>Feb 22</td> + <td>Enumerating trees using Prüfer codes (this topic is not in the book), <a href="./prufer.pdf">notes</a>, <a href="./dyck.pdf">supplementary notes</a></td> + <td><a href="./hw5.pdf">HW5</a> (<a href="./hw5.tex">.tex</a>)</td> + </tr> + <tr> + <td>Feb 24</td> + <td>Connectivity revisited, cut-vertices, blocks, <a href="./extra_02-24.pdf">extra notes</a></td> + <td></td> + </tr> + <tr> + <td colspan="3"><b>March</b></td> + </tr> + <tr> + <td>Mar 1</td> + <td>Blocks (continued), vertex-connectivity, edge-connectivity <a href="./extra_03-01.pdf">extra notes</a></td> + <td><a href="./hw6.pdf">HW6</a> (<a href="./hw6.tex">.tex</a>)</td> + </tr> + <tr> + <td>Mar 3</td> + <td>Vertex- and edge-connectivity (continued), Menger's Theorem, <a href="./extra_03-03.pdf">extra notes</a></td> + <td></td> + </tr> + <tr> + <td>Mar 8</td> + <td>Review day, Discussion session #3</td> + <td><a href="./ds3.pdf">DS3</a></td> + </tr> + <tr> + <td>Mar 10</td> + <td> + <dl> + <dt><b>Midterm</b></dt> + <dd>You may bring one standard 8.5x11 sheet of paper with handwritten notes.</dd> + <dd>All materials through HW6 are fair game. Beyond those materials, you may be required to know what cut-vertices are and prove some basic properties about them, but you will not be explicitly tested on block decompositions, vertex/edge connectivity or Menger's theorem.</dd> + </dl> + </td> + <td></td> + </tr> + <tr> + <td>Mar 15</td> + <td rowspan="2"><b>No Class</b> (Spring Break), <a href="./fun.pdf">extra fun if you're bored</a></td> + <td></td> + </tr> + <tr> + <td>Mar 17</td> + <td></td> + </tr> + <tr> + <td>Mar 22</td> + <td>Eulerian circuits and trails, <a href="./extra_03-22.pdf">extra notes</a></td> + <td><a href="./hw7.pdf">HW7</a> (<a href="./hw7.tex">.tex</a>)</td> + </tr> + <tr> + <td>Mar 24</td> + <td>Hamilton cycles and paths, <a href="./extra_03-24.pdf">extra notes</a></td> + <td></td> + </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><a href="./hw8.pdf">HW8</a> (<a href="./hw8.tex">.tex</a>)</td> + </tr> + <tr> + <td>Mar 31</td> + <td>Hall's Marriage Theorem, extensions and applications, <a href="./extra_03-31.pdf">extra notes</a>, <a href="./dilworth.pdf">supplimentary notes</a></td> + <td></td> + </tr> + <tr> + <td colspan="3"><b>April</b></td> + </tr> + <tr> + <td>Apr 5</td> + <td>Graph colorings, chromatic numbers, <a href="./extra_04-05.pdf">extra notes</a></td> + <td><a href="./hw9.pdf">HW9</a> (<a href="./hw9.tex">.tex</a>)</td> + </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><a href="./ds4.pdf">DS4</a></td> + </tr> + <tr> + <td>Apr 12</td> + <td>Chromatic numbers and trees, edge-chromatic numbers <a href="./extra_04-12.pdf">extra notes</a></td> + <td><a href="./hw10.pdf">HW10</a> (<a href="./hw10.tex">.tex</a>)</td> + </tr> + <tr> + <td>Apr 14</td> + <td>Intro to planar graphs, Euler's formula, headshaking lemma, <a href="./extra_04-14.pdf">extra notes</a></td> + <td></td> + </tr> + <tr> + <td>Apr 19</td> + <td>6-color theorem, Kuratowski's Theorem (statement), Kempe swaps, 5-color theorem, <a href="./extra_04-19.pdf">extra notes</a></td> + <td><a href="./hw11.pdf">HW11</a> (<a href="./hw11.tex">.tex</a>)</td> + </tr> + <tr> + <td>Apr 21</td> + <td>Discussion session #5, <a href="./extra_04-21.pdf">extra notes</a></td> + <td><a href="./ds5.pdf">DS5</a></td> + </tr> + <tr> + <td>Apr 26</td> + <td>Introduction to Ramsey numbers, <a href="./extra_04-26.pdf">extra notes</a></td> + <td><a href="./hw12.pdf">HW12</a> (<a href="./hw12.tex">.tex</a>)</td> + </tr> + <tr> + <td>Apr 28</td> + <td>Lower-bounds on Ramsey numbers, how many monochromatic triangles are there? <a href="./extra_04-28.pdf">extra notes</a></td> + <td></td> + </tr> + <tr> + <td colspan="3"><b>May</b></td> + </tr> + <tr> + <td>May 3</td> + <td>Extremal numbers, Mantel, Turán, Kővári–Sós–Turán (special case), <a href="./extra_05-03.pdf">extra notes</a></td> + <td><a href="./hw13.pdf">HW13</a> (<a href="./hw13.tex">.tex</a>)</td> + </tr> + <tr> + <td>May 5</td> + <td>Review day, Discussion session #6</td> + <td><a href="./ds6.pdf">DS6</a></td> + </tr> + <tr> + <td>May 12</td> + <td> + <dl> + <dt><b>Final Exam</b></dt> + <dd>You may bring one standard 8.5x11 sheet of paper with handwritten notes.</dd> + <dd>The exam will focus on materials covered in HW7–HW13. Of course, this class builds heavily upon itself, so you won't succeed in this exam unless you have a firm grasp on the materials in HW1–HW6.</dd> + </dl> + </td> + <td> + <dl> + <dt><b>Location & Time</b></dt> + <dd>196 Carver Hall</dd> + <dd>Thursday, May 12</dd> + <dd>9:45am–11:45am</dd> + </dl> + </td> + </tr> +</table> + +<hr /> + +$snippet(replaceFileName(path,"_notation.html"))$ diff --git a/www/teaching/graphs2022/prufer.pdf b/www/teaching/graphs2022/prufer.pdf Binary files differnew file mode 100644 index 0000000..02bdc9e --- /dev/null +++ b/www/teaching/graphs2022/prufer.pdf diff --git a/www/teaching/graphs2022/syllabus.pdf b/www/teaching/graphs2022/syllabus.pdf Binary files differnew file mode 100644 index 0000000..35caf8b --- /dev/null +++ b/www/teaching/graphs2022/syllabus.pdf diff --git a/www/teaching/lcs22/aldous_markov.pdf b/www/teaching/lcs22/aldous_markov.pdf Binary files differnew file mode 100644 index 0000000..260d0bd --- /dev/null +++ b/www/teaching/lcs22/aldous_markov.pdf diff --git a/www/teaching/lcs22/alexander_lcs.pdf b/www/teaching/lcs22/alexander_lcs.pdf Binary files differnew file mode 100644 index 0000000..9b55a81 --- /dev/null +++ b/www/teaching/lcs22/alexander_lcs.pdf diff --git a/www/teaching/lcs22/alon_probcomb.pdf b/www/teaching/lcs22/alon_probcomb.pdf Binary files differnew file mode 100644 index 0000000..d135d5c --- /dev/null +++ b/www/teaching/lcs22/alon_probcomb.pdf diff --git a/www/teaching/lcs22/bukh_frogs.pdf b/www/teaching/lcs22/bukh_frogs.pdf Binary files differnew file mode 100644 index 0000000..362042c --- /dev/null +++ b/www/teaching/lcs22/bukh_frogs.pdf diff --git a/www/teaching/lcs22/chvatal_lcs.pdf b/www/teaching/lcs22/chvatal_lcs.pdf Binary files differnew file mode 100644 index 0000000..a451657 --- /dev/null +++ b/www/teaching/lcs22/chvatal_lcs.pdf diff --git a/www/teaching/lcs22/hollander_coupling.pdf b/www/teaching/lcs22/hollander_coupling.pdf Binary files differnew file mode 100644 index 0000000..3c7b015 --- /dev/null +++ b/www/teaching/lcs22/hollander_coupling.pdf diff --git a/www/teaching/lcs22/index.html b/www/teaching/lcs22/index.html new file mode 100644 index 0000000..5a10fb7 --- /dev/null +++ b/www/teaching/lcs22/index.html @@ -0,0 +1,36 @@ +--- +title: MATH 595 (Fall 2022) +title_short: Longest Common Subsequences +math: true + +--- + +<h1>MATH 595: Longest Common Subsequences</h1> + +<p> +This is a graduate research seminar, so there will not be any official homeworks nor assessments. +This page will simply be used for posting relevant materials. +</p> + +<hr /> + +<h3>Relevant papers</h3> +<ul> + <li><a href="./chvatal_lcs.pdf">Longest common subsequences of two random sequences</a> by Chvátal and Sankoff + <li><a href="./alexander_lcs.pdf">The rate of convergence of the mean length of the longest common subsequence</a> by Alexander</li> + <li><a href="./kiwi_lcs.pdf">Expected length of the longest common subsequence for large alphabets</a> by Kiwi, Loebl and Matoušek</li> + <li><a href="./lueker_lcs.pdf">Improved bounds on the average length of the longest common subsequences</a> by Lueker</li> + <li><a href="./bukh_frogs.pdf">Periodic words, common subsequences and frogs</a> by Bukh and Cox + <ul> + <li><a href="http://www.borisbukh.org/code/lcsfrogs19.html">code</a></li> + </ul> + </li> +</ul> + +<h3>Background reading</h3> +<ul> + <li><a href="norris_markov.pdf">Markov Chains</a> by Norris</li> + <li><a href="aldous_markov.pdf">Reversible Markov chains and random walks on graphs</a> by Aldous and Fill</li> + <li><a href="alon_probcomb.pdf">The probabilistic method</a> by Alon and Spencer</li> + <li><a href="hollander_coupling.pdf">Probability theory: The coupling method</a> by Hollander</li> +</ul> diff --git a/www/teaching/lcs22/kiwi_lcs.pdf b/www/teaching/lcs22/kiwi_lcs.pdf Binary files differnew file mode 100644 index 0000000..e7e49e0 --- /dev/null +++ b/www/teaching/lcs22/kiwi_lcs.pdf diff --git a/www/teaching/lcs22/lueker_lcs.pdf b/www/teaching/lcs22/lueker_lcs.pdf Binary files differnew file mode 100644 index 0000000..4f48698 --- /dev/null +++ b/www/teaching/lcs22/lueker_lcs.pdf diff --git a/www/teaching/lcs22/norris_markov.pdf b/www/teaching/lcs22/norris_markov.pdf Binary files differnew file mode 100644 index 0000000..063343f --- /dev/null +++ b/www/teaching/lcs22/norris_markov.pdf diff --git a/www/teaching/matrices2019/.htaccess b/www/teaching/matrices2019/.htaccess new file mode 100644 index 0000000..a81375f --- /dev/null +++ b/www/teaching/matrices2019/.htaccess @@ -0,0 +1,10 @@ +AuthUserFile /var/www/htpass/matrices2019/solutions +AuthName "Homework Solutions" +AuthType Basic +<Files ".htaccess"> +order allow,deny +deny from all +</Files> +<FilesMatch ".*sol\.pdf$"> +require user matrices +</FilesMatch> diff --git a/www/teaching/matrices2019/.password b/www/teaching/matrices2019/.password new file mode 100644 index 0000000..f83297b --- /dev/null +++ b/www/teaching/matrices2019/.password @@ -0,0 +1 @@ +matrices:kerneloftruth diff --git a/www/teaching/matrices2019/basis.pdf b/www/teaching/matrices2019/basis.pdf Binary files differnew file mode 100644 index 0000000..221d090 --- /dev/null +++ b/www/teaching/matrices2019/basis.pdf diff --git a/www/teaching/matrices2019/dsw1.pdf b/www/teaching/matrices2019/dsw1.pdf Binary files differnew file mode 100644 index 0000000..46bfeb6 --- /dev/null +++ b/www/teaching/matrices2019/dsw1.pdf diff --git a/www/teaching/matrices2019/dsw2.pdf b/www/teaching/matrices2019/dsw2.pdf Binary files differnew file mode 100644 index 0000000..3b8e3cb --- /dev/null +++ b/www/teaching/matrices2019/dsw2.pdf diff --git a/www/teaching/matrices2019/dsw3.pdf b/www/teaching/matrices2019/dsw3.pdf Binary files differnew file mode 100644 index 0000000..1cd03a6 --- /dev/null +++ b/www/teaching/matrices2019/dsw3.pdf diff --git a/www/teaching/matrices2019/dsw4.pdf b/www/teaching/matrices2019/dsw4.pdf Binary files differnew file mode 100644 index 0000000..1e724a8 --- /dev/null +++ b/www/teaching/matrices2019/dsw4.pdf diff --git a/www/teaching/matrices2019/dsw5.pdf b/www/teaching/matrices2019/dsw5.pdf Binary files differnew file mode 100644 index 0000000..6622ee8 --- /dev/null +++ b/www/teaching/matrices2019/dsw5.pdf diff --git a/www/teaching/matrices2019/dsw6.pdf b/www/teaching/matrices2019/dsw6.pdf Binary files differnew file mode 100644 index 0000000..af00c9a --- /dev/null +++ b/www/teaching/matrices2019/dsw6.pdf diff --git a/www/teaching/matrices2019/hw1.pdf b/www/teaching/matrices2019/hw1.pdf Binary files differnew file mode 100644 index 0000000..23a6483 --- /dev/null +++ b/www/teaching/matrices2019/hw1.pdf diff --git a/www/teaching/matrices2019/hw10.pdf b/www/teaching/matrices2019/hw10.pdf Binary files differnew file mode 100644 index 0000000..10c692d --- /dev/null +++ b/www/teaching/matrices2019/hw10.pdf diff --git a/www/teaching/matrices2019/hw11.pdf b/www/teaching/matrices2019/hw11.pdf Binary files differnew file mode 100644 index 0000000..f626728 --- /dev/null +++ b/www/teaching/matrices2019/hw11.pdf diff --git a/www/teaching/matrices2019/hw2.pdf b/www/teaching/matrices2019/hw2.pdf Binary files differnew file mode 100644 index 0000000..4b54f01 --- /dev/null +++ b/www/teaching/matrices2019/hw2.pdf diff --git a/www/teaching/matrices2019/hw3.pdf b/www/teaching/matrices2019/hw3.pdf Binary files differnew file mode 100644 index 0000000..c1c7207 --- /dev/null +++ b/www/teaching/matrices2019/hw3.pdf diff --git a/www/teaching/matrices2019/hw4.pdf b/www/teaching/matrices2019/hw4.pdf Binary files differnew file mode 100644 index 0000000..0d01d55 --- /dev/null +++ b/www/teaching/matrices2019/hw4.pdf diff --git a/www/teaching/matrices2019/hw5.pdf b/www/teaching/matrices2019/hw5.pdf Binary files differnew file mode 100644 index 0000000..c7111ea --- /dev/null +++ b/www/teaching/matrices2019/hw5.pdf diff --git a/www/teaching/matrices2019/hw6.pdf b/www/teaching/matrices2019/hw6.pdf Binary files differnew file mode 100644 index 0000000..a743801 --- /dev/null +++ b/www/teaching/matrices2019/hw6.pdf diff --git a/www/teaching/matrices2019/hw7.pdf b/www/teaching/matrices2019/hw7.pdf Binary files differnew file mode 100644 index 0000000..0e2e2f3 --- /dev/null +++ b/www/teaching/matrices2019/hw7.pdf diff --git a/www/teaching/matrices2019/hw8.pdf b/www/teaching/matrices2019/hw8.pdf Binary files differnew file mode 100644 index 0000000..5865bbd --- /dev/null +++ b/www/teaching/matrices2019/hw8.pdf diff --git a/www/teaching/matrices2019/hw9.pdf b/www/teaching/matrices2019/hw9.pdf Binary files differnew file mode 100644 index 0000000..774afc6 --- /dev/null +++ b/www/teaching/matrices2019/hw9.pdf diff --git a/www/teaching/matrices2019/index.html b/www/teaching/matrices2019/index.html new file mode 100644 index 0000000..3541d94 --- /dev/null +++ b/www/teaching/matrices2019/index.html @@ -0,0 +1,226 @@ +--- +title: 21-241 (summer 2019) +title_short: Matrices +math: true + +--- + +<h1>21-241: Matrices and Linear Transformations</h1> +<h4><a href="./syllabus.pdf">Course Information</a></h4> +<dl> + <dt>Lecture</dt> + <dd>4709 Wean Hall</dd> + <dd>MTWRF 10:30–11:50 a.m.</dd> + <dt>Office hours</dt> + <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> +</dl> +<br /> +<hr /> + +<h2>Schedule and Assignments</h2> +<h5><a href="/doc/hw.tex">Homework Template</a></h5> +<p>Homework assignments are due on the date by which they are posted. <br /> +Solutions will be posted after the lecture that day.</p> +<table class="cellpadding" style="width: 100%" > + <tr> + <td colspan="3"><b>Week #1</b></td> + </tr> + <tr> + <td style="width: 15%">July 1</td> + <td>Systems of linear equations, Gaussian elimination, matrix-vector representations</td> + <td></td> + </tr> + <tr> + <td>July 2</td> + <td>Matrix rank, homogenous and non-homogeneous solutions</td> + <td><a href="hw1.pdf">HW1</a></td> + </tr> + <tr> + <td>July 3</td> + <td>Matrix operations, matrix inverse</td> + <td style="width: 25%"></td> + </tr> + <tr> + <td>July 4</td> + <td><b>No Class</b> (Independence Day)</td> + <td></td> + </tr> + <tr> + <td>July 5</td> + <td>Matrix inverse (cont), elementary matrices, <a href="dsw1.pdf">DSW1</a></td> + <td><a href="hw2.pdf">HW2</a></td> + </tr> + <tr> + <td colspan="3"><b>Week #2</b></td> + </tr> + <tr> + <td>July 8</td> + <td>Vector spaces, subpaces</td> + <td></td> + </tr> + <tr> + <td>July 9</td> + <td>Subspace properties, principle of mathematical induction, span</td> + <td><a href="hw3.pdf">HW3</a></td> + </tr> + <tr> + <td>July 10</td> + <td>Linear independence, basis, dimension</td> + <td></td> + </tr> + <tr> + <td>July 11</td> + <td>Four fundamental subspaces of a matrix, matrix rank for realsies (or complexsies)</td> + <td></td> + </tr> + <tr> + <td>July 12</td> + <td>Fisher's theorem, rank–nullity theorem, <a href="dsw2.pdf">DSW2</a></td> + <td><a href="hw4.pdf">HW4</a></td> + </tr> + <tr> + <td colspan="3"><b>Week #3</b></td> + </tr> + <tr> + <td>July 15</td> + <td>Inner products, norms, Cauchy–Schwarz inequality</td> + <td></td> + </tr> + <tr> + <td>July 16</td> + <td>Orthonormal bases, Gram–Schmidt algorithm, orthogonal complement</td> + <td><a href="hw5.pdf">HW5</a></td> + </tr> + <tr> + <td>July 17</td> + <td> + <dl> + <dt><b>Midterm</b></dt> + <dd>The exam will cover all materials through HW5.</dd> + <dd>Remember, you may bring one standard 8.5x11 sheet of paper with handwritten notes.</dd> + </dl> + </td> + <td></td> + </tr> + <tr> + <td>July 18</td> + <td>Orthogonal complements (cont), pathological examples in infinitely many dimensions, projections</td> + <td></td> + </tr> + <tr> + <td>July 19</td> + <td>Linear transformations, every reasonable function is a matrix, <a href="dsw3.pdf">DSW3</a></td> + <td><a href="hw6.pdf">HW6</a></td> + </tr> + <tr> + <td colspan="3"><b>Week #4</b></td> + </tr> + <tr> + <td>July 22</td> + <td>Linear transformations (cont), isomorphisms, partial converse to the rank–nullity theorem</td> + <td></td> + </tr> + <tr> + <td>July 23</td> + <td>Orthogonal matrices, isometries of $$\mathbb{R}^n$$</td> + <td><a href="hw7.pdf">HW7</a></td> + </tr> + <tr> + <td>July 24</td> + <td>Change-of-basis, similarity, diagonalizable matrices</td> + <td></td> + </tr> + <tr> + <td>July 25</td> + <td>A first look at eigenvalues and eigenvectors, Schur's triangularization theorem</td> + <td></td> + </tr> + <tr> + <td>July 26</td> + <td>Determinants, <a href="dsw4.pdf">DSW4</a></td> + <td><a href="hw8.pdf">HW8</a></td> + </tr> + <tr> + <td colspan="3"><b>Week #5</b></td> + </tr> + <tr> + <td>July 29</td> + <td>Determinants (cont)</td> + <td></td> + </tr> + <tr> + <td>July 30</td> + <td>Characteristic polynomials, eigenvalues and eigenvectors, spectral theorem</td> + <td><a href="hw9.pdf">HW9</a></td> + </tr> + <tr> + <td>July 31</td> + <td>Cayley–Hamilton theorem, Fibonacci numbers</td> + <td>No office hours today</td> + </tr> + <tr> + <td>Aug 1</td> + <td>Positive (semi)definite matrices</td> + <td>Office hours from 12–2</td> + </tr> + <tr> + <td>Aug 2</td> + <td>Invariant subpaces, <a href="dsw5.pdf">DSW5</a></td> + <td><a href="hw10.pdf">HW10</a></td> + </tr> + <tr> + <td colspan="3"><b>Week #6</b></td> + </tr> + <tr> + <td>Aug 5</td> + <td>Invariant subspaces (cont), Jordan canonical form</td> + <td></td> + </tr> + <tr> + <td>Aug 6</td> + <td>Jordan canonical form (cont)</td> + <td></td> + </tr> + <tr> + <td>Aug 7</td> + <td>Funzies: almost orthogonal vectors, decomposing rectangles into squares, etc</td> + <td><a href="hw11.pdf">HW11</a></td> + </tr> + <tr> + <td>Aug 8</td> + <td>Funzies: Hadamard's theorem, etc, <a href="dsw6.pdf">DSW6</a></td> + <td></td> + </tr> + <tr> + <td>Aug 9</td> + <td> + <dl> + <dt><b>Final Exam</b></dt> + <dd>The exam will cover all materials in HW6 through HW11.</dd> + <dd>Remember, you may bring one standard 8.5x11 sheet of paper with handwritten notes.</dd> + </dl> + </td> + <td> + <dl> + <dt><b>Location & Time</b></dt> + <dd>B131 Hamerschlag Hall</dd> + <dd>4:00–7:00 p.m.</dd> + </dl> + </td> + </tr> +</table> +<br /> +<hr /> + +<h4>Supplementary Materials</h4> +<p>It turns out that every vector space having a basis is equivalent to the Axiom of Choice. +This material is beyond the scope of this course, but I still recommend giving it a read.</p> +<ul> + <li>Notes on Zorn's Lemma and the Axiom of Choice can be found <a href="http://www.borisbukh.org/MathStudiesAlgebra1718/notes_ac.pdf">here</a>, courtesy of Boris Bukh.</li> + <li>A proof that Zorn's Lemma implies that every vector space has a basis can be found <a href="./basis.pdf">here</a>.</li> + <li>Andreas Blass's <a href="http://www.math.lsa.umich.edu/~ablass/bases-AC.pdf">paper</a> shows that if every vector space has a basis, then the Axiom of Choice is true.</li> +</ul> diff --git a/www/teaching/matrices2019/syllabus.pdf b/www/teaching/matrices2019/syllabus.pdf Binary files differnew file mode 100644 index 0000000..67aa338 --- /dev/null +++ b/www/teaching/matrices2019/syllabus.pdf |