diff options
63 files changed, 21 insertions, 2528 deletions
diff --git a/www/img/cmu_logo.png b/www/img/cmu_logo.png Binary files differnew file mode 100644 index 0000000..770628c --- /dev/null +++ b/www/img/cmu_logo.png diff --git a/www/index.html b/www/index.html index 300ef63..462c324 100644 --- a/www/index.html +++ b/www/index.html @@ -25,7 +25,7 @@ short_title: Chris Wells <div class="employment"> <h6><b>PhD</b> in Algorithms, Combinatorics and Optimization</h6> - <img src="/img/cmu_seal.png" height=70 alt="CMU"> + <img src="/img/cmu_logo.png" height=70 alt="CMU"> <ul> <li>2020</li> <li>Carnegie Mellon University</li> @@ -35,7 +35,7 @@ short_title: Chris Wells <div class="employment"> <h6><b>MS</b> in Mathematics</h6> - <img src="/img/isu_seal.png" height=70 alt="ISU"> + <img src="/img/isu_logo.png" height=70 alt="ISU"> <ul> <li>2015</li> <li>Iowa State University</li> @@ -45,7 +45,7 @@ short_title: Chris Wells <div class="employment"> <h6><b>BS</b> in Mathematics</h6> - <img src="/img/isu_seal.png" height=70 alt="ISU"> + <img src="/img/isu_logo.png" height=70 alt="ISU"> <ul> <li>2014</li> <li>Iowa State University</li> @@ -58,7 +58,7 @@ short_title: Chris Wells <div class="employment"> <h6><b>Postdoctoral Research Associate</b></h6> - <img src="/img/au_logo.png" height=50 alt="AU"> + <img src="/img/au_logo.png" height=60 alt="AU"> <ul> <li>2023–Present</li> <li>Auburn University</li> @@ -66,12 +66,28 @@ short_title: Chris Wells </div> <div class="employment"> <h6><b>RTG Postdoctoral Research Associate</b></h6> - <img src="/img/isu_logo.png" height=50 alt="ISU"> + <img src="/img/isu_logo.png" height=60 alt="ISU"> <ul> <li>2020–2023</li> <li>Iowa State University</li> </ul> </div> + <div class="employment"> + <h6><b>Teaching Assistant</b></h6> + <img src="/img/cmu_logo.png" height=60 alt="CMU"> + <ul> + <li>2015–2020</li> + <li>Carnegie Mellon University</li> + </ul> + </div> + <div class="employment"> + <h6><b>Teaching Assistant</b></h6> + <img src="/img/isu_logo.png" height=60 alt="ISU"> + <ul> + <li>2014–2015</li> + <li>Iowa State University</li> + </ul> + </div> </div> diff --git a/www/teaching/graphs2022/.htaccess b/www/teaching/graphs2022/.htaccess deleted file mode 100644 index 722a33b..0000000 --- a/www/teaching/graphs2022/.htaccess +++ /dev/null @@ -1,10 +0,0 @@ -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 deleted file mode 100644 index 01f7e2a..0000000 --- a/www/teaching/graphs2022/_notation.html +++ /dev/null @@ -1,180 +0,0 @@ -<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 differdeleted file mode 100644 index 2683488..0000000 --- a/www/teaching/graphs2022/dilworth.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/ds1.pdf b/www/teaching/graphs2022/ds1.pdf Binary files differdeleted file mode 100644 index 1180fc1..0000000 --- a/www/teaching/graphs2022/ds1.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/ds2.pdf b/www/teaching/graphs2022/ds2.pdf Binary files differdeleted file mode 100644 index 10bcc75..0000000 --- a/www/teaching/graphs2022/ds2.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/ds3.pdf b/www/teaching/graphs2022/ds3.pdf Binary files differdeleted file mode 100644 index 3955084..0000000 --- a/www/teaching/graphs2022/ds3.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/ds4.pdf b/www/teaching/graphs2022/ds4.pdf Binary files differdeleted file mode 100644 index bc1fd62..0000000 --- a/www/teaching/graphs2022/ds4.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/ds5.pdf b/www/teaching/graphs2022/ds5.pdf Binary files differdeleted file mode 100644 index 2f2afc6..0000000 --- a/www/teaching/graphs2022/ds5.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/ds6.pdf b/www/teaching/graphs2022/ds6.pdf Binary files differdeleted file mode 100644 index 189b080..0000000 --- a/www/teaching/graphs2022/ds6.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/dyck.pdf b/www/teaching/graphs2022/dyck.pdf Binary files differdeleted file mode 100644 index 71cbd1e..0000000 --- a/www/teaching/graphs2022/dyck.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_01-18.pdf b/www/teaching/graphs2022/extra_01-18.pdf Binary files differdeleted file mode 100644 index 184cdc6..0000000 --- a/www/teaching/graphs2022/extra_01-18.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_01-20.pdf b/www/teaching/graphs2022/extra_01-20.pdf Binary files differdeleted file mode 100644 index f35dd5a..0000000 --- a/www/teaching/graphs2022/extra_01-20.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_01-25.pdf b/www/teaching/graphs2022/extra_01-25.pdf Binary files differdeleted file mode 100644 index 13935d8..0000000 --- a/www/teaching/graphs2022/extra_01-25.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_01-27.pdf b/www/teaching/graphs2022/extra_01-27.pdf Binary files differdeleted file mode 100644 index 04a6a6d..0000000 --- a/www/teaching/graphs2022/extra_01-27.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_02-01.pdf b/www/teaching/graphs2022/extra_02-01.pdf Binary files differdeleted file mode 100644 index 498d20f..0000000 --- a/www/teaching/graphs2022/extra_02-01.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_02-08.pdf b/www/teaching/graphs2022/extra_02-08.pdf Binary files differdeleted file mode 100644 index b689f2c..0000000 --- a/www/teaching/graphs2022/extra_02-08.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_02-10.pdf b/www/teaching/graphs2022/extra_02-10.pdf Binary files differdeleted file mode 100644 index f087b4b..0000000 --- a/www/teaching/graphs2022/extra_02-10.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_02-24.pdf b/www/teaching/graphs2022/extra_02-24.pdf Binary files differdeleted file mode 100644 index 74d8c0b..0000000 --- a/www/teaching/graphs2022/extra_02-24.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_03-01.pdf b/www/teaching/graphs2022/extra_03-01.pdf Binary files differdeleted file mode 100644 index 2877516..0000000 --- a/www/teaching/graphs2022/extra_03-01.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_03-03.pdf b/www/teaching/graphs2022/extra_03-03.pdf Binary files differdeleted file mode 100644 index c6f8000..0000000 --- a/www/teaching/graphs2022/extra_03-03.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_03-22.pdf b/www/teaching/graphs2022/extra_03-22.pdf Binary files differdeleted file mode 100644 index 63ad3a0..0000000 --- a/www/teaching/graphs2022/extra_03-22.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_03-29.pdf b/www/teaching/graphs2022/extra_03-29.pdf Binary files differdeleted file mode 100644 index d7ce789..0000000 --- a/www/teaching/graphs2022/extra_03-29.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_03-31.pdf b/www/teaching/graphs2022/extra_03-31.pdf Binary files differdeleted file mode 100644 index 1f7aeb3..0000000 --- a/www/teaching/graphs2022/extra_03-31.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_04-05.pdf b/www/teaching/graphs2022/extra_04-05.pdf Binary files differdeleted file mode 100644 index 28a35cc..0000000 --- a/www/teaching/graphs2022/extra_04-05.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_04-07.pdf b/www/teaching/graphs2022/extra_04-07.pdf Binary files differdeleted file mode 100644 index bfb08ea..0000000 --- a/www/teaching/graphs2022/extra_04-07.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_04-12.pdf b/www/teaching/graphs2022/extra_04-12.pdf Binary files differdeleted file mode 100644 index 4624e16..0000000 --- a/www/teaching/graphs2022/extra_04-12.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_04-14.pdf b/www/teaching/graphs2022/extra_04-14.pdf Binary files differdeleted file mode 100644 index 47072d7..0000000 --- a/www/teaching/graphs2022/extra_04-14.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_04-19.pdf b/www/teaching/graphs2022/extra_04-19.pdf Binary files differdeleted file mode 100644 index 23b78b0..0000000 --- a/www/teaching/graphs2022/extra_04-19.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_04-26.pdf b/www/teaching/graphs2022/extra_04-26.pdf Binary files differdeleted file mode 100644 index dfb0e2b..0000000 --- a/www/teaching/graphs2022/extra_04-26.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_04-28.pdf b/www/teaching/graphs2022/extra_04-28.pdf Binary files differdeleted file mode 100644 index ba0ce2e..0000000 --- a/www/teaching/graphs2022/extra_04-28.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/extra_05-03.pdf b/www/teaching/graphs2022/extra_05-03.pdf Binary files differdeleted file mode 100644 index 6fe7d53..0000000 --- a/www/teaching/graphs2022/extra_05-03.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/fun.pdf b/www/teaching/graphs2022/fun.pdf Binary files differdeleted file mode 100644 index a9a34ec..0000000 --- a/www/teaching/graphs2022/fun.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw1.pdf b/www/teaching/graphs2022/hw1.pdf Binary files differdeleted file mode 100644 index dfea1fb..0000000 --- a/www/teaching/graphs2022/hw1.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw1.tex b/www/teaching/graphs2022/hw1.tex deleted file mode 100644 index 1f0b532..0000000 --- a/www/teaching/graphs2022/hw1.tex +++ /dev/null @@ -1,126 +0,0 @@ -\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 differdeleted file mode 100644 index 3655b55..0000000 --- a/www/teaching/graphs2022/hw10.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw10.tex b/www/teaching/graphs2022/hw10.tex deleted file mode 100644 index abb54fc..0000000 --- a/www/teaching/graphs2022/hw10.tex +++ /dev/null @@ -1,193 +0,0 @@ -\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 differdeleted file mode 100644 index 1b0be88..0000000 --- a/www/teaching/graphs2022/hw11.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw11.tex b/www/teaching/graphs2022/hw11.tex deleted file mode 100644 index b18793b..0000000 --- a/www/teaching/graphs2022/hw11.tex +++ /dev/null @@ -1,162 +0,0 @@ -\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 differdeleted file mode 100644 index d4be075..0000000 --- a/www/teaching/graphs2022/hw12.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw12.tex b/www/teaching/graphs2022/hw12.tex deleted file mode 100644 index 9a5abf9..0000000 --- a/www/teaching/graphs2022/hw12.tex +++ /dev/null @@ -1,140 +0,0 @@ -\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 differdeleted file mode 100644 index 972b6fe..0000000 --- a/www/teaching/graphs2022/hw13.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw13.tex b/www/teaching/graphs2022/hw13.tex deleted file mode 100644 index f254b2d..0000000 --- a/www/teaching/graphs2022/hw13.tex +++ /dev/null @@ -1,155 +0,0 @@ -\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 differdeleted file mode 100644 index b33ff75..0000000 --- a/www/teaching/graphs2022/hw2.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw2.tex b/www/teaching/graphs2022/hw2.tex deleted file mode 100644 index 1032470..0000000 --- a/www/teaching/graphs2022/hw2.tex +++ /dev/null @@ -1,134 +0,0 @@ -\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 differdeleted file mode 100644 index f2f1a63..0000000 --- a/www/teaching/graphs2022/hw3.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw3.tex b/www/teaching/graphs2022/hw3.tex deleted file mode 100644 index 3f83d09..0000000 --- a/www/teaching/graphs2022/hw3.tex +++ /dev/null @@ -1,130 +0,0 @@ -\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 differdeleted file mode 100644 index dab44ac..0000000 --- a/www/teaching/graphs2022/hw4.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw4.tex b/www/teaching/graphs2022/hw4.tex deleted file mode 100644 index e678650..0000000 --- a/www/teaching/graphs2022/hw4.tex +++ /dev/null @@ -1,129 +0,0 @@ -\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 differdeleted file mode 100644 index b9f5bb6..0000000 --- a/www/teaching/graphs2022/hw5.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw5.tex b/www/teaching/graphs2022/hw5.tex deleted file mode 100644 index 067511e..0000000 --- a/www/teaching/graphs2022/hw5.tex +++ /dev/null @@ -1,131 +0,0 @@ -\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 differdeleted file mode 100644 index 3874514..0000000 --- a/www/teaching/graphs2022/hw6.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw6.tex b/www/teaching/graphs2022/hw6.tex deleted file mode 100644 index c787ccd..0000000 --- a/www/teaching/graphs2022/hw6.tex +++ /dev/null @@ -1,170 +0,0 @@ -\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 differdeleted file mode 100644 index 271f38d..0000000 --- a/www/teaching/graphs2022/hw7.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw7.tex b/www/teaching/graphs2022/hw7.tex deleted file mode 100644 index c4380ba..0000000 --- a/www/teaching/graphs2022/hw7.tex +++ /dev/null @@ -1,143 +0,0 @@ -\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 differdeleted file mode 100644 index c946dd4..0000000 --- a/www/teaching/graphs2022/hw8.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw8.tex b/www/teaching/graphs2022/hw8.tex deleted file mode 100644 index c2243b4..0000000 --- a/www/teaching/graphs2022/hw8.tex +++ /dev/null @@ -1,139 +0,0 @@ -\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 differdeleted file mode 100644 index bec538b..0000000 --- a/www/teaching/graphs2022/hw9.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/hw9.tex b/www/teaching/graphs2022/hw9.tex deleted file mode 100644 index 7429f34..0000000 --- a/www/teaching/graphs2022/hw9.tex +++ /dev/null @@ -1,151 +0,0 @@ -\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 deleted file mode 100644 index 78be034..0000000 --- a/www/teaching/graphs2022/index.html +++ /dev/null @@ -1,430 +0,0 @@ ---- -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 /> - -<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/prufer.pdf b/www/teaching/graphs2022/prufer.pdf Binary files differdeleted file mode 100644 index 02bdc9e..0000000 --- a/www/teaching/graphs2022/prufer.pdf +++ /dev/null diff --git a/www/teaching/graphs2022/syllabus.pdf b/www/teaching/graphs2022/syllabus.pdf Binary files differdeleted file mode 100644 index 35caf8b..0000000 --- a/www/teaching/graphs2022/syllabus.pdf +++ /dev/null |
