Wikipedia:Reference desk/Archives/Mathematics/2008 September 27

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 27

Monochromatic triangles in a graph

Suppose the edges of $K_{n}$ (a complete graph with n vertices) are colored red or blue arbitrarily. How many monochromatic triangles are guaranteed to exist?

I am assuming that n is at least 6 so that 1 such triangle is guaranteed by Ramsey's theorem. Also I know that the answer is 2 for n=6 but I can't prove it. Can anyone help? Regards--Shahab (talk) 10:34, 27 September 2008 (UTC)

I have no idea about the general case, but your answer for the n=6 case is shown correct to be a lower bound by the alternative proof in the first example of the Ramsey's theorem article. 84.239.160.166 (talk) 12:15, 27 September 2008 (UTC)

I am sorry but I can't seem to understand that proof also. I'm trying to figure it out. Also my book has a hint for the original problem. Maybe I should have posted that too initially. It says: Let $r_{i}$ be the number of red edges connected to vertex i. Show that the number of monochromatic triangles is thus ${\binom {n}{3}}-{\frac {1}{2}}\sum _{i-1}^{n}r_{i}(n-1-r_{i})$. Minimize this function to deduce the result. Regards--Shahab (talk) 12:41, 27 September 2008 (UTC)

Is your problem with interpreting the formula or minimizing it? The idea in the proof mentioned above is not quite the same as in the formula, but very similar. I'm not sure if there's an easy way to minimize that formula accurately, but bounding it should be straightforward. 84.239.160.166 (talk) 13:47, 27 September 2008 (UTC)

I can't understand what ${\frac {1}{2}}\sum _{i-1}^{n}r_{i}(n-1-r_{i})$ represents. I suppose it is the number of non-monochromatic triangles, but I do not know why. About your second point, I think the question is asking for a lower bound. Regards--Shahab (talk) 13:55, 27 September 2008 (UTC)

It's not counting triangles, it's counting pairs of edges pretty much like the second (alternate) proof in the Ramsey's Theorem example. Working through that proof should be illuminating. 84.239.160.166 (talk) 15:22, 27 September 2008 (UTC)

A way you could approach this. Consider a k by k matrix representing the edges of the graph, entries are either red or blue and you just need to consider the elements above the diagonal. You'll have a coloured triangle if m_a,b=m_a,c=m_c,b. --Salix (talk): 13:16, 27 September 2008 (UTC)

Using a recursive approach. If you know there are a minimum of r monochromatic triangles for n points, then there must be at least 2*r monochromatic triangles for n+1 points. Consider a single monochromatic and add an extra point, at least one of the new triangles must be monochromatic as well. This is only a lower bound for the minimum though. --Salix (talk): 14:03, 27 September 2008 (UTC)

I can't understand you Salix. If I have a single monochromatic triangle consisting of red lines and I add an extra point, and join it to the three previous ones by blue lines, how do I get an extra monochromatic triangle? Maybe I haven't interpreted you correctly. Can you please elaborate. Regards--Shahab (talk) 14:15, 27 September 2008 (UTC)

Stupid me. I've been doing a computer test with complete enumeration results so far are n=6: 2, n=7: 4, n=8: 8. Which is looking a lot like 2^(n-5) it get a bit slow to do after that.--Salix (talk): 14:36, 27 September 2008 (UTC)

Why would you think the number of triangles could grow faster than cubically? —David Eppstein (talk) 19:48, 27 September 2008 (UTC)

OK. I have progressed this far. Let $r_{i}$ be the number of red edges connected to vertex i. Then $r_{i}(n-1-r_{i})$ is the number of triples (xiz) with xi red and iz blue. Now as $r_{i}$ varies from 0 to n-1 what will be the maximum value of $r_{i}(n-1-r_{i})$? (I plan to show that if X is the max value then ${\binom {n}{3}}-\lfloor {\frac {n}{2}}X\rfloor$ is the answer. Is this correct?) Also in the hint the summation runs from i-1 to n. But i is itself the variable. So does this make sense?--Shahab (talk) 00:29, 28 September 2008 (UTC)

For anyone who is interested I have found the answer. i.e. the # of monochromatic guaranteed triangles to be ${\begin{cases}{\binom {n}{3}}-\lfloor {\frac {n(n-1)^{2}}{8}}\rfloor ,&{\mbox{if }}n{\mbox{ is odd}}\\{\binom {n}{3}}-\lfloor {\frac {n^{2}(n-2)}{8}}\rfloor ,&{\mbox{if }}n{\mbox{ is even}}\end{cases}}$--Shahab (talk) 05:45, 28 September 2008 (UTC)

That formula was enough to find it in OEIS: (sequence A014557 in the OEIS). —David Eppstein (talk) 06:06, 28 September 2008 (UTC)

Integration Question

What is the best strategy for finding the integral of sin x × (1+cos x)⁴ ? —Preceding unsigned comment added by 86.156.7.131 (talk) 20:24, 27 September 2008 (UTC)

If you want something to the fourth power, then you might want to try starting with the fifth power. What's the derivative of (1+cos x)⁵? Can you use that? -- Jao (talk) 20:29, 27 September 2008 (UTC)

Alternatively, you could spot that you have something and its derivative in the integrand - that usually means you should try substituting for the something. --Tango (talk) 20:57, 27 September 2008 (UTC)

The strategy is to include the differential dx in the expression to be integrated. So you have dy = (1+cos x)⁴ sin x dx. Now try to move the differentiation sign d to the left observing the rules of differentiation. You know that sin x dx = d(something). When the d has been moved all the way to the left you have dy=d(something), and the integral is y=something+constant. Bo Jacoby (talk) 22:21, 27 September 2008 (UTC).

Since

$\sin x\,dx$

is the differential of

$-\cos x,\,$

You can start with

$u=1+\cos x,\,$

so that

$-du=\sin x\,dx.$

Then

$\int (1+\cos x)^{4}\sin x\,dx=\int u^{4}\,(-du)$

and you're just integrating a polynomial. Michael Hardy (talk) 00:52, 28 September 2008 (UTC)

PS: "Tango"'s point is really what you need to learn. What I gave is the ensuing details. Michael Hardy (talk) 00:56, 28 September 2008 (UTC)