From ff65b3f82a5cdb84ef528ca9265d908c55f48902 Mon Sep 17 00:00:00 2001 From: Chris Wells Date: Sun, 8 Feb 2026 18:53:16 -0600 Subject: Eventually each teaching site will be moved into its original repo, but that's for a later date... --- www/teaching/algmethods22/index.html | 24 +++ www/teaching/algmethods22/lovasz_shannon.pdf | Bin 0 -> 869084 bytes www/teaching/calcI21/challenge1.pdf | Bin 0 -> 100865 bytes www/teaching/calcI21/challenge2.pdf | Bin 0 -> 72701 bytes www/teaching/calcI21/challenge3.pdf | Bin 0 -> 119952 bytes www/teaching/calcI21/index.html | 28 +++ www/teaching/concepts2017/.htaccess | 10 ++ www/teaching/concepts2017/.password | 1 + www/teaching/concepts2017/DSW2.pdf | Bin 0 -> 125134 bytes www/teaching/concepts2017/DSW3.pdf | Bin 0 -> 147698 bytes www/teaching/concepts2017/DSW4.pdf | Bin 0 -> 82394 bytes www/teaching/concepts2017/DSW5.pdf | Bin 0 -> 109036 bytes www/teaching/concepts2017/NHW1.pdf | Bin 0 -> 119246 bytes www/teaching/concepts2017/NHW10.pdf | Bin 0 -> 68832 bytes www/teaching/concepts2017/NHW10re.pdf | Bin 0 -> 57890 bytes www/teaching/concepts2017/NHW11.pdf | Bin 0 -> 96477 bytes www/teaching/concepts2017/NHW11re.pdf | Bin 0 -> 72137 bytes www/teaching/concepts2017/NHW12.pdf | Bin 0 -> 88197 bytes www/teaching/concepts2017/NHW12re.pdf | Bin 0 -> 61179 bytes www/teaching/concepts2017/NHW13.pdf | Bin 0 -> 65441 bytes www/teaching/concepts2017/NHW13re.pdf | Bin 0 -> 55893 bytes www/teaching/concepts2017/NHW1re.pdf | Bin 0 -> 56100 bytes www/teaching/concepts2017/NHW2.pdf | Bin 0 -> 88154 bytes www/teaching/concepts2017/NHW2re.pdf | Bin 0 -> 59556 bytes www/teaching/concepts2017/NHW3.pdf | Bin 0 -> 81633 bytes www/teaching/concepts2017/NHW3re.pdf | Bin 0 -> 51312 bytes www/teaching/concepts2017/NHW4.pdf | Bin 0 -> 96754 bytes www/teaching/concepts2017/NHW4re.pdf | Bin 0 -> 55923 bytes www/teaching/concepts2017/NHW5.pdf | Bin 0 -> 91784 bytes www/teaching/concepts2017/NHW5re.pdf | Bin 0 -> 55294 bytes www/teaching/concepts2017/NHW6.pdf | Bin 0 -> 74378 bytes www/teaching/concepts2017/NHW6re.pdf | Bin 0 -> 64097 bytes www/teaching/concepts2017/NHW7.pdf | Bin 0 -> 107881 bytes www/teaching/concepts2017/NHW7re.pdf | Bin 0 -> 92046 bytes www/teaching/concepts2017/NHW8.pdf | Bin 0 -> 85254 bytes www/teaching/concepts2017/NHW8re.pdf | Bin 0 -> 77766 bytes www/teaching/concepts2017/NHW9.pdf | Bin 0 -> 85234 bytes www/teaching/concepts2017/NHW9re.pdf | Bin 0 -> 77138 bytes www/teaching/concepts2017/Sullivan_Text.pdf | Bin 0 -> 3195181 bytes www/teaching/concepts2017/WHW1.pdf | Bin 0 -> 82061 bytes www/teaching/concepts2017/WHW2.pdf | Bin 0 -> 115025 bytes www/teaching/concepts2017/WHW2re.pdf | Bin 0 -> 56781 bytes www/teaching/concepts2017/WHW3.pdf | Bin 0 -> 124540 bytes www/teaching/concepts2017/WHW3re.pdf | Bin 0 -> 75952 bytes www/teaching/concepts2017/WHW4.pdf | Bin 0 -> 181224 bytes www/teaching/concepts2017/WHW4re.pdf | Bin 0 -> 55126 bytes www/teaching/concepts2017/WHW5.pdf | Bin 0 -> 123868 bytes www/teaching/concepts2017/WHW5re.pdf | Bin 0 -> 55610 bytes www/teaching/concepts2017/index.html | 198 +++++++++++++++++++++ www/teaching/concepts2017/review.pdf | Bin 0 -> 112040 bytes www/teaching/concepts2017/syllabus.pdf | Bin 0 -> 231881 bytes www/teaching/discrete20/.htaccess | 19 ++ www/teaching/discrete20/.password | 4 + www/teaching/discrete20/extra.pdf | Bin 0 -> 142214 bytes www/teaching/discrete20/hats.pdf | Bin 0 -> 126508 bytes www/teaching/discrete20/index.html | 157 +++++++++++++++++ www/teaching/discrete20/pairwise.pdf | Bin 0 -> 134135 bytes www/teaching/discrete20/pie.pdf | Bin 0 -> 158348 bytes www/teaching/discrete20/quiz11.pdf | Bin 0 -> 98549 bytes www/teaching/discrete20/quiz12.pdf | Bin 0 -> 152075 bytes www/teaching/discrete20/quiz13.pdf | Bin 0 -> 116738 bytes www/teaching/discrete20/quiz14.pdf | Bin 0 -> 115656 bytes www/teaching/discrete20/rec1.pdf | Bin 0 -> 143499 bytes www/teaching/discrete20/rec10.pdf | Bin 0 -> 164637 bytes www/teaching/discrete20/rec11.pdf | Bin 0 -> 126446 bytes www/teaching/discrete20/rec12.pdf | Bin 0 -> 152729 bytes www/teaching/discrete20/rec2.pdf | Bin 0 -> 160215 bytes www/teaching/discrete20/rec4.pdf | Bin 0 -> 165482 bytes www/teaching/discrete20/rec5.pdf | Bin 0 -> 145352 bytes www/teaching/discrete20/rec6.pdf | Bin 0 -> 151460 bytes www/teaching/discrete20/rec7.pdf | Bin 0 -> 185427 bytes www/teaching/discrete20/rec8.pdf | Bin 0 -> 134288 bytes www/teaching/discrete20/rec9.pdf | Bin 0 -> 169522 bytes www/teaching/discrete2016/disc_rec_1.pdf | Bin 0 -> 117868 bytes www/teaching/discrete2016/disc_rec_10.pdf | Bin 0 -> 157616 bytes www/teaching/discrete2016/disc_rec_11.pdf | Bin 0 -> 131733 bytes www/teaching/discrete2016/disc_rec_13.pdf | Bin 0 -> 125522 bytes www/teaching/discrete2016/disc_rec_14.pdf | Bin 0 -> 107570 bytes www/teaching/discrete2016/disc_rec_2.pdf | Bin 0 -> 128372 bytes www/teaching/discrete2016/disc_rec_3.pdf | Bin 0 -> 150977 bytes www/teaching/discrete2016/disc_rec_4.pdf | Bin 0 -> 153818 bytes www/teaching/discrete2016/disc_rec_6.pdf | Bin 0 -> 126109 bytes www/teaching/discrete2016/disc_rec_7.pdf | Bin 0 -> 131828 bytes www/teaching/discrete2016/disc_rec_8.pdf | Bin 0 -> 167510 bytes www/teaching/discrete2016/index.html | 47 +++++ www/teaching/graphs2022/.htaccess | 10 ++ www/teaching/graphs2022/_notation.html | 180 +++++++++++++++++++ www/teaching/graphs2022/dilworth.pdf | Bin 0 -> 210467 bytes www/teaching/graphs2022/ds1.pdf | Bin 0 -> 143800 bytes www/teaching/graphs2022/ds2.pdf | Bin 0 -> 142283 bytes www/teaching/graphs2022/ds3.pdf | Bin 0 -> 231280 bytes www/teaching/graphs2022/ds4.pdf | Bin 0 -> 150636 bytes www/teaching/graphs2022/ds5.pdf | Bin 0 -> 136900 bytes www/teaching/graphs2022/ds6.pdf | Bin 0 -> 195329 bytes www/teaching/graphs2022/dyck.pdf | Bin 0 -> 199820 bytes www/teaching/graphs2022/extra_01-18.pdf | Bin 0 -> 132966 bytes www/teaching/graphs2022/extra_01-20.pdf | Bin 0 -> 149413 bytes www/teaching/graphs2022/extra_01-25.pdf | Bin 0 -> 134001 bytes www/teaching/graphs2022/extra_01-27.pdf | Bin 0 -> 146656 bytes www/teaching/graphs2022/extra_02-01.pdf | Bin 0 -> 120303 bytes www/teaching/graphs2022/extra_02-08.pdf | Bin 0 -> 125951 bytes www/teaching/graphs2022/extra_02-10.pdf | Bin 0 -> 118433 bytes www/teaching/graphs2022/extra_02-24.pdf | Bin 0 -> 166498 bytes www/teaching/graphs2022/extra_03-01.pdf | Bin 0 -> 120232 bytes www/teaching/graphs2022/extra_03-03.pdf | Bin 0 -> 158463 bytes www/teaching/graphs2022/extra_03-22.pdf | Bin 0 -> 185012 bytes www/teaching/graphs2022/extra_03-29.pdf | Bin 0 -> 188834 bytes www/teaching/graphs2022/extra_03-31.pdf | Bin 0 -> 229233 bytes www/teaching/graphs2022/extra_04-05.pdf | Bin 0 -> 153964 bytes www/teaching/graphs2022/extra_04-07.pdf | Bin 0 -> 105853 bytes www/teaching/graphs2022/extra_04-12.pdf | Bin 0 -> 203410 bytes www/teaching/graphs2022/extra_04-14.pdf | Bin 0 -> 187336 bytes www/teaching/graphs2022/extra_04-19.pdf | Bin 0 -> 216044 bytes www/teaching/graphs2022/extra_04-26.pdf | Bin 0 -> 190548 bytes www/teaching/graphs2022/extra_04-28.pdf | Bin 0 -> 184654 bytes www/teaching/graphs2022/extra_05-03.pdf | Bin 0 -> 175624 bytes www/teaching/graphs2022/fun.pdf | Bin 0 -> 114487 bytes www/teaching/graphs2022/hw1.pdf | Bin 0 -> 96520 bytes www/teaching/graphs2022/hw1.tex | 126 ++++++++++++++ www/teaching/graphs2022/hw10.pdf | Bin 0 -> 173559 bytes www/teaching/graphs2022/hw10.tex | 193 ++++++++++++++++++++ www/teaching/graphs2022/hw11.pdf | Bin 0 -> 124456 bytes www/teaching/graphs2022/hw11.tex | 162 +++++++++++++++++ www/teaching/graphs2022/hw12.pdf | Bin 0 -> 99252 bytes www/teaching/graphs2022/hw12.tex | 140 +++++++++++++++ www/teaching/graphs2022/hw13.pdf | Bin 0 -> 170608 bytes www/teaching/graphs2022/hw13.tex | 155 +++++++++++++++++ www/teaching/graphs2022/hw2.pdf | Bin 0 -> 125043 bytes www/teaching/graphs2022/hw2.tex | 134 ++++++++++++++ www/teaching/graphs2022/hw3.pdf | Bin 0 -> 89192 bytes www/teaching/graphs2022/hw3.tex | 130 ++++++++++++++ www/teaching/graphs2022/hw4.pdf | Bin 0 -> 146357 bytes www/teaching/graphs2022/hw4.tex | 129 ++++++++++++++ www/teaching/graphs2022/hw5.pdf | Bin 0 -> 145049 bytes www/teaching/graphs2022/hw5.tex | 131 ++++++++++++++ www/teaching/graphs2022/hw6.pdf | Bin 0 -> 113834 bytes www/teaching/graphs2022/hw6.tex | 170 ++++++++++++++++++ www/teaching/graphs2022/hw7.pdf | Bin 0 -> 126370 bytes www/teaching/graphs2022/hw7.tex | 143 +++++++++++++++ www/teaching/graphs2022/hw8.pdf | Bin 0 -> 147135 bytes www/teaching/graphs2022/hw8.tex | 139 +++++++++++++++ www/teaching/graphs2022/hw9.pdf | Bin 0 -> 136949 bytes www/teaching/graphs2022/hw9.tex | 151 ++++++++++++++++ www/teaching/graphs2022/index.html | 251 +++++++++++++++++++++++++++ www/teaching/graphs2022/prufer.pdf | Bin 0 -> 218753 bytes www/teaching/graphs2022/syllabus.pdf | Bin 0 -> 129504 bytes www/teaching/lcs22/aldous_markov.pdf | Bin 0 -> 1861415 bytes www/teaching/lcs22/alexander_lcs.pdf | Bin 0 -> 1017207 bytes www/teaching/lcs22/alon_probcomb.pdf | Bin 0 -> 2513954 bytes www/teaching/lcs22/bukh_frogs.pdf | Bin 0 -> 749830 bytes www/teaching/lcs22/chvatal_lcs.pdf | Bin 0 -> 740288 bytes www/teaching/lcs22/hollander_coupling.pdf | Bin 0 -> 634702 bytes www/teaching/lcs22/index.html | 36 ++++ www/teaching/lcs22/kiwi_lcs.pdf | Bin 0 -> 193390 bytes www/teaching/lcs22/lueker_lcs.pdf | Bin 0 -> 493306 bytes www/teaching/lcs22/norris_markov.pdf | Bin 0 -> 12460676 bytes www/teaching/matrices2019/.htaccess | 10 ++ www/teaching/matrices2019/.password | 1 + www/teaching/matrices2019/basis.pdf | Bin 0 -> 99318 bytes www/teaching/matrices2019/dsw1.pdf | Bin 0 -> 118530 bytes www/teaching/matrices2019/dsw2.pdf | Bin 0 -> 129675 bytes www/teaching/matrices2019/dsw3.pdf | Bin 0 -> 142888 bytes www/teaching/matrices2019/dsw4.pdf | Bin 0 -> 124518 bytes www/teaching/matrices2019/dsw5.pdf | Bin 0 -> 140953 bytes www/teaching/matrices2019/dsw6.pdf | Bin 0 -> 116703 bytes www/teaching/matrices2019/hw1.pdf | Bin 0 -> 75447 bytes www/teaching/matrices2019/hw10.pdf | Bin 0 -> 120382 bytes www/teaching/matrices2019/hw11.pdf | Bin 0 -> 113958 bytes www/teaching/matrices2019/hw2.pdf | Bin 0 -> 94101 bytes www/teaching/matrices2019/hw3.pdf | Bin 0 -> 94438 bytes www/teaching/matrices2019/hw4.pdf | Bin 0 -> 100870 bytes www/teaching/matrices2019/hw5.pdf | Bin 0 -> 92215 bytes www/teaching/matrices2019/hw6.pdf | Bin 0 -> 118884 bytes www/teaching/matrices2019/hw7.pdf | Bin 0 -> 130623 bytes www/teaching/matrices2019/hw8.pdf | Bin 0 -> 143892 bytes www/teaching/matrices2019/hw9.pdf | Bin 0 -> 117958 bytes www/teaching/matrices2019/index.html | 226 ++++++++++++++++++++++++ www/teaching/matrices2019/syllabus.pdf | Bin 0 -> 118980 bytes 178 files changed, 3105 insertions(+) create mode 100644 www/teaching/algmethods22/index.html create mode 100644 www/teaching/algmethods22/lovasz_shannon.pdf create mode 100644 www/teaching/calcI21/challenge1.pdf create mode 100644 www/teaching/calcI21/challenge2.pdf create mode 100644 www/teaching/calcI21/challenge3.pdf create mode 100644 www/teaching/calcI21/index.html create mode 100644 www/teaching/concepts2017/.htaccess create mode 100644 www/teaching/concepts2017/.password create mode 100644 www/teaching/concepts2017/DSW2.pdf create mode 100644 www/teaching/concepts2017/DSW3.pdf create mode 100644 www/teaching/concepts2017/DSW4.pdf create mode 100644 www/teaching/concepts2017/DSW5.pdf create mode 100644 www/teaching/concepts2017/NHW1.pdf create mode 100644 www/teaching/concepts2017/NHW10.pdf create mode 100644 www/teaching/concepts2017/NHW10re.pdf create mode 100644 www/teaching/concepts2017/NHW11.pdf create mode 100644 www/teaching/concepts2017/NHW11re.pdf create mode 100644 www/teaching/concepts2017/NHW12.pdf create mode 100644 www/teaching/concepts2017/NHW12re.pdf create mode 100644 www/teaching/concepts2017/NHW13.pdf create mode 100644 www/teaching/concepts2017/NHW13re.pdf create mode 100644 www/teaching/concepts2017/NHW1re.pdf create mode 100644 www/teaching/concepts2017/NHW2.pdf create mode 100644 www/teaching/concepts2017/NHW2re.pdf create mode 100644 www/teaching/concepts2017/NHW3.pdf create mode 100644 www/teaching/concepts2017/NHW3re.pdf create mode 100644 www/teaching/concepts2017/NHW4.pdf create mode 100644 www/teaching/concepts2017/NHW4re.pdf create mode 100644 www/teaching/concepts2017/NHW5.pdf create mode 100644 www/teaching/concepts2017/NHW5re.pdf create mode 100644 www/teaching/concepts2017/NHW6.pdf create mode 100644 www/teaching/concepts2017/NHW6re.pdf create mode 100644 www/teaching/concepts2017/NHW7.pdf create mode 100644 www/teaching/concepts2017/NHW7re.pdf create mode 100644 www/teaching/concepts2017/NHW8.pdf create mode 100644 www/teaching/concepts2017/NHW8re.pdf create mode 100644 www/teaching/concepts2017/NHW9.pdf create mode 100644 www/teaching/concepts2017/NHW9re.pdf create mode 100644 www/teaching/concepts2017/Sullivan_Text.pdf create mode 100644 www/teaching/concepts2017/WHW1.pdf create mode 100644 www/teaching/concepts2017/WHW2.pdf create mode 100644 www/teaching/concepts2017/WHW2re.pdf create mode 100644 www/teaching/concepts2017/WHW3.pdf create mode 100644 www/teaching/concepts2017/WHW3re.pdf create mode 100644 www/teaching/concepts2017/WHW4.pdf create mode 100644 www/teaching/concepts2017/WHW4re.pdf create mode 100644 www/teaching/concepts2017/WHW5.pdf create mode 100644 www/teaching/concepts2017/WHW5re.pdf create mode 100644 www/teaching/concepts2017/index.html create mode 100644 www/teaching/concepts2017/review.pdf create mode 100644 www/teaching/concepts2017/syllabus.pdf create mode 100644 www/teaching/discrete20/.htaccess create mode 100644 www/teaching/discrete20/.password create mode 100644 www/teaching/discrete20/extra.pdf create mode 100644 www/teaching/discrete20/hats.pdf create mode 100644 www/teaching/discrete20/index.html create mode 100644 www/teaching/discrete20/pairwise.pdf create mode 100644 www/teaching/discrete20/pie.pdf create mode 100644 www/teaching/discrete20/quiz11.pdf create mode 100644 www/teaching/discrete20/quiz12.pdf create mode 100644 www/teaching/discrete20/quiz13.pdf create mode 100644 www/teaching/discrete20/quiz14.pdf create mode 100644 www/teaching/discrete20/rec1.pdf create mode 100644 www/teaching/discrete20/rec10.pdf create mode 100644 www/teaching/discrete20/rec11.pdf create mode 100644 www/teaching/discrete20/rec12.pdf create mode 100644 www/teaching/discrete20/rec2.pdf create mode 100644 www/teaching/discrete20/rec4.pdf create mode 100644 www/teaching/discrete20/rec5.pdf create mode 100644 www/teaching/discrete20/rec6.pdf create mode 100644 www/teaching/discrete20/rec7.pdf create mode 100644 www/teaching/discrete20/rec8.pdf create mode 100644 www/teaching/discrete20/rec9.pdf create mode 100644 www/teaching/discrete2016/disc_rec_1.pdf create mode 100644 www/teaching/discrete2016/disc_rec_10.pdf create mode 100644 www/teaching/discrete2016/disc_rec_11.pdf create mode 100644 www/teaching/discrete2016/disc_rec_13.pdf create mode 100644 www/teaching/discrete2016/disc_rec_14.pdf create mode 100644 www/teaching/discrete2016/disc_rec_2.pdf create mode 100644 www/teaching/discrete2016/disc_rec_3.pdf create mode 100644 www/teaching/discrete2016/disc_rec_4.pdf create mode 100644 www/teaching/discrete2016/disc_rec_6.pdf create mode 100644 www/teaching/discrete2016/disc_rec_7.pdf create mode 100644 www/teaching/discrete2016/disc_rec_8.pdf create mode 100644 www/teaching/discrete2016/index.html create mode 100644 www/teaching/graphs2022/.htaccess create mode 100644 www/teaching/graphs2022/_notation.html create mode 100644 www/teaching/graphs2022/dilworth.pdf create mode 100644 www/teaching/graphs2022/ds1.pdf create mode 100644 www/teaching/graphs2022/ds2.pdf create mode 100644 www/teaching/graphs2022/ds3.pdf create mode 100644 www/teaching/graphs2022/ds4.pdf create mode 100644 www/teaching/graphs2022/ds5.pdf create mode 100644 www/teaching/graphs2022/ds6.pdf create mode 100644 www/teaching/graphs2022/dyck.pdf create mode 100644 www/teaching/graphs2022/extra_01-18.pdf create mode 100644 www/teaching/graphs2022/extra_01-20.pdf create mode 100644 www/teaching/graphs2022/extra_01-25.pdf create mode 100644 www/teaching/graphs2022/extra_01-27.pdf create mode 100644 www/teaching/graphs2022/extra_02-01.pdf create mode 100644 www/teaching/graphs2022/extra_02-08.pdf create mode 100644 www/teaching/graphs2022/extra_02-10.pdf create mode 100644 www/teaching/graphs2022/extra_02-24.pdf create mode 100644 www/teaching/graphs2022/extra_03-01.pdf create mode 100644 www/teaching/graphs2022/extra_03-03.pdf create mode 100644 www/teaching/graphs2022/extra_03-22.pdf create mode 100644 www/teaching/graphs2022/extra_03-29.pdf create mode 100644 www/teaching/graphs2022/extra_03-31.pdf create mode 100644 www/teaching/graphs2022/extra_04-05.pdf create mode 100644 www/teaching/graphs2022/extra_04-07.pdf create mode 100644 www/teaching/graphs2022/extra_04-12.pdf create mode 100644 www/teaching/graphs2022/extra_04-14.pdf create mode 100644 www/teaching/graphs2022/extra_04-19.pdf create mode 100644 www/teaching/graphs2022/extra_04-26.pdf create mode 100644 www/teaching/graphs2022/extra_04-28.pdf create mode 100644 www/teaching/graphs2022/extra_05-03.pdf create mode 100644 www/teaching/graphs2022/fun.pdf create mode 100644 www/teaching/graphs2022/hw1.pdf create mode 100644 www/teaching/graphs2022/hw1.tex create mode 100644 www/teaching/graphs2022/hw10.pdf create mode 100644 www/teaching/graphs2022/hw10.tex create mode 100644 www/teaching/graphs2022/hw11.pdf create mode 100644 www/teaching/graphs2022/hw11.tex create mode 100644 www/teaching/graphs2022/hw12.pdf create mode 100644 www/teaching/graphs2022/hw12.tex create mode 100644 www/teaching/graphs2022/hw13.pdf create mode 100644 www/teaching/graphs2022/hw13.tex create mode 100644 www/teaching/graphs2022/hw2.pdf create mode 100644 www/teaching/graphs2022/hw2.tex create mode 100644 www/teaching/graphs2022/hw3.pdf create mode 100644 www/teaching/graphs2022/hw3.tex create mode 100644 www/teaching/graphs2022/hw4.pdf create mode 100644 www/teaching/graphs2022/hw4.tex create mode 100644 www/teaching/graphs2022/hw5.pdf create mode 100644 www/teaching/graphs2022/hw5.tex create mode 100644 www/teaching/graphs2022/hw6.pdf create mode 100644 www/teaching/graphs2022/hw6.tex create mode 100644 www/teaching/graphs2022/hw7.pdf create mode 100644 www/teaching/graphs2022/hw7.tex create mode 100644 www/teaching/graphs2022/hw8.pdf create mode 100644 www/teaching/graphs2022/hw8.tex create mode 100644 www/teaching/graphs2022/hw9.pdf create mode 100644 www/teaching/graphs2022/hw9.tex create mode 100644 www/teaching/graphs2022/index.html create mode 100644 www/teaching/graphs2022/prufer.pdf create mode 100644 www/teaching/graphs2022/syllabus.pdf create mode 100644 www/teaching/lcs22/aldous_markov.pdf create mode 100644 www/teaching/lcs22/alexander_lcs.pdf create mode 100644 www/teaching/lcs22/alon_probcomb.pdf create mode 100644 www/teaching/lcs22/bukh_frogs.pdf create mode 100644 www/teaching/lcs22/chvatal_lcs.pdf create mode 100644 www/teaching/lcs22/hollander_coupling.pdf create mode 100644 www/teaching/lcs22/index.html create mode 100644 www/teaching/lcs22/kiwi_lcs.pdf create mode 100644 www/teaching/lcs22/lueker_lcs.pdf create mode 100644 www/teaching/lcs22/norris_markov.pdf create mode 100644 www/teaching/matrices2019/.htaccess create mode 100644 www/teaching/matrices2019/.password create mode 100644 www/teaching/matrices2019/basis.pdf create mode 100644 www/teaching/matrices2019/dsw1.pdf create mode 100644 www/teaching/matrices2019/dsw2.pdf create mode 100644 www/teaching/matrices2019/dsw3.pdf create mode 100644 www/teaching/matrices2019/dsw4.pdf create mode 100644 www/teaching/matrices2019/dsw5.pdf create mode 100644 www/teaching/matrices2019/dsw6.pdf create mode 100644 www/teaching/matrices2019/hw1.pdf create mode 100644 www/teaching/matrices2019/hw10.pdf create mode 100644 www/teaching/matrices2019/hw11.pdf create mode 100644 www/teaching/matrices2019/hw2.pdf create mode 100644 www/teaching/matrices2019/hw3.pdf create mode 100644 www/teaching/matrices2019/hw4.pdf create mode 100644 www/teaching/matrices2019/hw5.pdf create mode 100644 www/teaching/matrices2019/hw6.pdf create mode 100644 www/teaching/matrices2019/hw7.pdf create mode 100644 www/teaching/matrices2019/hw8.pdf create mode 100644 www/teaching/matrices2019/hw9.pdf create mode 100644 www/teaching/matrices2019/index.html create mode 100644 www/teaching/matrices2019/syllabus.pdf 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 + +--- + +

