Commons license.

Your support will help MIT OpenCourseWare

continue to offer high quality educational resources for free.

To make a donation or view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

PROFESSOR: OK let's get started.

I once taught with a professor who

was lamenting the fact that as the term progresses attendance

in lecture tends to drop off.

And gets pretty dramatic by the end of the term

when you're lecturing, and nobody's there.

And I asked him what he did about it.

And he thought about it and he said,

there's only two things that can get students to come

to lecture, candy and sex.

Now we've already tried candy, so today we're

going to talk about sex.

In fact we're going to use graph theory

to address a decades old debate concerning

the relative promiscuity of men versus women.

Now graphs are incredibly useful structures in computer science,

and we're going to be studying them for the next five or six

lectures.

They come up in all sorts of applications, scheduling,

optimization, communications, the design

and analysis of algorithms.

In fact next week, you're going to see how to Stanford

graduate students became gazillionaires

because they use graph theoretic in a clever way.

But let's talk about sex.

The issue that we're going to address today

is one of the most talked about, and most well studied,

questions in all of human sociology.

On average, who has more opposite gender partners,

men or women?

Now opposite gender is going to be important.

And by this I mean, one boy, and one girl.

All right, I'm not making a political statement.

It's just that the math is a lot easier that way, as you'll see.

Now I'd like to start by taking a pole here

to see what you think about that.

So raise your and if you think men, on average,

have more opposite gender partners than women do.

Only a few.

AUDIENCE: In life or [INAUDIBLE]

PROFESSOR: Um, you can--

[LAUGHTER]

PROFESSOR: One on one.

OK, so let's say over the course of their lives, let's say,

or over the course of 2010, that men in America

have more opposite-gender partners than women in America,

say in 2010.

Raise your hand if you think men have more going on.

All right a bunch of you.

Raise your hand if you think women have

more opposite-gender partners?

This is unusual.

Maybe even more voted for women, but it's close.

Raise your hand if you think it's equal.

All right, about the same.

Raise your hand if you think there's no way to know,

that it's hopeless to really figure it out.

All right, nobody goes for that.

All right, good.

All right well now in the popular literature,

I think the feelings are different than expressed here.

Pretty much universally, in the literature,

it's believed that men have more opposite-gender partners

than women.

And in fact, you could even think

about that, if you think about literature,

the leader of the harem is always a man.

And he's got lots of women.

In polygamist cultures, it's always

the man that has multiple wives, not the reverse.

Now not surprisingly, this issue has

been studied "scientifically," I'll

put in quotes, extensively, in one of the largest studies ever

done.

Researchers from University of Chicago

interviewed 2,500 people, at random, over several years.

They brought them in, on many occasions,

to try to get the answer for the question once and for all.

And they wrote this 700 page book,

called The soul of Social Organization of Sexuality:

Sexual Practices in the US.

Actually walking around with this book

has proved to be a little embarrassing.

Last week my 11-year-old daughter saw it,

and she goes dad, why do you have this sex book.

And I grabbed it back and said, well that's for the course.

I'm teaching.

And I thought I'd gotten away with it,

and everything was fine.

And then later that day she texted all of our friends

about the new news that what do you know,

her dad teaches sex ed at MIT.

Anyway this study concludes that on average men

have 74% more opposite-gender partners than women.

There's one other central claims.

And this is in the US.

OK now, when you think about it that sounds maybe reasonable,

might be OK.

But not according to ABC News.

They did a poll of 1,500 people in the country, in 2004,

and concluded that the average disparity is much greater.

In particular, in this study, they

said that the average man has 20 partners--

I'm assuming over their lifetime--

and the average woman has six.

And this gives a disparity 233%.

So ABC News did a smaller survey says that it's 233% here,

much more than 74%.

Now ABC News claimed this is one of the most

scientific studies ever done.

And there was a 2.5% margin of error.

Now we'll actually talk about what that means mathematically

later in the term when we do probability, and do

study polling.

Now of course I should also mention

that ABC News is the one that said

Al Gore won the presidential election in 2000.

Now the study is called American Sex Survey,

a Peak Between the Sheets.

That doesn't sound so scientific.

And it was on TV, on Primetime Live in 2004.

The promo for this is really good.

