Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was watching this TED talk, which suggested that on average your friends tend to individually have more friends than you do. To define this more formally, we are comparing the average number of friends with:

average over each person p of:
    friend popularity, defined as:
    average over each friend f of p:
        number of friends f has

Intuitively, this seems to make sense. After all, if someone has a high number of friends, they will tend to increase friend popularity and affect a high number of people, while those people who decrease friend popularity only affect a low number of people. Does this result hold for all graphs?

Given a person p, let t stand for:

sum over each friend f of p:
    number of friends f has

It is pretty clear that sum(t)=sum(f^2) as a person with f friends has value of f towards their f friends value of t.

We are then trying to determine whether: sum(t/f)>sum(f) holds for all graphs.

share|improve this question
2  
As I recall, there was an informal discussion of something like this in one of Gladwell's books... that being said, this is probably more sociological than mathematical. –  J. M. Dec 15 '10 at 11:46
4  
@J.M. I have provided an exact graph theory question that should be answerable mathematically. Does sum(t/f)>sum(f) hold for all graphs or is there a counter example? –  Casebash Dec 15 '10 at 11:49

2 Answers 2

up vote 15 down vote accepted

The answer is yes, this holds for any graph (with weak inequality, as Jon points out).

Let's set up some notation. The graph of friendships is $G$. The set of vertices of $G$ (the people) is $V$; the set of edges (the friendships) is $E$. For a person $v$, the number of friends that person has is $\deg v$. The total number of people is $n$.

We want to show that $$\frac{1}{n} \sum_{v \in V} \deg v \leq \frac{1}{n} \sum_{v \in V} \frac{1}{\deg v} \sum_{(u,v) \in E} \deg(u).$$

Cancel the $1/n$'s from both sides. After a little rewriting, we want to show that $$\sum_{v \in V} \sum_{(u,v) \in E} 1 \leq \sum_{v \in V} \sum_{(u,v) \in E} \frac{\deg u}{\deg v}. \quad (*)$$

Let's consider what a given edge $(u,v)$ contributes to each side of $(*)$. On the left, it contributes $1+1=2$. On the right, it contributes $(\deg u)/(\deg v) + (\deg v)/(\deg u)$. For any two positive numbers $x$ and $y$, we have $2 \leq x/y+y/x$. So every edge contributes more to the right hand side of $(*)$ than to the left, and we have the claimed result.

share|improve this answer
3  
By the way, a standard heuristic for this sort of problem: Try to get all your sums to be over the same index set, even at the expense of doing something like replacing $\deg v$ by $\sum_{(u,v) \in E} 1$. –  David Speyer Dec 15 '10 at 14:17
1  
That's a very nice proof. So the core observation is that each edge contributes 2 to the total number of friends, but deg u/deg v+deg v/deg u to the number obtained by adding each person's friend popularity. Also, its worthwhile noting that 2≤x/y+y/x is easily proved using either calculus or the AM-GM inequality, just in case anyone doesn't know that –  Casebash Dec 15 '10 at 22:07
    
To clarify my previous comment: deg u and deg v are the degrees of the vertices after the graph has been completed. As it is worded, my comment could have been incorrectly interpreted to be referring to a situation where a graph is built one edge at a time and the degree is the degree at this stage of construction. That is probably why I didn't spot this solution - you consider the effect that each edge being added separately has at the end, rather than the effect right now. –  Casebash Jul 25 '12 at 14:57

Trivial comment, but I'm new so I have to post it as an answer: The strict inequality definitely doesn't hold in general, since the sums are equal for regular graphs.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.