MATH 595: Algebraic Methods in Combinatorics

+ +

+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. +

+ +
+ +

Resources

+ diff --git a/www/teaching/algmethods22/lovasz_shannon.pdf b/www/teaching/algmethods22/lovasz_shannon.pdf new file mode 100644 index 0000000..021b4e2 Binary files /dev/null and b/www/teaching/algmethods22/lovasz_shannon.pdf differ diff --git a/www/teaching/calcI21/challenge1.pdf b/www/teaching/calcI21/challenge1.pdf new file mode 100644 index 0000000..857be98 Binary files /dev/null and b/www/teaching/calcI21/challenge1.pdf differ diff --git a/www/teaching/calcI21/challenge2.pdf b/www/teaching/calcI21/challenge2.pdf new file mode 100644 index 0000000..325db58 Binary files /dev/null and b/www/teaching/calcI21/challenge2.pdf differ diff --git a/www/teaching/calcI21/challenge3.pdf b/www/teaching/calcI21/challenge3.pdf new file mode 100644 index 0000000..0a5dfec Binary files /dev/null and b/www/teaching/calcI21/challenge3.pdf differ 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 + +--- + +

MATH 165: Calculus I

+

Recorded lectures

+

Other materials available on Canvas

+
+
Lecture
+
Gilman 1652
+
MRF 11:00–11:50am
+
Recitation
+
Gilman 1652
+
T 11:00–11:50am
+
+
+
+ +

