DMAT_AS3

Problem 1

Question

Let $p$ be a prime and consider the cyclic group $C_p=⟨\sigma ⟩$ of order $p$ acting on all $p$-tuples $(a_1,a_2,\dots ,a_p)\in [n{]}^p$ by cyclic shift. That is, $(a_1,a_2,\dots ,a_p)\sigma =(a_p,a_1,\dots ,a_{p-1})$. Analyzing the orbits and stabilizers of this group action show that $p$ divides $np-n$.

Let $\mathcal{O}$ be the number of orbits. From Burnside’s Lemma,

$$\begin{array}{rl}\mathcal{O}& =\frac{1}{p}\sum _{g\in C_p}\text{fix}(g).\end{array}$$

Now, $\text{fix(e)}=n^p$, and since $p$ is prime, the remaining $p-1$ members of $C_p$ only fix tuples containing a single repeating number. Thus,

$$\mathcal{O}=\frac{n^p+(p-1)n}{p}=\frac{n^p-n}{p}+n.$$

Since $\mathcal{O}$ is a natural number, it follows that $p$ divides $n^p-n$.

---

Problem 2

Question

Considering the group of rotational symmetries of the cube discussed in class, find the number of distinguishable 17 dollar cubes that can be built using three types of edges: one dollar lead bars, two dollar silver bars, and three dollar gold bars.

Let $E=\{e_1,e_2,\dots ,e_{12}\}$ denote the edge set. Let $\Phi =\{\text{Pb},\text{Au},\text{Ag}\}$, and let $w(\text{Pb})=1$, $w(\text{Au})=2$, $w(\text{Ag})=3$. The figure generating series is $a(t)=t+t^2+t^3$. Let $G\le \text{Sym}(E)$ be the rotational symmetries of the cube. The cycle types of the elements of $G$ are as follows:

Symmetry	Cycle type	Count
The identity symmetry	$c_1(g)=12$	1
Face symmetries ($180°$ rotations)	$c_2(g)=6$	3
Face Symmetries ($90^{\circ }$ rotations)	$c_4(g)=3$	6
Edge Symmetries	$c_1(g)=2$, $c_2(g)=5$	6
Vertex Symmetries	$c_3(g)=4$	8

From the cycle index theorem, the function generating series is given by

$$\begin{array}{rl}b(t)& =Z(G;a(t),\dots ,a(t^{12}))\\ & =\frac{1}{24}\sum _{g\in G}a(t{)}^{c_1(g)}\dots a(t^{12}{)}^{c_{12}(g)}\\ & =\frac{1}{24}(a(t{)}^{12}+3a(t^2{)}^6+6a(t^4{)}^3+6a(t{)}^{2}a(t^2{)}^5+8a(t^3{)}^4).\end{array}$$

The number of distinguishable $17$ dollar cubes is the coefficient of $t^{17}$ in $b(t)$, which is $153$.

---

Problem 3

Question

If we delete a node $v$ from a tree (together with all edges that end there), we get a graph whose connected components are trees. We call these connected components the branches at node $v$. Prove that every tree has a node such that every branch at this node contains at most half the nodes of the tree.

Let $T$ be a tree on $n$ nodes. Pick an arbitrary vertex ${\mathbf{v}}_0$ of $T$. Let $C_1^0,C_2^0,\dots ,C_{k_0}^0$ be the branches at ${\mathbf{v}}_0$. If $|C_i^0|\le \lfloor \frac{n}{2}\rfloor$ for each $1\le i\le k_0$, we are done. Else, let $|C_{\alpha }^0|=\lfloor \frac{n}{2}\rfloor +{\lambda }_0$, for some $1\le \alpha \le k_0$ and positive integer ${\lambda }_0$. Let ${\mathbf{v}}_1$ be the vertex that connects $C_{\alpha }^0$ to ${\mathbf{v}}_0$. Define $C_1^1\equiv T\setminus C_{\alpha }^0$, and let $C_2^1,\dots ,C_{k_1}^1$ be the remaining branches at ${\mathbf{v}}_1$. Note that $|C_1^1|=n-\lfloor \frac{n}{2}\rfloor -{\lambda }_0\le \lfloor \frac{n}{2}\rfloor$.

