I earned a PhD in mathematics at Wesleyan University.
My advisor was
Karen
L. Collins and my thesis was On minimality of planar
graphs with respect to treewidth.
I double majored in mathemaics and visual art at Bowdoin
College.
I taught mathematics at St. Mark's School for two years. I also coached JV basketball and lacrosse.
I grew up in Mystic, Connecticut.
Research
I am interested in graph theory (i.e. networks). Specifically, I have expertise with a measure called the treewidth
of a graph. Treewidth is at the heart of the proof of Robertson and Seymour's deep Graph Structure
Theorem and has far reaching
implications, contributing to proofs of the Graph Minor Theorem and
the Strong
Perfect Graph Theorem, and a simplified proof of the Four
Color Theorem.
The Graph Structure Theorem says that for any fixed graph, say G,
every graph either reduces to G through a sequence of edge
deletions, edge contractions and
vertex deletions (i.e. contains G as a minor) or can be built by piecing
together graphs of
bounded genus in a tree structure. The result
rests on the fact that planar (genus zero) graphs can have arbitrarily
large treewidth. In particular, the proof makes use of square grids because for n > 1 the
(n x n)-square grid has treewidth n.
We generalize the structures in square grids that
guarantee large treewidth. Actually, square grids are
inefficient for this outcome. Our more general structures, which we call nets,
are defined by identifying three sides of a graph embedded in the
plane. These nets turn out to be particularly fruitful for understanding
treewidth by using properties of the embedding.
If you have never heard of treewidth (or graph theory),
here is a teaser ...
Make a list of all the people who have ever sent you a text message. On a
big piece of paper, draw a point representing each person on that
list. You can place the points wherever you like. For any
two people on your list who have texted each other, draw a line
connecting the points representing them. Your drawing now describes
your text message network.
This network of people is going to protect a
password. The password can have as many characters as you want, and
you are going to divide up the password so that no one person knows the
whole thing.
Here is your strategy. Group your friends into several (possibly overlapping)
sub-networks. Each sub-network will come up with one character in
the password. The sub-networks
need to be connected so that every member can
learn the character by a chain
of text messages that stays within the sub-network.
Individuals may need to
recover the password quickly, so each sub-network needs to be able to communicate directly with every other
sub-network. That
is, for any two sub-netwoks, either you have a friend who is in both
of them or there is a member of one sub-network who can text a
member of the other sub-network.
A spy agency is trying to learn your password by hacking into
individual phones. Hacking reveals each character on the phone, so
it is preferable if no individual is in too many different
sub-networks.
Question:
Given your text message network, is there a way to design
sub-networks so that as long as there are no more than four
hacked phones, the spy agency will not uncover your full password?
Five hacked phones? One hundred hacked phones?
... Bramble Number
For any graph, a collection of subsets of its vertices is called a
bramble if (1) every subset is connected in the
graph, and (2) the union of any pair of subsets is also connected. The order of a
bramble is the smallest number of vertices needed to get a
representative of each vertex subset in the collection. And the
bramble number of a graph is the maximum order
among all brambles in a graph.
The teaser is asking for the bramble number of your text
message network. Moreover, bramble number is a dual problem to the
treewidth of a graph.
Teaching
Add up the first five odd numbers: 1+3+5+7+9 = 25. That's 5 x 5. If
you add up the first ten odd numbers, you get
exactly 100 = 10 x 10. The first twenty odd
numbers add to 400 = 20 x 20. That can't be a
coincidence... Learning starts with curiosity. We
care about questions when the answer seems simple, surprising or
useful.
Do you feel like telling
someone this odd-number trick (even if you already know it)?
Maybe we stumbled on one of the
universe's greatest secrets, or maybe we just added wrong. Talking
to other people
validates our understanding, uncovers our misconceptions and gives us new ideas. Our learning
community moves us forward.
I drew the picture on the right to
help me understand why the odd numbers sum to square numbers. Left to your own
devices, you would undoubtably come up with a (maybe slightly)
different way of describing this phenomenon. Deep understanding requires creativity and a personal connection. So what is your
explaination? How do you plan to use this knowledge?
James S. Rolf and I created a video game called Cartes to help
students better understand
function properties. We designed the game with PreviewLabs. We also had advice from
the Yale Center for Health and Learning Games, and our funding came from the
Yale Center for Teaching and Learning. Check out a demo of the
gameply captured during a talk to the Math Club at the University of Bridgeport:
Brett C. Smith
Helmsley Postdoctoral Teaching Scholar
Department of Mathematics
Yale University
10 Hillhouse Ave
New Haven, CT 06511