Challenge Problem Sets

+ + 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 + +order allow,deny +deny from all + + +require user concepts + 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 new file mode 100644 index 0000000..a9455fd Binary files /dev/null and b/www/teaching/concepts2017/DSW2.pdf differ diff --git a/www/teaching/concepts2017/DSW3.pdf b/www/teaching/concepts2017/DSW3.pdf new file mode 100644 index 0000000..3677576 Binary files /dev/null and b/www/teaching/concepts2017/DSW3.pdf differ diff --git a/www/teaching/concepts2017/DSW4.pdf b/www/teaching/concepts2017/DSW4.pdf new file mode 100644 index 0000000..8d3d285 Binary files /dev/null and b/www/teaching/concepts2017/DSW4.pdf differ diff --git a/www/teaching/concepts2017/DSW5.pdf b/www/teaching/concepts2017/DSW5.pdf new file mode 100644 index 0000000..35dbf05 Binary files /dev/null and b/www/teaching/concepts2017/DSW5.pdf differ diff --git a/www/teaching/concepts2017/NHW1.pdf b/www/teaching/concepts2017/NHW1.pdf new file mode 100644 index 0000000..8b8923f Binary files /dev/null and b/www/teaching/concepts2017/NHW1.pdf differ diff --git a/www/teaching/concepts2017/NHW10.pdf b/www/teaching/concepts2017/NHW10.pdf new file mode 100644 index 0000000..6ea8677 Binary files /dev/null and b/www/teaching/concepts2017/NHW10.pdf differ diff --git a/www/teaching/concepts2017/NHW10re.pdf b/www/teaching/concepts2017/NHW10re.pdf new file mode 100644 index 0000000..8b82127 Binary files /dev/null and b/www/teaching/concepts2017/NHW10re.pdf differ diff --git a/www/teaching/concepts2017/NHW11.pdf b/www/teaching/concepts2017/NHW11.pdf new file mode 100644 index 0000000..7a59181 Binary files /dev/null and b/www/teaching/concepts2017/NHW11.pdf differ diff --git a/www/teaching/concepts2017/NHW11re.pdf b/www/teaching/concepts2017/NHW11re.pdf new file mode 100644 index 0000000..2f9b05c Binary files /dev/null and b/www/teaching/concepts2017/NHW11re.pdf differ diff --git a/www/teaching/concepts2017/NHW12.pdf b/www/teaching/concepts2017/NHW12.pdf new file mode 100644 index 0000000..412a687 Binary files /dev/null and b/www/teaching/concepts2017/NHW12.pdf differ diff --git a/www/teaching/concepts2017/NHW12re.pdf b/www/teaching/concepts2017/NHW12re.pdf new file mode 100644 index 0000000..5f57cfc Binary files /dev/null and b/www/teaching/concepts2017/NHW12re.pdf differ diff --git a/www/teaching/concepts2017/NHW13.pdf b/www/teaching/concepts2017/NHW13.pdf new file mode 100644 index 0000000..8208b80 Binary files /dev/null and b/www/teaching/concepts2017/NHW13.pdf differ diff --git a/www/teaching/concepts2017/NHW13re.pdf b/www/teaching/concepts2017/NHW13re.pdf new file mode 100644 index 0000000..5c47c87 Binary files /dev/null and b/www/teaching/concepts2017/NHW13re.pdf differ diff --git a/www/teaching/concepts2017/NHW1re.pdf b/www/teaching/concepts2017/NHW1re.pdf new file mode 100644 index 0000000..f6271b5 Binary files /dev/null and b/www/teaching/concepts2017/NHW1re.pdf differ diff --git a/www/teaching/concepts2017/NHW2.pdf b/www/teaching/concepts2017/NHW2.pdf new file mode 100644 index 0000000..08cdba4 Binary files /dev/null and b/www/teaching/concepts2017/NHW2.pdf differ diff --git a/www/teaching/concepts2017/NHW2re.pdf b/www/teaching/concepts2017/NHW2re.pdf new file mode 100644 index 0000000..135fa2a Binary files /dev/null and b/www/teaching/concepts2017/NHW2re.pdf differ diff --git a/www/teaching/concepts2017/NHW3.pdf b/www/teaching/concepts2017/NHW3.pdf new file mode 100644 index 0000000..c8fe5b9 Binary files /dev/null and b/www/teaching/concepts2017/NHW3.pdf differ diff --git a/www/teaching/concepts2017/NHW3re.pdf b/www/teaching/concepts2017/NHW3re.pdf new file mode 100644 index 0000000..7171728 Binary files /dev/null and b/www/teaching/concepts2017/NHW3re.pdf differ diff --git a/www/teaching/concepts2017/NHW4.pdf b/www/teaching/concepts2017/NHW4.pdf new file mode 100644 index 0000000..694630b Binary files /dev/null and b/www/teaching/concepts2017/NHW4.pdf differ diff --git a/www/teaching/concepts2017/NHW4re.pdf b/www/teaching/concepts2017/NHW4re.pdf new file mode 100644 index 0000000..a07c726 Binary files /dev/null and b/www/teaching/concepts2017/NHW4re.pdf differ diff --git a/www/teaching/concepts2017/NHW5.pdf b/www/teaching/concepts2017/NHW5.pdf new file mode 100644 index 0000000..f196413 Binary files /dev/null and b/www/teaching/concepts2017/NHW5.pdf differ diff --git a/www/teaching/concepts2017/NHW5re.pdf b/www/teaching/concepts2017/NHW5re.pdf new file mode 100644 index 0000000..d41e140 Binary files /dev/null and b/www/teaching/concepts2017/NHW5re.pdf differ diff --git a/www/teaching/concepts2017/NHW6.pdf b/www/teaching/concepts2017/NHW6.pdf new file mode 100644 index 0000000..9d0b6ce Binary files /dev/null and b/www/teaching/concepts2017/NHW6.pdf differ diff --git a/www/teaching/concepts2017/NHW6re.pdf b/www/teaching/concepts2017/NHW6re.pdf new file mode 100644 index 0000000..920d648 Binary files /dev/null and b/www/teaching/concepts2017/NHW6re.pdf differ diff --git a/www/teaching/concepts2017/NHW7.pdf b/www/teaching/concepts2017/NHW7.pdf new file mode 100644 index 0000000..58ec984 Binary files /dev/null and b/www/teaching/concepts2017/NHW7.pdf differ diff --git a/www/teaching/concepts2017/NHW7re.pdf b/www/teaching/concepts2017/NHW7re.pdf new file mode 100644 index 0000000..652ec00 Binary files /dev/null and b/www/teaching/concepts2017/NHW7re.pdf differ diff --git a/www/teaching/concepts2017/NHW8.pdf b/www/teaching/concepts2017/NHW8.pdf new file mode 100644 index 0000000..4eac8c0 Binary files /dev/null and b/www/teaching/concepts2017/NHW8.pdf differ diff --git a/www/teaching/concepts2017/NHW8re.pdf b/www/teaching/concepts2017/NHW8re.pdf new file mode 100644 index 0000000..c15f90e Binary files /dev/null and b/www/teaching/concepts2017/NHW8re.pdf differ diff --git a/www/teaching/concepts2017/NHW9.pdf b/www/teaching/concepts2017/NHW9.pdf new file mode 100644 index 0000000..90cc837 Binary files /dev/null and b/www/teaching/concepts2017/NHW9.pdf differ diff --git a/www/teaching/concepts2017/NHW9re.pdf b/www/teaching/concepts2017/NHW9re.pdf new file mode 100644 index 0000000..aff2ac3 Binary files /dev/null and b/www/teaching/concepts2017/NHW9re.pdf differ diff --git a/www/teaching/concepts2017/Sullivan_Text.pdf b/www/teaching/concepts2017/Sullivan_Text.pdf new file mode 100644 index 0000000..996f55c Binary files /dev/null and b/www/teaching/concepts2017/Sullivan_Text.pdf differ diff --git a/www/teaching/concepts2017/WHW1.pdf b/www/teaching/concepts2017/WHW1.pdf new file mode 100644 index 0000000..b80ab46 Binary files /dev/null and b/www/teaching/concepts2017/WHW1.pdf differ diff --git a/www/teaching/concepts2017/WHW2.pdf b/www/teaching/concepts2017/WHW2.pdf new file mode 100644 index 0000000..9b974c4 Binary files /dev/null and b/www/teaching/concepts2017/WHW2.pdf differ diff --git a/www/teaching/concepts2017/WHW2re.pdf b/www/teaching/concepts2017/WHW2re.pdf new file mode 100644 index 0000000..35d7e1b Binary files /dev/null and b/www/teaching/concepts2017/WHW2re.pdf differ diff --git a/www/teaching/concepts2017/WHW3.pdf b/www/teaching/concepts2017/WHW3.pdf new file mode 100644 index 0000000..1e9624f Binary files /dev/null and b/www/teaching/concepts2017/WHW3.pdf differ diff --git a/www/teaching/concepts2017/WHW3re.pdf b/www/teaching/concepts2017/WHW3re.pdf new file mode 100644 index 0000000..d2ffbf2 Binary files /dev/null and b/www/teaching/concepts2017/WHW3re.pdf differ diff --git a/www/teaching/concepts2017/WHW4.pdf b/www/teaching/concepts2017/WHW4.pdf new file mode 100644 index 0000000..23fd6ef Binary files /dev/null and b/www/teaching/concepts2017/WHW4.pdf differ diff --git a/www/teaching/concepts2017/WHW4re.pdf b/www/teaching/concepts2017/WHW4re.pdf new file mode 100644 index 0000000..5b72b19 Binary files /dev/null and b/www/teaching/concepts2017/WHW4re.pdf differ diff --git a/www/teaching/concepts2017/WHW5.pdf b/www/teaching/concepts2017/WHW5.pdf new file mode 100644 index 0000000..ad91b26 Binary files /dev/null and b/www/teaching/concepts2017/WHW5.pdf differ diff --git a/www/teaching/concepts2017/WHW5re.pdf b/www/teaching/concepts2017/WHW5re.pdf new file mode 100644 index 0000000..59802c9 Binary files /dev/null and b/www/teaching/concepts2017/WHW5re.pdf differ 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 + +--- + +