If $|C_i^1|\le \lfloor \frac{n}{2}\rfloor$ for each $2\le i\le k_1$, we are done. Else, let $|C_{\beta }^1|=\lfloor \frac{n}{2}\rfloor +{\lambda }_1$, for some $2\le \beta \le k_1$ and positive integer ${\lambda }_1$. Note that ${\lambda }_1<{\lambda }_0$. Thus, if we continue in this manner, we are guaranteed to find a node $\mathbf{v}$ such that every branch contains at most half the nodes of the tree in no more than ${\lambda }_0$ steps.

---

Problem 4

Question

Prove that in a finite undirected graph where each vertex has degree ≥ 2 must have a cycle. Is this necessarily true for infinite graphs? Also prove the following: Let G be a finite directed graph. If every vertex of G has out-degree at least 1, then G has a directed cycle.

Let $G$ be a finite undirected graph where each vertex has degree $\ge 2$. Let $v_0$ be an arbitrary vertex of $G$. Let $v_1$ be a vertex $v_0$ is connected to. $v_1$ must be connected to another vertex $v_2$ other than $v_0$, since it has degree of at least $2$. Inductively, $v_k$ must be connected to a vertex $v_{k+1}\ne v_{k-1}$. Since $G$ is finite, vertices will eventually repeat in the sequence $v_0,v_1,\dots$. Let $v_l=v_m$, $l<m$. Then, $v_l,\dots ,v_{m-1}$ is a cycle.

This not true for infinite graphs. A simple counterexample is the graph $G$ on $\mathbb{N}$ where $(n,n+1)\in E(G)$ for each $n\in \mathbb{N}$.

Let $G$ be a finite directed graph where each vertex has out degree at least $1$. Let $v_0$ be an arbitrary vertex of $G$. Let $v_0\to v_1$ be an edge. Since every vertex has at least one outgoing edge, the sequence can be extended to any arbitrary length. Again, since $G$ is finite, vertices are bound to repeat eventually, yielding a cycle $v_l\to \cdots \to v_{m-1}\to v_l$ for some $l<m$ and $v_l=v_m$.

---

Problem 5

Question

Prove that in a connected graph G with at least three vertices, any two longest paths have a vertex in common.

Let $G$ have $n$ vertices. Let the maximal path length in $G$ be $k$ edges. FTSOC, assume $G$ has two paths of length $k$ with disjoint vertex sets $V=\{v_0,\dots ,v_k\}$ and $V^{\prime }=\{v_0^{\prime },\dots ,v_k^{\prime }\}$. Since $G$ is connected, there exists an edge between $V_1$ and $V_2$ in $G$, say $\{v_i,v_j^{\prime }\}$. If $i\ge k/2$, define $\overline{v}$ to be $v_0$, else define $\overline{v}$ to be $v_k$. If $j\ge k/2$, define ${\overline{v}}^{\prime }$ to be $v_0^{\prime }$, else define ${\overline{v}}^{\prime }$ to be $v_k^{\prime }$. The path $\overline{v},\dots ,v_i,v_j^{\prime },\dots ,{\overline{v}}^{\prime }$ has a minimum length of $k+1$, a contradiction.

---

Problem 6

Question

We know that for any $n$, the set of all transpositions (2-cycles) generates the symmetric group ${\mathfrak{S}}_n$. We associate a graph on the vertex set $[n]$ to a set of transpositions by identifying the transposition $(ij)$ with the edge joining the vertices $i$ and $j$. Show that a set of transpositions generates ${\mathfrak{S}}_n$ if and only if the corresponding graph on $[n]$ is connected.

Let $S$ be a set of transpositions on $[n]$, and $G$ be the corresponding graph on $[n]$.

