Wikipedia:Reference desk/Archives/Mathematics/2012 September 15

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 15

connected graphs

Is there a known pathological set of vertices for which the Urquhart graph, the Gabriel graph or the relative neighborhood graph is not connected? If not, is nonexistence proven? —Tamfang (talk) 07:06, 15 September 2012 (UTC)

Hmm. If the number of points is finite, then you can prove by induction that the relative neighborhood graph is connected. There are only finitely many pairwise distances between the points. Consider these pairwise distances in increasing order to prove that any two points are in the same connected component: Two points that are separated by the minimum pairwise distance (among all pairs of points) must be joined by an edge. Now consider two points A and B that are separated by more than the minimum pairwise distance. Either they are joined by an edge, or else there is a third point C whose distances from A and from B are strictly less than the distance between A and B. By induction, A and C are in the same connected component, and B and C are in the same connected component; so A and B are in the same connected component. —Bkell (talk) 08:31, 15 September 2012 (UTC)

Or how about this for the Urquhart graph, to separate two figures you'd need to have a cycle of triangles which each had two sides removed. One of those sides in the circle must be the smallest so why was it removed? Dmcq (talk) 08:38, 15 September 2012 (UTC)

If you have a graph where all the lengths round the cycle are the same so there is no consistent ordering then you can separate it in two but that's rather straining it. Eg you can do that with a large seven sided regular figure with a smaller one at its centre. Dmcq (talk) 14:53, 15 September 2012 (UTC)

Recurrence relation

I was thinking about what would happen if a player keeps scoring one more than his average. Let's say a cricketer has an average L_n after n matches. Let's say in the next match, he scores L_n+1. His new average will be

L_n+1 = (n * L_n + L_n + 1) / (n + 1)

Hence we have the recurrence,

L_n+1 = L_n + 1 / (n+1)

Now since L_n+1 - L_n tends to zero as n tends to infinity, I know that the series converges. But how do I find out the number it converges to? Can someone please solve this recurrence for me?

Also, more generically, if a cricketer scores (k * L_n + c) more than is average instead of just one more, what would his average converge to? Note that if we ave k = c = 1, it reduces to the case we talked about above.

Help will be appreciated ! Rkr1991 ^{(Wanna chat?)} 11:01, 15 September 2012 (UTC)

I was working some more on this, and I find that the general series seems to converge for any value of k less than 2. Is this correct? And if so, how can I find the limit? Rkr1991 ^{(Wanna chat?)} 11:01, 15 September 2012 (UTC)

You cannot conclude that a sequence converges if the change tends to zero. The initial recurrence relation you give is, aside from an initial additive constant L₀, the harmonic series, which diverges (albeit very slowly). — Quondum 11:48, 15 September 2012 (UTC)

Yeah, there's no convergence at all. You can determine this just by thinking about the problem without actually doing any calculations. If a cricketer plays forever and keeps scoring any constant positive value more than his average every game, then his score for each specific game will diverge toward infinity, and his average score for all games will follow and diverge toward infinity as well (though ever more slowly, requiring ever more games for the same amount of increase). An increasing sequence does not necessarily converge even if the steps get smaller; the steps have to get smaller at a sufficient rate, and the rate of decrease described in your problem isn't sufficient. —SeekingAnswers (reply) 16:02, 17 September 2012 (UTC)