1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
\input ws-form.tex
\def\pre#1{\par\leavevmode\llap{\hbox to .5in{\hfil #1 \hfil}}}
\def\prebullet{\pre{$\bullet$}}
\def\em{\it\bf}
\parindent=.5in
\question{%
Q1 (5.34) -- Below are three sequences of length 10. One of the sequences cannot be the degree sequence of any graph. Identify it and say why. For each of the other two, say why (if you have enough information) a connected graph with that degree sequence:
\prebullet is definitely hamiltonian/cannot be hamiltonian;
\prebullet is definitely eulerian/cannot be eulerian;
\prebullet is definitely a tree/cannot be a tree; and
\prebullet is definitely planar/cannot be planar.
(If you do not have enough information to make a determination for a sequence without having specific graph(s) with that degree sequence, write “not enough information” for that property.)
\pre{a.} $(6,6,4,4,4,4,2,2,2,2)$
\pre{b.} $(7,7,7,7,6,6,6,2,1,1)$
\pre{c.} $(8,6,4,4,4,3,2,2,1,1)$
}{
Sequence $c$ cannot be a degree sequence because $\sum deg = 2q = 35$ where $q$ is the number of edges, which means there is a fractional number of edges, which is impossible.
\pre{a.} There is not enough info for hamiltonian. Definitely eulerian, because the degree of all vertices is even. Cannot be a tree because there must be exactly $n-1$ edges, and the sum of degrees is greater than $2n-2$. Not enough info for planar because the number of edges, $18 \leq 3n - 6 = 24$, the restriction on planar graphs derived from Euler's formula.
\pre{b.} Definitely not hamiltonian because there are two vertices of degree 1, which means there's no way to ``escape'' them to form a cycle. Definitely not eulerian because many vertices are not of even degree. Similar to $a$, $b$ cannot be a degree sequence of a tree because $25 \neq 10-1 = 9$. Definitely not planar by the same inequality used for $a$: $25 \not\leq 24$.}
\question{%
Q2 (5.39) -- Determine pr\"ufer$({\bf T})$ for the tree ${\bf T}$ in Figure 5.58 (not pictured).
}{
$(9,3,9,5,9,4,5,14,1,6,5,1)$
}
\question{%
Q3 (6.1) -- We say that a relation $R$ on a set $X$ is {\em symmetric} if $(x,y) \in R$ implies $(y,x) \in R$ for all $x, y \in X$. If $X = {a, b, c, d, e, f}$, how many symmetric relations are there on $X$? How many of these are reflexive?
}{
Constructing symmetric relations as a choice of 2 elements from 7 (adding an artificial element to account for reflexive pairs), there are ${2 \choose 7} = 21$ symmetric relations on $X$.
Further restricting the set to exclusively reflexive relations, reflexive pairs needn't be considered, so no artifical element need be added. Therefore, there are ${2 \choose 6} = 15$ symmetric, reflexive relations on $X$.
}
\question{%
\def\mod{\thinspace({\rm mod\thinspace} m)}
Q4 (6.2) -- A relation $R$ on a set $X$ is an {\em equivalence relation} if $R$ is reflexive, symmetric, and transitive. Fix an integer $m \geq 2$. Show that the relation defined on the set $\bf Z$ of integers by $aRb(a, b \in {\bf Z})$ if and only if $a \equiv b \thinspace({\rm mod\thinspace} m)$ is an equivalence relation. (Recall that $a \equiv b \thinspace({\rm mod \thinspace} m)$ means that when dividing $a$ by $m$ and $b$ by $m$ you get the same remainder.)
}{
Assume that $a \equiv b \thinspace({\rm mod \thinspace} m)$ is not an equivalence relation---that is, it is either not reflexive, not symmetric, or not transitive. It is clearly transitive because if $a \equiv b \equiv c \mod$, then the remainders of $a$ and $b$ are the same and the remainders of $b$ and $c$ are the same, so $a$ and $c$ are the same. It is also clearly symmetric, because equality of remainders transfers to equivalency from mod. Third, it is reflexive because the remainder of $b \div m$ is equal to $b \div m$. By contradiction, this means that no relation $aRb$ on $\bf Z$ could exist if $a \equiv b \mod$ is not an equivalence relation.
}
\question{%
Q5 (6.7) -- Alice and Bob are considering posets $\bf P$ and $\bf Q$. They soon realize that $\bf Q$ is isomorphic to ${\bf P}^d$. After 10 minutes of work, they figure out that $\bf P$ has height 5 and width 3. Bob doesn't want to find the height and width of $\bf Q$, since he figures it will take (at least) another 10 minutes to answer these questions for $\bf Q$. Alice says Bob is crazy and that she already knows the height and width of $\bf Q$. Who's right and why?
}{
If $\bf P^d$ is isomorphic to $\bf Q$, then there is a bijection $f: X \to Y$ between the base sets of $\bf P^d$ and $\bf Q$ such that all the same comparisons exist on relations $P^d$ and $Q$ for respective $v$ and $f(v)$. This means that any comparison or set of comparisons valid or invalid on $\bf P^d$ would be valid or invalid, respectively, on $\bf Q$. Therefore, a given chain or anti-chain will be retained and thus the heights and widths are the same of $\bf P^d$ and $\bf Q$. Note also that the heights and widths of $\bf P^d$ and $\bf P$ are the same because they have the same comparable objects, just opposite comparisons. (Alice is right)
}
\question{%
Q6 (6.8) -- For this exercise, considef the poset $\bf P$ in Figure 6.5 (not pictured).
\pre{a.} List the maximal elements of $\bf P$.
\pre{b.} List the minimal elements of $\bf P$.
\pre{c.} Find a maximal chain with two points in $\bf P$.
\pre{d.} Find a chain in $\bf P$ with three points that is {\it not} maximal. Say why your chain is not maximal.
\pre{e.} Find a maximal antichain with four points in $\bf P$.
}{
\pre{a.} $(15, 8, 11, 2, 17, 3)$
\pre{b.} $(16, 1, 5, 14)$
\pre{c.} $(16, 8)$
\pre{d.} $(15, 7, 13)$ is not maximal because, with transitivity, adding $1$ would form a larger chain.
\pre{e.} $(16, 1, 5, 14)$
}
\question{%
Q7 (6.9) -- Find the height $h$ of the poset ${\bf P} = (X, P)$ shown below as well as a maximum chain and a partition of $X$ into $h$ antichains using the algorithm from this chapter.
}{
Partition: $(23,12,22,18) \cup () \cup ()$
}
\question{%
Q8 (6.11) -- A restaurant chef has designed a new set of dishes for his menu. His set of dishes contains 10 main courses, and he will select a subset of them to place on the menu each night. To ensure variety of main courses for his patrons, he wants to guarantee that a night's menu is neither completely contained in nor completely contains another night's menu. What is the largest number of menus he can plan using his 10 main courses subject to this requirement?
}{
This is equivalent to asking the size of the maximum anti-chain of the subset lattice ${\bf 2}^{10}$, which is ${10 \choose 5}=252$, by Sperner's Theorem.
}
\bye
|