Assume $G$ is not connected. Let $C$ be a connected component of $G$. Let $a\in V(C)$. For all transpositions $\sigma \equiv (i,j)\in S$, the edge $(i,j)$ of $G$ must be in either $E(C)$ or $E(G\setminus C)$. In the first case, $\sigma (a)\in V(C)$, and in the second case, $\sigma (a)=a\in V(C)$. Inductively, $({\sigma }_k\dots {\sigma }_1)(a)\in V(C)$ for all positive integers $k$. It follows that $S$ cannot generate $\tau \equiv (a,b)\in {\mathfrak{S}}_n$ for any $b\in V(G\setminus C)$. Thus, $S$ does not generate ${\mathfrak{S}}_n$.

Conversely, assume $G$ is connected. For any $a,b\in [n]$, there exists a path between $a$ and $b$ in $G$. Let this path be $(v_0\equiv a,v_1),\dots ,(v_{k-1},v_k\equiv b)$.

Theorem 1(Lemma).

$\{(v_0\equiv a,v_1),\dots ,(v_{k-1},v_k\equiv b)\}$ generates $(a,b)$.

Proof
We proceed by induction on $k$. The Lemma holds trivially for $k=1$. Assume the lemma holds for $k=m-1$ for a positive integer $m$. So, $\{(v_1,v_2),\dots ,(v_{k-1},v_k)\}$ generates $\rho \equiv (v_1,b)$. Now, $(a,v_1)\rho (a,v_1)=(a,v_1)(v_1,b)(a,v_1)=(a,b)$.

Thus, $S$ can generate every transposition $(a,b)$, for $a,b\in [n]$. Since ${\mathfrak{S}}_n$ is generated by the set of all transpositions of $[n]$, $S$ generates ${\mathfrak{S}}_n$.

---

Problem 7

Question

Let $A$ be an incidence matrix of an undirected graph $G$. Let $E^{\prime }=\{e_{i_1},\dots ,e_{i_k}\}$ be a subset of edges of $G$. Show the following using induction on k. If the edges in E′ do not form a cycle, then the columns in A associated with those edges are linearly independent. The converse is true if the graph is bipartite.

Let ${\mathbf{e}}_i$ be the column in $A$ associated with the edge $e_i$, and let $C_E$ be the collection of columns in $A$ associated with the edges in $E$.

For $k=1$, the proposition clearly holds. Assume that the proposition holds for $k=n-1$. Let $E^{\prime }=\{e_{i_1},\dots ,e_{i_n}\}$ not have any cycles. Then, $C_{E^{\prime }\setminus e_{i_n}}$ is linearly independent. FTSOC, assume $C_{E^{\prime }}$ is linearly dependent. Then, there exists a non-trivial linear combination ${\alpha }_1{\mathbf{e}}_{i_1}+\cdots +{\alpha }_n{\mathbf{e}}_{i_n}=0$. Also, ${\alpha }_n\ne 0$, since a non-trivial linear combination of $C_{E^{\prime }\setminus e_{i_n}}$ equalling $0$ does not exist. Let ${\overline{E}}^{\prime }\subseteq E^{\prime }$ be the subcollection of $E^{\prime }$ with non-zero coefficient in the linear combination. Let $V^{\prime }$ be the set of vertices that edges in ${\overline{E}}^{\prime }$ are incident on. $(V^{\prime },{\overline{E}}^{\prime })$ is a subgraph of $G$. Each $v\in V^{\prime }$ has a minimum degree of $2$, since otherwise the linear combination cannot evaluate to $0$. We know that a graph with minimum degree $2$ contains a cycle, contradicting our hypothesis that $E^{\prime }$ does not have any cycles. Thus, $C_{E^{\prime }}$ is linearly independent.

Next, we will prove the contrapositive of the converse, that is, If $G$ is bipartite and some edges in $E^{\prime }$ form a cycle, $C_{E^{\prime }}$ is linearly dependent. If a graph is bipartite, it doesn’t have any odd cycles. Thus, the cycle in $E^{\prime }$ must be of even length. Let $e_{j_1},\dots ,e_{j_{2a}},e_{j_1}$ be edges of the cycle, in that order. Now, note that $({\mathbf{e}}_{j_1}+{\mathbf{e}}_{j_3}+\cdots +{\mathbf{e}}_{2a-1})-({\mathbf{e}}_{j_2}+{\mathbf{e}}_{j_4}+\cdots +{\mathbf{e}}_{2a})$, a non-trivial linear combination of $C_{E^{\prime }}$, is equal to $0$, since every vertex that has an edge associated with it in the first sum also has one in the second sum, and no other edge associated with it in both the sums . Thus, $C_{E^{\prime }}$ is linearly dependent.

