01 September 2014

Kuratowski's Theorem

It has been more than a year since I've written in my theorem journal, but last week in Wisconsin I learned a theorem that definitely deserves to compel my return to the practice!

A graph is planar if it can be drawn in a plane (two dimensions, ie on a piece of paper) without graph edges crossing.

A subdivision of a graph G=(V,E) is a graph resulting from taking an edge e in E with endpoints u,v in V, introducing a new vertex w, and replacing e with two new edges, one between u,w and one between w,v.

Kuratowski's Theorem states that a graph with a finite number of vertices V and edges E is planar if and only if it does not contain a subgraph that is a subdivision of (1) the completely connected graph on five vertices or (2) the complete bipartite graph on six vertices, three in each partition.

Completely connected graph on five vertices:

Image from mathworld.

Complete bipartite graph on six vertices with 3 in each partition:

Image from mathworld.

29 July 2014

Priya Haji

Two weeks ago I had some very sad news. Priya Haji, the amazing and inspiring cousin of my best friend Sheila Hall, passed away at age 44. She was the co-founder of Save-up, a website to help people pay down debt. Before that she co-founded World of Good, a retail company that sold goods made by artisans around the world and promoted fair trade. While in college she co-founded a community recovery center in East Palo Alto called Free At Last.

Fast company did a great article on Priya.

Here you can read Priya's obituary on techcrunch.com.

Here you can watch Van Jones give a tribute to Priya at a celebration of her life.

Priya was always so fun to be around; she worked so hard and embraced everything so fully. She will live on in all of us if we try to be just a little less hesitant and jump in feet first to helping the people around us.

15 April 2014

far better

Preparing a lecture on robust estimation for my class on Thursday, I ran across this gem:

"Far better an approximate answer to the right question, which is often vague, than an exact answer to the wrong question, which can always be made precise." - John Tukey.

09 April 2014

Math in Computer Science

When I was at Wisconsin for my PhD, I visited two highschool calculus classes to try to show the students how useful math can be in real life. We looked at fourier integrals (integration by parts, and useful for modeling cell phone signals!) and decision statistics (when should the basketball team decide to recruit a player?) and talked about all kinds of jobs and the math that they used. Of course, when it came down to it, the students knew their parents don't use math each day in their jobs-- And even a math diehard like me has to admit that in a regular working day, the majority of jobs don't have math.

But that's why I really liked this article that was shared with me awhile ago by my friend Brian Cobb. It's written by a programmer advocating for more math understanding. As the author says, many people (in this case, the three articles he cites) believe that "from a workaday perspective, math is essentially useless." But the fact is, so many real innovations were driven by changing mathematical models and understandings of applications for programming.

My favorite line, of course: "mathematics is a tool for understanding phenomena in the world: the motion of the planets, the patterns in data, the perception of color, or any of a myriad things in the world"... and isn't that a worthy goal?

20 March 2014


I've never been one to take grades extremely seriously. I enjoyed studying the material that was interesting to me... and it turns out, that's not always what's on the test. However, in college I did get concerned that my good-ish grades were an indicator that I wouldn't be successful in electrical engineering. Thank goodness Professor Don Johnson pointed out a statistic to me way back then, that women drop engineering at a much higher GPA than men do-- I don't remember where he found it, but I vaguely remember it was something like women drop out at average of 3.3 and men at average of 2.3-- a full grade point higher.

Today I read an article about women who leave economics majors starting at A- grades. I wonder what this is today for STEM majors. I also appreciated the article's comments about women considering the whole picture-- in some types of technology and business jobs, it does take longer for a woman to get to the point where you will be treated equally (in terms of position and pay) to her male counterparts. Looking at the correlation between female students' choices and her consequences on the job market-- perhaps an A- female gets treated like a B- male? That would be an interesting study to do.

23 February 2014

the signal and the noise