21-127: Concepts of Mathematics

+

Course Information

+
+
Lecture
+
MTWRF 9:00-10:20
+
Office hours
+
MTWRF 1:30-2:30
+
+ +
+
+ +

Schedule and Assignments

+

Homework Template

+

Weekly assignments are due on the Friday of their respective weeks.
+Nightly assignments are due on the date by which they are posted.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Week #1WHW1
July 3Introduction to mathematical thinking and the need for formal arguments
July 4No Class
July 5Introduction to propositional logic
July 6Propositional logic and elementary proof techniquesNHW1 | Rewrite
July 7Elementary proof techniques
Week #2WHW2 | Rewrite
July 10Sets: set operations and containment argumentsNHW2 | Rewrite
July 11Sets: indexed operationsNHW3 | Rewrite
July 12Cartesian products and functionsNHW4 | Rewrite
July 13Functions: images and preimages
July 14Discussion session
Week #3WHW3 | Rewrite
July 17Induction to inductionNHW5 | Rewrite
July 18Induction: examples and pitfallsNHW6 | Rewrite
July 19Induction: strong and weak inductionNHW7 | Rewrite
July 20Induction: more examples
July 21Discussion session
Week #4WHW4 | Rewrite
July 24Properties of the integers: divisibility and primesNHW8 | Rewrite
July 25Properties of the integers: prime factorization and division algorithmNHW9 | Rewrite
July 26Modular arithmeticNHW10 | Rewrite
July 27Modular arithmetic: theorems and diophantine equationsOffice hours in 6203
July 28Discussion session: introducing Joe Briggs!Office hours in 6203
Week #5WHW5 | Rewrite
July 31Back to functions: meet George JectionNHW11 | Rewrite
Aug 1Cardinality of setsNHW12 | Rewrite
Aug 2Cardinality: to infinity and beyondNHW13 | Rewrite
Aug 3Counting with bijections
Aug 4Discussion session
Week #6No homework this week. Focus on studying and rewriting assignments
Aug 7The pigeonhole principle
Aug 8Double counting proofs
Aug 9Funzies: winning strategies for games, etc
Aug 10Review
Aug 11Final Exam
diff --git a/www/teaching/concepts2017/review.pdf b/www/teaching/concepts2017/review.pdf new file mode 100644 index 0000000..ebc3b03 Binary files /dev/null and b/www/teaching/concepts2017/review.pdf differ diff --git a/www/teaching/concepts2017/syllabus.pdf b/www/teaching/concepts2017/syllabus.pdf new file mode 100644 index 0000000..691014c Binary files /dev/null and b/www/teaching/concepts2017/syllabus.pdf differ 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 + +order allow,deny +deny from all + + +require user quiz11 + + +require user quiz12 + + +require user quiz13 + + +require user quiz14 + 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 new file mode 100644 index 0000000..a23a683 Binary files /dev/null and b/www/teaching/discrete20/extra.pdf differ diff --git a/www/teaching/discrete20/hats.pdf b/www/teaching/discrete20/hats.pdf new file mode 100644 index 0000000..53446fd Binary files /dev/null and b/www/teaching/discrete20/hats.pdf differ 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 + +--- + +