---

Problem 8

Question

The spanning tree game is a 2-player game. Each player in turn selects an edge. Alice starts by deleting an edge, and then Bob fixes an edge (which has not been deleted yet); an edge fixed cannot be deleted later on by the other player. Bob wins if he succeeds in constructing a spanning tree of the graph; otherwise, Alice wins. Prove the following. If there are two spanning trees in the graph whose edge sets are disjoint, Bob can win no matter how Alice plays.

Let $G$ be a graph on $n$ nodes. Let $T$ and $T^{\prime }$ be two spanning trees of $G$ such that $E(T)\cap E(T^{\prime })=\varnothing$. Let the set of edges fixed by Bob be $B$. Suppose Alice deletes edge $e$. If $e\notin E(T)\cup E(T^{\prime })$, Bob can randomly fix $e^{\prime }\in E(T)$. Now, suppose $e\in E(T)\cup E(T^{\prime })$. WLOG, $e\in E(T)$.

Theorem 2(Lemma).

If $T,T^{\prime }$ are spanning trees of a connected graph $G$ and $e\in E(T)\setminus E(T^{\prime })$, then there is an edge $e^{\prime }\in E(T^{\prime })\setminus E(T)$ such that $T-e+e^{\prime }$ is a spanning tree of $G$.

Proof
Every edge of $T$ is a cut-edge of $T$. Let $U$ and $U^{\prime }$ be the two components of $T-e$. Since $T^{\prime }$ is a spanning tree, it must contain an edge $e^{\prime }$ with endpoints in $U$ and $U^{\prime }$. $T-e+e^{\prime }$ is a spanning tree.

So, there exists $e^{\prime }\in E(T^{\prime })\setminus E(T)=E(T^{\prime })$ such that $T-e+e^{\prime }$ is a spanning tree. Bob picks $e^{\prime }$. Redefine $T$ to be $T-e+e^{\prime }$. Now, $E(T)\cap E(T^{\prime })=\{e^{\prime }\}$. Also, $B\subseteq E(T)$.

For the second move, Alice cannot pick an edge from $E(T)\cap E(T^{\prime })$, and $|E(T)\setminus E(T^{\prime })|=|E(T^{\prime })\setminus E(T)|\ge n-2$. Again, if Alice’s choice $e$ is in $E(T)\setminus E(T^{\prime })$, Bob can find an $e^{\prime }$ in $E(T^{\prime })\setminus E(T)$ such that $T-e+e^{\prime }$ is a spanning tree, and if $e$ is in $E(T^{\prime })\setminus E(T)$, Bob can find an $e^{\prime }$ in $E(T)\setminus E(T^{\prime })$ such that $T^{\prime }-e+e^{\prime }$ is a spanning tree. If he hasn’t fixed $e^{\prime }$ already, he fixes it, and updates the value of $T$ or $T^{\prime }$ as before. In all other cases, Bob randomly fixes $e^{\prime }\in E(T)$. $B$ remains a subset of $E(T)$.

Inductively, on the $k$th move, Alice cannot delete an edge from $E(T)\cap E(T^{\prime })$, since Bob has claimed all those edges as they were created. Alice must pick her edge from $E(T)\setminus E(T^{\prime })$, $E(T^{\prime })\setminus E(T)$, or $(E(T)\cup E(T^{\prime }){)}^c$. Bob proceeds as before.

At every step, $B$ grows by $1$, and $B\subseteq E(T)$. Thus, in $n-1$ moves, Bob can grow $B$ to $E(T)$, winning the game (note that $T$ may be redefined several times in the course of the game; it nevertheless remains a spanning tree).