\documentclass[12pt]{article}
\usepackage{6820}

\newcommand\reals{\mathbb R}
\newcommand\naturals{\mathbb N}
\newcommand\integers{\mathbb Z}
\newcommand\len[1]{|\kern1pt#1\kern1pt|}

\begin{document}

\header{Homework 2}{Due Wednesday, September 21, 2022}

\begin{enumerate}
\item
A \emph{basket} is an undirected graph $G$ of the following form: There are two special vertices called the \emph{sides} and two special vertices that make up the \emph{handle}. The side vertices are each of degree $n-3$ and the handle vertices are each of degree $2$. Each handle vertex is connected to the other handle vertex and to one of the sides. Each side vertex is connected to all other vertices except one of the handle vertices and the other side. The remaining $n-4$ vertices of $G$ may be connected to one another arbitrarily.
\begin{figure}[h]
\begin{center}
\tikzstyle{background grid}=[draw, black!50, step=.5cm]
\tikzstyle{every state}=[circle, fill=black, inner sep=1.5pt, minimum size=0pt]
\begin{tikzpicture}
\small
\useasboundingbox (0,.8) rectangle (4,3.5);
%\node [inner sep=0pt,above right,opacity=.5] {\includegraphics[width=4cm]{images/basket}};
\node[state] (h1) at (1.5,2.9) {};
\node[state] (h2) at (2.5,2.9) {};
\node[state] (s1) at (.3,1.7) {};
\node[state] (s2) at (3.7,1.7) {};
\coordinate (center) at (2,.9);
\foreach \i in {1,...,5}
\node[state] (x\i) at ($(center) + (90+72*\i:6mm)$) {};
\node[anchor=east] at (.3,1.7) {\textit{side}};
\node[anchor=west] at (3.7,1.7) {\textit{side}};
\node[anchor=south] at (2,3) {\textit{handle}};
\path (h1) edge[thick] (h2);
\path (s1) edge[thick] (h1) edge[thick] (x1) edge[thick] (x2) edge[thick] (x3) edge[thick] (x4) edge[thick] (x5);
\path (s2) edge[thick] (h2) edge[thick] (x1) edge[thick] (x2) edge[thick] (x3) edge[thick] (x4) edge[thick] (x5);
\path (x1) edge[thick] (x2) edge[thick] (x4) edge[thick] (x5);
\path (x2) edge[thick] (x5);
\path (x3) edge[thick] (x2) edge[thick] (x4) edge[thick] (x5);
\end{tikzpicture}
\end{center}
\caption{A basket}
\end{figure}

Give an algorithm that makes only $O(n)$ probes of the adjacency matrix of $G$ and determines whether $G$ is a basket.

This is a counterexample to the \emph{Anderaa-Rosenberg conjecture}, which stated that any nontrivial graph property that is invariant under graph isomorphism requires $\Omega(n^2)$ probes of the adjacency matrix to test. Anderaa refuted this conjecture in 1975 using a different counterexample (see [1]), but modified the conjecture to say that it held for \emph{monotone} properties, those that cannot change from false to true when edges are deleted. This was later verified by Rivest and Vuillemin [1].

(\emph{Hint}.
 N fvzvyne ceboyrz naq vgf fbyhgvba ner cbfgrq ba gur unaqbhgf cntr.)

\item
\begin{enumerate}
\item
Give an efficient algorithm for determining the number of paths of length exactly $k$ between all pairs of vertices in a directed graph.
\item
Give an efficient algorithm for determining the number of paths of length at most $k$ between all pairs of vertices. (\emph{Warning}. Beware of the ``obvious'' solution, which counts paths more than once.)
\item
Suppose that all edges have positive integer weights. Let $s$ and $t$ be two vertices. Give an efficient algorithm for determining the number of minimum-weight paths from $s$ to $t$. (\emph{Extra karma}. Solve the problem under the weaker assumption that the edges have nonnegative weights, provided there are no weightless cycles.)
\end{enumerate}

\item
A matroid is \emph{linear} (or \emph{linearly representable}) if it is isomorphic to the matroid of columns of some matrix over some field.
\begin{enumerate}
\item
Show that the spanning tree matroid of an undirected graph is linear over $\integers_2$.
\item
Does every matroid have a linear representation over $\integers_2$? Give a proof or a counterexample. (\emph{Hint}.
 Pbafvqre gur zngebvq bs nyy fhofrgf bs fvmr ng zbfg gjb bs n sbhe-ryrzrag frg.)
\end{enumerate}
\end{enumerate}

\noindent
[1] R. L. Rivest and J. Vuillemin, On recognizing graph properties from adjacency matrices. Theoretical Computer Science 3, 371-384, 1976-77.

\end{document}