It says, a groundbreaking ABC News Primetime Live survey

finds a range of eye popping sexual activities, fantasies,

and attitudes in this country, confirming

some conventional wisdom, exploding some myths,

and venturing where few scientific surveys have

gone before.

By the end of today, we're going to agree

with that last statement.

OK now who do you think's right?

University of Chicago.

Who votes for 74% as being pretty close?

A few of you.

I've already slammed these guys.

Who votes for ABC News as being more accurate?

Yeah, nobody.

Who votes for no way to tell?

I got some votes there, all right.

So how do you tackle this problem?

In theory we could do our own 6.042 survey.

I don't know how much we'd really learn,

and for sure I'd get fired.

So I don't think we're going to do that.

But fortunately, this is the kind of question

that could be handled, and actually

answered, by graph theory, even though it might

be more interesting to interview thousands of people,

and find out what's going on.

That's not as efficient as using graphs.

So let me start by defining what a graph is.

Informally graph is just a bunch of dots and lines

connecting the dots, it's actually very simple.

So here's to graph.

These are the nodes, and they're connected

with these lines, called edges.

And often the nodes, and sometimes the edges,

are labeled.

For example, we might call this x1, x2, x3, x4, x5, x6, and x7.

So that's an example of a graph.

Now this being a math class, we got

to give a formal definition of a graph.

And we'll usually use the formal definition.

A graph G is a pair of sets often called V and E.

Where V is a set of elements called vertices or nodes.

And it has to be non-empty here in this class.

And we'll go back and forth between vertices and nodes.

Even the text we use both words interchangeably.

And E is a set of 2-item subsets and V,

and they're called edges.

So for example, over here in this picture,

V is the set of nodes is x1, x2, x3, up to x7, that's the nodes.

And E, the set of edges, is pairs,

unordered pairs of vertices.

So for example x1, x2 is an edge.

And it's the same as the set x2, x1,

doesn't matter the order here.

Later in a week or so, we'll talk about directed graphs

where the order matters.

x1, x3 is also an edge here, and so one.

Think we've got, let's see, 1, 2, 3, 4, 5, 6,

7 edges in this graph.

And the last one would be x5, x7.

Edges are also sometimes written with this notation, x1 line x2,

is another notation.

And then later when you talk about directed edges,

we'll put a little arrowhead on one end of this.

Now the definition of a graph is really pretty simple.

Just think of it as dots and lines, if you want.

But there's often differences in how people define graphs.

For example, in this class we don't allow the empty graph,

i.e. the graph with no nodes.

So we're going to insist that every graph has to have

at least one node in it.

And that's just to make the theorems

we're going prove be true.

Otherwise there's some theorems that

are false for the special case of the empty graph.

But we don't require the graph to have any edges.

In fact, it's possible you have a graph with nodes,

but no edges.

For example, this graph.

Three-node graph.

So here G equals VE, V equals x1, x2, x3.

And E is just the empty set.

Now for a general graph, when you do have edges,

we say that two nodes, call them xi and xj,

are adjacent if they're connected by an edge, namely

if xi xj is an edge.

All right so for example, x5 is adjacent to x7,

but it's not adjacent to x4, there's no edge there.

Closely related is the definition of the incidence.

An edge E, which is xixj, is said

to be incident to its end points, xi and xj.

OK so, for example, if I labeled that edge as E, E

is the edge x1, x2, and this incident to x1, and incident

x2.

Then we can talk about the degree of a node.

The number of edges incident to a node

is called the degree of the node.

So for example, what's the degree of x5 over here?

3, so in this case, the degree of x5 equals 3.

The degree of x7 is 1.

These guys all have degree 0, there's

no edges incident to them.

Now in this class, we're going to look at only simple graphs,

at lease for a while.

A graph is simple if it has no loops, or multiple edges.

Now a loop is an edge that only connects up one node, that's

a loop and we don't allow it.

A multiple edge is we've got two edges that are really the same,

they connect the same endpoints.

Also called a multi-edge.

And those we're not going to have in simple graphs.

We don't allow this.

We don't allow that.

Any questions so far about what a graph is?

So how are we going to use a graph

to model the problem of opposite-gender partners?

That's the question we're after.

So any thoughts about what the nodes of the graph

are going to represent?

What is it?