I finished Nate Silver's book (in November, and in time to hand off to my dad at Thanksgiving), and I finally getting around to posting some of my favorite points.

The first thing that caught my eye reminds me of conversations with the Internet MRA IPAM group, especially John Doyle. Talking about several wrong predictions during the recession starting in 2008 that were based solely on data, Silver wrote "ECRI actually seems quite proud of this approach. 'Just as you do not need to know exactly how a car engine works in order to drive safely,' it advised its clients in a 2004 book, 'You do not need to understand all the intricacies of the economy to accurately read those gauges.'" (p 197) This kind of statement makes me cringe, and Silver agrees: "This kind of statement is becoming more common in the age of Big Data. Who needs theory when you have so much information? But this is categorically the wrong attitude to take toward forecasting, especially in a field like economics where the data are so noisy."

I am often thinking of self-canceling predictions, and he does a good job discussing them in Chapter 7. A great example is that of a GPS that predicts where the heavy traffic will be-- if it sends more drivers on the less busy route, it won't be the less busy route for long.

Chapter 11 is about betting. There I learned that "free-market capitalism and Bayes' theorem come out of something of the same intellectual tradition. Adam Smith and Thomas Bayes were contemporaries, and both were educated in Scotland and were heavily influenced by the philosopher David Hume."

In this chapter I also enjoyed a quote from Daniel Kahneman about the two arrowed-lines illusion that makes two same-length lines look different lengths. He said "You can look at them, and one of the arrows is going to look longer than the other. But you can train yourself to recognize that this is a pattern that causes an illusion, and in that situation, I can't trust my impressions; I've got to use a ruler." This reminds me of abstract mathematics. At some point you learn the situations in which you can't trust your judgement or intuition, and you slow down and look at things more carefully.

"A climate of healthy skepticism" is the title of Chapter 12; you all know this must be one of my favorite chapters. Not only because it's about skepticism though-- also I am very interested in skepticism about climate change, which is the topic of this chapter. A lot of the difficulties with policy on climate change are human-understanding related, not science related. Silver quotes Richard Rood, a scientist at NASA who also teaches at Michigan (I'd like to meet him!). Rood said, "At NASA, I finally realized that the definition of rocket science is using relatively simple physics to solve complex problems. The science part is relatively easy. The other parts-- how do you develop policy, how do you respond in terms of public health-- these are all relatively difficult problems because they don't have as well defined a cause-and-effect mechanism." Unfortunately the conclusion of this chapter is that politics these days are just too polarizing, and "It is seen as a gaffe when one says something inconvenient-- and true" (p411). It's my hope that this doesn't hold true permanently.

From Tom Schelling, "There is a tendency in our planning to confuse the unfamiliar with the improbable." This quote reminds me of the unseen species problem, or the problem of estimating a probability of some event when we haven't ever (or have rarely) seen the event happen. I wonder if someday this probability theory will be able to help us better handle predicting rare or new unconsidered events.

Last but certainly not least, there was a very nice little description of how "signal and noise" comes, of course, from the study of electrical engineering, in particular communications. Gave me warm fuzzies... little did I understand, when I was just a 19 year old kid in Don Johnson's intro to EE class, that I was learning math and ideas that were built up over centuries to create some of the most amazing technology we've ever seen!

28 January 2014

What kind of math is right for you?

Apparently this poster was handed out at a recent AMS math meeting, trying to show people how there are many cool options when you choose to go into math. Sounds good right? But let's play the game "Which of these is not like the others..."

What's that you say? All the men are doing pure math and all the women are doing applied math? What a fun puzzle for cluster feature selection! Do you think they were trying to get us to see the pattern? That's a math problem you know.

Thanks to Tullia Dymarz for her response photo:

This one's another puzzle! These ladies are all studying different aspects of what field? Turn your computer upside down to find out!

ʎɹoǝɥʇ dnoɹƃ ɔᴉʇoʇdɯʎsɐ :ɹǝʍsuɐ