21-228: Discrete Mathematics

+ +

Official course webpage

+ +

Class meetings:

+ + + + + + + + + + + + + + + + + + + + +
Lecture§A§B§C
MWF 1:30–2:20T 8:30–9:20T 9:30–10:20T 4:30–5:30
Hamerschlag B131Posner 146Scaife 219Baker 235A
+ +

Office hours:

+ + + + + + + + + + + + + + + + + +
TomChrisSunny
W 2:30–4:30R 12:30–2:30R 4:30–5:30
Wean 6113Wean 6201Wean 6215
+ +
+ +
+ +

Recitation notes

+ +

+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. +

+ +

+I type these up quickly, so please let me know if you find any mistakes! +

+ + + +
+
+ +
Supplementary materials
+ + diff --git a/www/teaching/discrete20/pairwise.pdf b/www/teaching/discrete20/pairwise.pdf new file mode 100644 index 0000000..599101d Binary files /dev/null and b/www/teaching/discrete20/pairwise.pdf differ diff --git a/www/teaching/discrete20/pie.pdf b/www/teaching/discrete20/pie.pdf new file mode 100644 index 0000000..ca487f4 Binary files /dev/null and b/www/teaching/discrete20/pie.pdf differ diff --git a/www/teaching/discrete20/quiz11.pdf b/www/teaching/discrete20/quiz11.pdf new file mode 100644 index 0000000..7c1531f Binary files /dev/null and b/www/teaching/discrete20/quiz11.pdf differ diff --git a/www/teaching/discrete20/quiz12.pdf b/www/teaching/discrete20/quiz12.pdf new file mode 100644 index 0000000..168d8c7 Binary files /dev/null and b/www/teaching/discrete20/quiz12.pdf differ diff --git a/www/teaching/discrete20/quiz13.pdf b/www/teaching/discrete20/quiz13.pdf new file mode 100644 index 0000000..5b642cb Binary files /dev/null and b/www/teaching/discrete20/quiz13.pdf differ diff --git a/www/teaching/discrete20/quiz14.pdf b/www/teaching/discrete20/quiz14.pdf new file mode 100644 index 0000000..bf181a6 Binary files /dev/null and b/www/teaching/discrete20/quiz14.pdf differ diff --git a/www/teaching/discrete20/rec1.pdf b/www/teaching/discrete20/rec1.pdf new file mode 100644 index 0000000..42761b7 Binary files /dev/null and b/www/teaching/discrete20/rec1.pdf differ diff --git a/www/teaching/discrete20/rec10.pdf b/www/teaching/discrete20/rec10.pdf new file mode 100644 index 0000000..cd649a2 Binary files /dev/null and b/www/teaching/discrete20/rec10.pdf differ diff --git a/www/teaching/discrete20/rec11.pdf b/www/teaching/discrete20/rec11.pdf new file mode 100644 index 0000000..8a4b99f Binary files /dev/null and b/www/teaching/discrete20/rec11.pdf differ diff --git a/www/teaching/discrete20/rec12.pdf b/www/teaching/discrete20/rec12.pdf new file mode 100644 index 0000000..f54f3d2 Binary files /dev/null and b/www/teaching/discrete20/rec12.pdf differ diff --git a/www/teaching/discrete20/rec2.pdf b/www/teaching/discrete20/rec2.pdf new file mode 100644 index 0000000..b96fae3 Binary files /dev/null and b/www/teaching/discrete20/rec2.pdf differ diff --git a/www/teaching/discrete20/rec4.pdf b/www/teaching/discrete20/rec4.pdf new file mode 100644 index 0000000..de2eba8 Binary files /dev/null and b/www/teaching/discrete20/rec4.pdf differ diff --git a/www/teaching/discrete20/rec5.pdf b/www/teaching/discrete20/rec5.pdf new file mode 100644 index 0000000..eee55aa Binary files /dev/null and b/www/teaching/discrete20/rec5.pdf differ diff --git a/www/teaching/discrete20/rec6.pdf b/www/teaching/discrete20/rec6.pdf new file mode 100644 index 0000000..d124151 Binary files /dev/null and b/www/teaching/discrete20/rec6.pdf differ diff --git a/www/teaching/discrete20/rec7.pdf b/www/teaching/discrete20/rec7.pdf new file mode 100644 index 0000000..408249b Binary files /dev/null and b/www/teaching/discrete20/rec7.pdf differ diff --git a/www/teaching/discrete20/rec8.pdf b/www/teaching/discrete20/rec8.pdf new file mode 100644 index 0000000..4ad894a Binary files /dev/null and b/www/teaching/discrete20/rec8.pdf differ diff --git a/www/teaching/discrete20/rec9.pdf b/www/teaching/discrete20/rec9.pdf new file mode 100644 index 0000000..651b04a Binary files /dev/null and b/www/teaching/discrete20/rec9.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_1.pdf b/www/teaching/discrete2016/disc_rec_1.pdf new file mode 100644 index 0000000..b24d97c Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_1.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_10.pdf b/www/teaching/discrete2016/disc_rec_10.pdf new file mode 100644 index 0000000..3782021 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_10.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_11.pdf b/www/teaching/discrete2016/disc_rec_11.pdf new file mode 100644 index 0000000..b1ee3e7 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_11.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_13.pdf b/www/teaching/discrete2016/disc_rec_13.pdf new file mode 100644 index 0000000..e6209b6 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_13.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_14.pdf b/www/teaching/discrete2016/disc_rec_14.pdf new file mode 100644 index 0000000..3ab5dc6 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_14.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_2.pdf b/www/teaching/discrete2016/disc_rec_2.pdf new file mode 100644 index 0000000..59bf43a Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_2.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_3.pdf b/www/teaching/discrete2016/disc_rec_3.pdf new file mode 100644 index 0000000..bd54977 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_3.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_4.pdf b/www/teaching/discrete2016/disc_rec_4.pdf new file mode 100644 index 0000000..a97b8b2 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_4.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_6.pdf b/www/teaching/discrete2016/disc_rec_6.pdf new file mode 100644 index 0000000..5d7ee77 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_6.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_7.pdf b/www/teaching/discrete2016/disc_rec_7.pdf new file mode 100644 index 0000000..7e29ce8 Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_7.pdf differ diff --git a/www/teaching/discrete2016/disc_rec_8.pdf b/www/teaching/discrete2016/disc_rec_8.pdf new file mode 100644 index 0000000..8e40e8a Binary files /dev/null and b/www/teaching/discrete2016/disc_rec_8.pdf differ 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 + +--- + +

