1
$\begingroup$

I am currently taking an introduction to graph theory course. We are using the 5th edition book by Robin J Wilson. At the end of chapter 1 there are some challenging problems I'd like to think about. But the problem is I don't exactly know what it is asking me. Here is the problem:

If $G$ is a simple graph with the edge-set $E(G)$, the vector space of G is the vector space over the field $\mathbb{Z}_2 = \{0,1\}$ of integers mod 2, whose elements are subsets of $E(G)$. The sum $E+F$ of two such subset $E$ and $F$ is the set of edges in $E$ or $F$ but not both and scaler multiplication is defined by $1\cdot E = E$ and $0\cdot E = \text{empty set}$. Show that this defines a vector spacee over $\mathbb{Z}_2$ and find a basis for it

So I've taken linear algebra, abstract algebra so I am familiar with what a vector field is. Similarly I also know what a field is and I also know simple modular arithmetic. However, I dont know how to combine everything together. If M.SE could be kind enough to go through the problem and explain what each part is doing and the meaning and possibly a solution. For example what does it mean by "vector space of G over the field.."

  • 0
    Here is a good coverage of the basic graph vector spaces- vertex space, edge space, cycle space, and cut space. Note that cycle and cut spaces are subspaces of edge space. http://www.dreamincode.net/forums/topic/328653-algebraic-graph-theory-vertex-and-edge-spaces/2014-03-13

1 Answers 1

3

This is too long for a comment, so I'll leave it up here as an answer instead. I propose you pick your linear algebra notes/textbook and with that try to do the following:

Let $X$ be a set, and let $V=\mathcal{P}(X)$ be the set of all subsets of $X$.

Define an operation $+:V\times V\to V$ as follows: if $A$, $B\in V$, so that $A$ and $B$ are subsets of $X$, then we define $A+B$ to be $A\cup B-A\cap B$.

Now show that this operation $+$ has all the properties required of the addition of a vector space—your linear algebra notes surely list them, so I won't repeat them here.

Next, we are going to consider the field $F=\mathbb Z_2$ with two elements and define a scaar multiplication $\cdot:F\times V\to V$ as follows.

For all $A\in V$ we define $0\cdot A=\emptyset$ and $1\cdot A=A$. This is enough, because $F$ has exactly two elements, namely $0$ and $1$.

Now check that this scalar multiplication $\cdot$ has all the required properties of the scalar multiplication of a vector space over the field $F$, and that $+$ and $\cdot$ are related in the way they should in order for $V$ to become a vector space with them as operations.