Archive for September 2010

Decycling Graphs and Terrorists

In 2009 I was working at MIT coordinating math research for Research Science Institute for high school students. One of our students Jacob Hurwitz got a project on decycling graphs.

“Decycling” means removing vertices of a graph, so that the resulting graph doesn’t have cycles. The decycling number of a graph is the smallest number of vertices you need to remove.

Decycling is equivalent to finding induced forests in a graph. The set of vertices of the largest induced forest is a complement to the smallest set of vertices you need to remove for decycling.

lattice

forest

tree

Among other things, Jacob found induced trees and forests of the highest densities on graphs of all semi-regular tessellations. On the pictures he provided for this essay, you can see an example of a tessellation, a corresponding densest forest, and a corresponding densest tree. The density of the forest and the tree is 2/3, meaning that 1/3 of the vertices are removed.

To motivate RSI students I tried to come up with practical uses for their projects. When I was talking to Jacob about decycling, the only thing I could think of was terrorists. When terrorists create their cells, they need to limit connections among themselves, in order to limit the damage to everyone else in the cell if one of them gets busted.

That means the graph of connections of a terrorist cell is a tree. Suppose there is a group of people that we suspect, and we know the graph of their contacts, then the decycling number of the graph is the number of people that are guaranteed to be innocent.

Have you noticed how Facebook and LinkedIn are reasonably good at suggesting people you might know? The algorithm they use to analyze the data is fairly effective in revealing potential connections. Recently, someone was able to download all of the Facebook data, which means that any government agency ought to be able to do the same thing. They could analyze such data to discover implicit connections. As a byproduct of looking for terrorists, they would also discover all of our grudges.

Oh dear. What are they going to think when they find out I’m not connected to my exes?

Share:Facebooktwitterredditpinterestlinkedinmail

Marriage Proposals, Or How I Learned to Say No

In the name of privacy, I have changed the names of the men I did not marry. But there is no point in changing the names of my ex-husbands, as my readers probably know their names anyway.

I received my first marriage proposal when I was 16. As a person who was unable to say “no” to anything, I accepted it. Luckily, we were not allowed to get married until I was 18, the legal marriage age in the USSR, and by that time we broke up.

To my next proposal, from Sasha, I still couldn’t say “no”, and ended up marrying him. The fact that I was hoping to divorce him before I got married at 19 shows that I should have devoted more effort in learning to say “no”. I decided to divorce him within the first year.

My next proposal came from Andrey, I said yes, with every intention of living with Andrey forever. We married when I was 22 and he divorced me when I was 29.

After I recovered from my second divorce, I had a fling with an old friend, Sam, who was visiting Moscow on his way to immigrate to Israel.

Sam proposed to me in a letter that was sent from the train he took from the USSR to Israel. At that point I realized I had a problem with saying “no”. The idea of marrying Sam seemed premature and very risky. I didn’t want to say yes. I should have said no, but Sam didn’t have a return address, so I didn’t say anything.

That same year I received a phone call from Joseph. Joseph was an old friend who lived in the US, and I hadn’t seen or heard from him for ten years. He invited me to visit him in the US and then proposed to me the day after my arrival. The idea of marrying Joseph seemed premature and very risky, but in my heart it felt absolutely right. I said yes, and I wanted to say yes.

I was very glad that I hadn’t promised anything to Sam. But I felt uncomfortable. So even before I called my mother to notify her of my marriage plans, I located Sam in Israel and called him to tell him that I had accepted a marriage proposal from Joseph. I needed to consent to marry someone else as a way of saying “no” to Sam.

After I married Joseph, I came back to Russia to do all the paperwork and pick up my son, Alexey for our move to the US. There I met Victor. I wasn’t flirting with Victor and was completely disinterested. So his proposal came as a total surprise. That was the time I realized that I had a monumental problem with saying “no”. I had to say “no” to Victor, but I couldn’t force myself to pronounce the word. Here is our dialogue as I remember it:

  • Me: I can’t marry you, I am already married.
  • Victor: I am sure it’s a fictitious marriage; you just want to move to the USA.
  • Me: That’s not true. It’s a real marriage.
  • Victor: If it were a fictitious marriage, you wouldn’t admit it. So, it’s a fictitious marriage. My proposal stands.

My sincere attempt at saying “no” didn’t work. I moved to the US to live with Joseph and I soon got pregnant. Victor was the first person on my list to notify — another rather roundabout way to reject a proposal.

The marriage lasted eight years. Sometime after I divorced Joseph, I met Evan who invited me on a couple of dates. I wasn’t sure I wanted to get involved with him. But he proposed and got my attention. I was single and available, though I had my doubts about him.

Evan mentioned that he had royal blood. So I decided to act like a princess. I gave him a puzzle:

I have two coins that together make 15 cents. One of them is not a nickel. What are my coins?

He didn’t solve it. In and of itself, that wouldn’t be a reason to reject a guy. But Evan didn’t even understand my explanation, despite the fact that he was a systems administrator. A systems administrator who doesn’t get logic is a definite turn-off.

So I said “no”! That was my first “no” and I have mathematics to thank.

Share:Facebooktwitterredditpinterestlinkedinmail

My Sister

Ingrid and Me 2010When the Women and Math program at IAS was coming to an end, Ingrid Daubechies invited me to a picnic at her place for PACM

(The Program in Applied and Computational Mathematics at Princeton University). I accepted with great enthusiasm for three reasons: I was awfully tired and needed a rest; PACM was my former workplace, so I was hoping to meet old acquaintances; and most of all, I loved the chance to hang out with Ingrid.

Ingrid is a great cook, so she prepared some amazing deserts for the picnic. While I was helping myself to a second serving of her superb lemon mousse, a man asked me if I was Ingrid’s sister. Ingrid overheard this and laughingly told him that we are soul-sisters.

I admire Ingrid, so at first I took this as a compliment and felt all warm and fuzzy. But when my critical reasoning returned, I had to ask myself: Why would someone think I am Ingrid’s sister with my Eastern European round face, my Russian name and my Russian accent?

I started talking to the man. He asked me what I do. I told him that I am a mathematician. He was stunned. What is so surprising in meeting a mathematician at a math department picnic?

Now I think I understand what happened. It never occurred to him that I was a mathematician. I was clearly unattached, so he couldn’t place me as someone’s wife. As the picnic was at Ingrid’s house, he must have concluded that I had to be Ingrid’s relative. Very logical, but very gender biased.

Share:Facebooktwitterredditpinterestlinkedinmail