21-228: Discrete Mathematics

+

Official Course Webpage

+
+
Lecture
+
MWF 11:30-12:20
+
Recitation for §A
+
T 8:30-9:20
+
Recitation for §B
+
T 9:30-10:20
+
Tom Bohman's office hours
+
W 1:30-3:00
+
My office hours
+
Th 1:00-3:00
+
+
+
+ +

Recitation notes

+

Please let me know if I have made any mistakes in writing these up.

+ +
+
+ +

For more information on the "matching method" for doing inclusion-exclusion, see the following resource, which refers to this method as "DIE."
+ An alternate approach to alternating sums: A method to DIE for.

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 + + order allow,deny + deny from all + + + require user graphs + 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 @@ +

Quick notation

+

+This list will grow throughout the semester. +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
NotationMeaning
$[n]$$\{1,\dots,n\}$ (Note: $[0]=\varnothing$)
$2^X$ where $X$ is a setpower-set of $X$ (nb: if $X$ is finite, then $|2^X|=2^{|X|}$)
${X\choose k}$ where $X$ is a set$\{S\in 2^X:|S|=k\}$ (nb: if $X$ is finite, then $|{X\choose k}|={|X|\choose k}$)
$A\sqcup B$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.)
$V(G)$vertex set of $G$
$E(G)$edge set of $G$
$K_n$clique on $n$ vertices
$C_n$cycle on $n$ vertices
$P_n$path on $n$ vertices
$K_{m,n}$complete bipartite graph with parts of sizes $m$ and $n$
$K_{n_1,n_2,\dots,n_t}$complete $t$-partite graph with parts of sizes $n_1,n_2,\dots,n_t$
$\overline{G}$complement of $G$
$G-v$ where $v$ is a vertex of $G$remove the vertex $v$ along with any incident edges from $G$
$G-e$ where $e$ is an edge of $G$remove the edge $e$ from $G$, but keep all vertices
$G+e$ where $e$ is an edge not in $G$add the edge $e$ to $G$
$G-U$ where $U$ is either a set of vertices or a set of edges of $G$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. +
$G[X]$ where $X\subseteq V(G)$subgraph of $G$ induced by $X$ (Note: $G[X]=G-(V(G)\setminus X)$)
$L(G)$the line graph of $G$
$G\cup H$ or $G\sqcup H$disjoint union of $G$ and $H$ (Note: I will always use $\sqcup$ since it reinforces the disjointness)
$G+H$ or $G\vee H$join of $G$ and $H$
$G\mathbin\square H$ or $G\times H$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$.)
$d(u,v)$distance between vertices $u$ and $v$
$N(v)$neighborhood of $v$
$\deg v$degree of the vertex $v$
$\Delta(G)$maximum degree of $G$
$\delta(G)$minimum degree of $G$
$\deg^+ v$ or $\operatorname{od}v$out-degree of the vertex $v$ in a digraph (Note: I will never use $\operatorname{od}$ since that's just dumb)
$\deg^- v$ or $\operatorname{id}v$in-degree of the vertex $v$ in a digraph (Note: I will never use $\operatorname{id}$ since that's just dumb)
$G\cong H$$G$ and $H$ are isomorphic graphs
$\operatorname{Aut}(G)$automorphism group of $G$
$\kappa(G)$vertex-connectivity of $G$
$\lambda(G)$edge-connectivity of $G$
$\alpha(G)$independence number of $G$
$\omega(G)$clique number of $G$
$\alpha'(G)$matching number/edge-independence number of $G$, i.e. the largest matching in $G$
$\beta(G)$vertex-cover number of $G$, i.e. min number of vertices that touch all edges
$\beta'(G)$edge-cover number of $G$, i.e. min number of edges that touch all vertices
$\chi(G)$chromatic number of $G$
$\chi'(G)$edge-chromatic number/chromatic index of $G$, i.e. chromatic number of $L(G)$
$R(m,n)$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$
+ +

+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. +

diff --git a/www/teaching/graphs2022/dilworth.pdf b/www/teaching/graphs2022/dilworth.pdf new file mode 100644 index 0000000..2683488 Binary files /dev/null and b/www/teaching/graphs2022/dilworth.pdf differ diff --git a/www/teaching/graphs2022/ds1.pdf b/www/teaching/graphs2022/ds1.pdf new file mode 100644 index 0000000..1180fc1 Binary files /dev/null and b/www/teaching/graphs2022/ds1.pdf differ diff --git a/www/teaching/graphs2022/ds2.pdf b/www/teaching/graphs2022/ds2.pdf new file mode 100644 index 0000000..10bcc75 Binary files /dev/null and b/www/teaching/graphs2022/ds2.pdf differ diff --git a/www/teaching/graphs2022/ds3.pdf b/www/teaching/graphs2022/ds3.pdf new file mode 100644 index 0000000..3955084 Binary files /dev/null and b/www/teaching/graphs2022/ds3.pdf differ diff --git a/www/teaching/graphs2022/ds4.pdf b/www/teaching/graphs2022/ds4.pdf new file mode 100644 index 0000000..bc1fd62 Binary files /dev/null and b/www/teaching/graphs2022/ds4.pdf differ diff --git a/www/teaching/graphs2022/ds5.pdf b/www/teaching/graphs2022/ds5.pdf new file mode 100644 index 0000000..2f2afc6 Binary files /dev/null and b/www/teaching/graphs2022/ds5.pdf differ diff --git a/www/teaching/graphs2022/ds6.pdf b/www/teaching/graphs2022/ds6.pdf new file mode 100644 index 0000000..189b080 Binary files /dev/null and b/www/teaching/graphs2022/ds6.pdf differ diff --git a/www/teaching/graphs2022/dyck.pdf b/www/teaching/graphs2022/dyck.pdf new file mode 100644 index 0000000..71cbd1e Binary files /dev/null and b/www/teaching/graphs2022/dyck.pdf differ diff --git a/www/teaching/graphs2022/extra_01-18.pdf b/www/teaching/graphs2022/extra_01-18.pdf new file mode 100644 index 0000000..184cdc6 Binary files /dev/null and b/www/teaching/graphs2022/extra_01-18.pdf differ diff --git a/www/teaching/graphs2022/extra_01-20.pdf b/www/teaching/graphs2022/extra_01-20.pdf new file mode 100644 index 0000000..f35dd5a Binary files /dev/null and b/www/teaching/graphs2022/extra_01-20.pdf differ diff --git a/www/teaching/graphs2022/extra_01-25.pdf b/www/teaching/graphs2022/extra_01-25.pdf new file mode 100644 index 0000000..13935d8 Binary files /dev/null and b/www/teaching/graphs2022/extra_01-25.pdf differ diff --git a/www/teaching/graphs2022/extra_01-27.pdf b/www/teaching/graphs2022/extra_01-27.pdf new file mode 100644 index 0000000..04a6a6d Binary files /dev/null and b/www/teaching/graphs2022/extra_01-27.pdf differ diff --git a/www/teaching/graphs2022/extra_02-01.pdf b/www/teaching/graphs2022/extra_02-01.pdf new file mode 100644 index 0000000..498d20f Binary files /dev/null and b/www/teaching/graphs2022/extra_02-01.pdf differ diff --git a/www/teaching/graphs2022/extra_02-08.pdf b/www/teaching/graphs2022/extra_02-08.pdf new file mode 100644 index 0000000..b689f2c Binary files /dev/null and b/www/teaching/graphs2022/extra_02-08.pdf differ diff --git a/www/teaching/graphs2022/extra_02-10.pdf b/www/teaching/graphs2022/extra_02-10.pdf new file mode 100644 index 0000000..f087b4b Binary files /dev/null and b/www/teaching/graphs2022/extra_02-10.pdf differ diff --git a/www/teaching/graphs2022/extra_02-24.pdf b/www/teaching/graphs2022/extra_02-24.pdf new file mode 100644 index 0000000..74d8c0b Binary files /dev/null and b/www/teaching/graphs2022/extra_02-24.pdf differ diff --git a/www/teaching/graphs2022/extra_03-01.pdf b/www/teaching/graphs2022/extra_03-01.pdf new file mode 100644 index 0000000..2877516 Binary files /dev/null and b/www/teaching/graphs2022/extra_03-01.pdf differ diff --git a/www/teaching/graphs2022/extra_03-03.pdf b/www/teaching/graphs2022/extra_03-03.pdf new file mode 100644 index 0000000..c6f8000 Binary files /dev/null and b/www/teaching/graphs2022/extra_03-03.pdf differ diff --git a/www/teaching/graphs2022/extra_03-22.pdf b/www/teaching/graphs2022/extra_03-22.pdf new file mode 100644 index 0000000..63ad3a0 Binary files /dev/null and b/www/teaching/graphs2022/extra_03-22.pdf differ diff --git a/www/teaching/graphs2022/extra_03-29.pdf b/www/teaching/graphs2022/extra_03-29.pdf new file mode 100644 index 0000000..d7ce789 Binary files /dev/null and b/www/teaching/graphs2022/extra_03-29.pdf differ diff --git a/www/teaching/graphs2022/extra_03-31.pdf b/www/teaching/graphs2022/extra_03-31.pdf new file mode 100644 index 0000000..1f7aeb3 Binary files /dev/null and b/www/teaching/graphs2022/extra_03-31.pdf differ diff --git a/www/teaching/graphs2022/extra_04-05.pdf b/www/teaching/graphs2022/extra_04-05.pdf new file mode 100644 index 0000000..28a35cc Binary files /dev/null and b/www/teaching/graphs2022/extra_04-05.pdf differ diff --git a/www/teaching/graphs2022/extra_04-07.pdf b/www/teaching/graphs2022/extra_04-07.pdf new file mode 100644 index 0000000..bfb08ea Binary files /dev/null and b/www/teaching/graphs2022/extra_04-07.pdf differ diff --git a/www/teaching/graphs2022/extra_04-12.pdf b/www/teaching/graphs2022/extra_04-12.pdf new file mode 100644 index 0000000..4624e16 Binary files /dev/null and b/www/teaching/graphs2022/extra_04-12.pdf differ diff --git a/www/teaching/graphs2022/extra_04-14.pdf b/www/teaching/graphs2022/extra_04-14.pdf new file mode 100644 index 0000000..47072d7 Binary files /dev/null and b/www/teaching/graphs2022/extra_04-14.pdf differ diff --git a/www/teaching/graphs2022/extra_04-19.pdf b/www/teaching/graphs2022/extra_04-19.pdf new file mode 100644 index 0000000..23b78b0 Binary files /dev/null and b/www/teaching/graphs2022/extra_04-19.pdf differ diff --git a/www/teaching/graphs2022/extra_04-26.pdf b/www/teaching/graphs2022/extra_04-26.pdf new file mode 100644 index 0000000..dfb0e2b Binary files /dev/null and b/www/teaching/graphs2022/extra_04-26.pdf differ diff --git a/www/teaching/graphs2022/extra_04-28.pdf b/www/teaching/graphs2022/extra_04-28.pdf new file mode 100644 index 0000000..ba0ce2e Binary files /dev/null and b/www/teaching/graphs2022/extra_04-28.pdf differ diff --git a/www/teaching/graphs2022/extra_05-03.pdf b/www/teaching/graphs2022/extra_05-03.pdf new file mode 100644 index 0000000..6fe7d53 Binary files /dev/null and b/www/teaching/graphs2022/extra_05-03.pdf differ diff --git a/www/teaching/graphs2022/fun.pdf b/www/teaching/graphs2022/fun.pdf new file mode 100644 index 0000000..a9a34ec Binary files /dev/null and b/www/teaching/graphs2022/fun.pdf differ diff --git a/www/teaching/graphs2022/hw1.pdf b/www/teaching/graphs2022/hw1.pdf new file mode 100644 index 0000000..dfea1fb Binary files /dev/null and b/www/teaching/graphs2022/hw1.pdf differ 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 new file mode 100644 index 0000000..3655b55 Binary files /dev/null and b/www/teaching/graphs2022/hw10.pdf differ 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 new file mode 100644 index 0000000..1b0be88 Binary files /dev/null and b/www/teaching/graphs2022/hw11.pdf differ 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 new file mode 100644 index 0000000..d4be075 Binary files /dev/null and b/www/teaching/graphs2022/hw12.pdf differ 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)}