Mathematics desk
< September 17	<< Aug \| September \| Oct >>	September 19 >

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 18[edit]

Finding maximum clique in a largish graph[edit]

I have a particular graph with 67,230 vertices and 1,116,605,284 edges, and I'd like to find a maximum clique in it. I realize this is an NP-complete problem. However, maybe there is some algorithm that will run fast enough for me to get an answer for this graph. Does anyone know about the run times of various algorithms for specific sizes of graphs?

On the other hand, for my purposes a "pretty big" clique would probably be good enough. I'm thinking about taking a greedy approach and doing that several times to try to find a "pretty big" clique; since my graph contains 49.4% of the possible edges, it might look similar to the random graph $G(67230,1/2)$ , so a greedy approach might get me within a factor of 2 (based on what I read in the fourth paragraph of Clique problem#Special classes of graphs). Does anyone have any suggestions for this or another approach I should take here? Otherwise I'm probably just going to try something and see how well I can do. —Bkell (talk) 01:25, 18 September 2010 (UTC)[reply]

I have no idea if anything here might be useful. 67.119.14.196 (talk) 22:32, 19 September 2010 (UTC)[reply]

Placing equally spaced vertices in a curve (but not based on arc length)[edit]

I'm trying to find the name of this problem so I can read the existing literature on the subject, but I'm not finding anything.

I have a real-valued, continuous function $f$ . For a given value $x$ , I want to find a value $a$ so that the distance from the point $(x,f(x))$ to the point $(x+a,f(x+a))$ equals $r$ .

Does this sound familiar to you guys? How can I read more on these kinds of problems? Could you point me to the right direction on which methods I could use to solve it? Approximations are fine.

If x is a fixed parameter, then can't you just solve for a with your favorite numerical root finding method? 67.119.14.196 (talk) 05:47, 18 September 2010 (UTC)[reply]

It's what I'm doing. Just wondering if there's something better out there.

You're trying to find the intersection of a circle with an arbitrary curve. If that's all you have to go on, you're left with general methods. 67.119.14.196 (talk) 16:10, 18 September 2010 (UTC)[reply]

The existing literature on the subject would switch variable names such that a is the constant and x is the unknown. Bo Jacoby (talk) 06:35, 18 September 2010 (UTC).[reply]

Casimir Operator[edit]

I am wondering how to prove that the casimir operator acts as a scalar matrix if the ground field is not algebraically closed. I tried a math forum. it should be either obvious or wrong. In weibel's homological algebra, the result is stated as if it was obvious. --80.99.46.164 (talk) 08:05, 18 September 2010 (UTC)[reply]

Inequality question- For which values of k does the inequality hold for all real values of x?[edit]

Here is the equation [1] I have tried to solve it, but can only arrive at $k<{\frac {-3}{2}}$ or $k>{\frac {3}{2}}$ . I have told that it is wrong. Are there any other conditions for the inequality to hold for all real values of x? —Preceding unsigned comment added by Invisiblebug590 (talk • contribs) 08:17, 18 September 2010 (UTC)[reply]

First note that k must be positive, as otherwise the expression will be negative for very large x. Also note that the denominator must have no roots, as otherwise the expression is undefined for certain x. Finally, the numerator must have no roots, as otherwise the expression is 0 for certain x. Those conditions should suffice.--203.97.79.114 (talk) 09:02, 18 September 2010 (UTC)[reply]

Every real/complex algebra, generated by real-symmetric matrices is semisimple?[edit]

Hello,

I have yet another question about semisimple algebras.

Every algebra (real or complex, not really clear to me if both hold) generated by real-symmetric matrices is semisimple.

I have seen this being used in many articles, without any explanation or reference. Is this true and if so, which theorem is being relied on?

Many thanks,Evilbu (talk)

Let A be an algebra over the reals generated by real symmetric matrices. Note that if a is in A, then so is the transpose of a (use the fact that (ab)^T = b^T a^T, where the T denotes transpose). Now suppose A has a non-zero radical, so it has a non-zero nilpotent ideal I. Let x be a non-zero element of this ideal, so y= x.x^T is also in I, and is symmetric and non-zero (to show y is non-zero use the fact that if a linear map has matrix x with respect to an orthonormal basis, then its adjoint has matrix x^T). But no non-zero symmetric matrix can be nilpotent, since it is diagonalisable. I learned this argument from a paper by Eugene Gutkin in Phys. Let. A Tinfoilcat (talk) 19:05, 18 September 2010 (UTC)[reply]

If you see this used in an article without explanation or references the please add a {{fact}} or similar tag. I think it WP standards were being followed more then this question would not need to be asked.--RDBury (talk) 01:00, 19 September 2010 (UTC)[reply]

Thank you both. However, I still have some questions and remarks. First of all, I meant "articles in journals" (not Wikipedia-articles, sorry for the confusion). Secondly, does that argument also work for algebras generated by realsymmetric matrices over the complex numbers. Finally, I do think there might be a problem in Semisimple algebra because there it is claimed that the radical is the unique nilpotent ideal containing all nilpotent elements of the algebra, and that finitedimensional algebras are semisimple iff the radical is trivial. But this would imply that a matrix ring over a field is not semisimple (as there are nontrivial nilpotent elements) while that ring is even simple.Evilbu (talk)

The article semisimple algebra is wrong, for exactly the reason you mention, probably due to some confusion with the commutative case. I fixed it. The argument above for semisimplicity actually appears in that article. 129.67.37.143 (talk) 13:30, 19 September 2010 (UTC)[reply]

American Mathematicians[edit]

why is it that you never hear of (white, Western European-descent) American mathematicians ? Wikipedia will attest that there are many (there's a list somewhere) but when speaking of solving unsolved problems the persons involved will always be Chinese (or Indian, less commonly other Asian) or Eastern Europeans (I'm generalizing a bit, but this is most often the case) If they are American, then they'll be either immigrants from those nations or be first generations from those nations 24.92.78.167 (talk) 15:52, 18 September 2010 (UTC)[reply]

Looking at the table in Fields medal, I see about 25% of the medalists are listed next to US flags. 67.119.14.196 (talk) 16:22, 18 September 2010 (UTC)[reply]

Of those, the vast majority have Western-European sounding surnames. What is the issue here? Are you just annoyed because you can never remember how to pronounce Chebyshev's inequality? Yaris678 (talk) 18:13, 18 September 2010 (UTC)[reply]

See Category:American mathematicians. -- Wavelength (talk) 18:27, 18 September 2010 (UTC)[reply]

Hear of where? I think you'll find that amongst the general public the most famous mathematician in the world is that guy on Numb3rs.--RDBury (talk) 01:05, 19 September 2010 (UTC)[reply]

I hear of, and meet, American mathematicians incessantly. Just a moment ago I edited the article about William Thurston. Michael Hardy (talk) 16:44, 19 September 2010 (UTC)[reply]

There are a lot of Ph.D. students and post docs from Asia and Russia in the US (also in Europe). During lunch time, it often happens that you're sitting at a table where lively discussions are going on in Chinese. Count Iblis (talk) 15:47, 19 September 2010 (UTC)[reply]

Index of a subgroup[edit]

Resolved

Let m be a natural number and p a prime. Consider the multiplicative (mod p) group $Z_{p}^{*}$ , and its subgroup $H=\{x^{m}:x\in Z_{p}^{*}\}$ . What will be the index of this subgroup? I have the answer in my book as gcd(m,p-1) but I have no idea how this comes about. Thanks - Shahab (talk) 16:19, 18 September 2010 (UTC)[reply]

Do you know about Lagrange's theorem? How many elements does

Z_{p}^{*}

have? What does the subgroup generated by x^m look like? 67.119.14.196 (talk) 22:17, 18 September 2010 (UTC)[reply]

I know of Lagranges theorem.

Z_{p}^{*}

is cyclic and has p-1 elements, and for a fixed x, the subgroup generated by x^m is of the form {x^mk:k is an integer}. Its order will be O(x)/gcd(m,p-1) whch divides p-1. Now what should I do? If x generates

Z_{p}^{*}

then by elementary number theory, the index of such a subgroup is (m,p-1). But that doesnt answer my question-Shahab (talk) 03:03, 19 September 2010 (UTC)[reply]

Suppose g is a generator of

Z_{p}^{*}

. Then, as you say, the subgroup generated by g^m is

G=\{g^{mk}:k\in Z\}=\{(g^{k})^{m}:k\in Z\}

So

G\subseteq H

. But for each

x\in Z_{p}^{*}

there is an integer a_x such that

x=g^{a_{x}}

, so

H=\{g^{ma_{x}}:x\in Z_{p}^{*}\}

So

H\subseteq G

. Put this all together and you have H = G. Gandalf61 (talk) 10:09, 19 September 2010 (UTC)[reply]

Thanks. Regards-Shahab (talk) 15:48, 19 September 2010 (UTC)[reply]

Base and mod, 2 qs[edit]

Is it correct that the value of x (mod n) is the same as the final (rightmost) digit in base n? And what field of study would the study of bases fall in? Could you have a base with a variable in it? —Preceding unsigned comment added by 24.92.78.167 (talk) 16:24, 18 September 2010 (UTC)[reply]

The answer to the first question is false, like 15 is 0 mod 3, while its right most digit 5 is 2 mod 3. It is true for n=2 though.-Shahab (talk) 16:47, 18 September 2010 (UTC)[reply]

[ec] 15 is

120_{3}

in base 3, and its rightmost digit is 0, which is 15 mod 3. And likewise for any other nonnegative number, so the answer to the first question is yes. You may find more information in Numeral system. -- Meni Rosenfeld (talk) 17:45, 18 September 2010 (UTC)[reply]

I mean the rightmost digit of the number x written in base n. For example 15 in base 3 is 120 and the right most digit 0 is congruent to 15 mod 3 —Preceding unsigned comment added by 24.92.78.167 (talk) 17:44, 18 September 2010 (UTC)[reply]

Oh, I misunderstood :).-Shahab (talk) 17:54, 18 September 2010 (UTC)[reply]

Also note that log_n x is related to the number of digits it takes to represent x in base n. Taking the example above of 15 = 120₃, log₃ 15 = log 15 / log 3 ≃ 2.46, so it takes three digits (120) to represent 15 in base 3. In general, it takes ⌊log_n x⌋ + 1 digits to represent x in base n. See Logarithm#Uses and occurrences. -- 124.157.249.242 (talk) 08:06, 19 September 2010 (UTC)[reply]

Higher Dimensional Results[edit]

There's a theorem that says that given a continuous map ƒ from the sphere to the plane, there will always be two antipodal points, say p and q, such that ƒ(p) = ƒ(q). The proof employs the fundamental group. Does anyone know of any higher dimensional results? Take a continuous map from a hypersphere to a hyperplane. Are there always antipodal points, maybe even submanifolds of antipodal points, with the same property? — Fly by Night (talk) 17:37, 18 September 2010 (UTC)[reply]

The Borsuk–Ulam_theorem states that for a continuous map from the n-sphere to the Euclidean n-space there is a pair of antipodal points that map to the same point. Invrnc (talk) 23:14, 18 September 2010 (UTC)[reply]

Thanks for that. Any idea about stronger results, i.e. submanifolds of antipodal points, with the same property? — Fly by Night (talk) 22:43, 19 September 2010 (UTC)[reply]

I doubt a stronger result like that is true. Just thinking about S¹ and S², you're only guaranteed one pair of antipodal points in both cases. Maybe if you decreased the dimension of the hyperplane you're mapping to you could guarantee a higher dimensional manifold on Sⁿ satisfying the condition. For example any map from S² to R has a loop of points each with the same value as their antipodal point. My naive conjecture would be that for continuous f:Sⁿ → R^k, there must be an (n-k) dimensional submanifold M (homeomorphic to S^n-k?) with each point p in M satisfying f(p) = f(-p). Pretty sure it should be true for k = 1, and apparently it's true for k = n, but I have no idea if it's true generally. I don't know much topology and I haven't thought much about it. Rckrone (talk) 17:05, 20 September 2010 (UTC)[reply]

Yeah, that was what my intuition was telling me too. I was hoping that there might be a known theorem so that I might study the methods used in proving it. Thanks again! — Fly by Night (talk) 17:46, 20 September 2010 (UTC)[reply]

Rado's theorem doubt[edit]

In Rado's theorem (Ramsey theory) it says in the last line: ...can be written as a linear combination.... Does it mean integer linear combinations or rational linear combinations? If the former, how does the special case of Rado's single equation theorem follow from the general theorem. - Shahab (talk) 19:12, 18 September 2010 (UTC)[reply]

Okay. Found the answer and updated the page.-Shahab (talk) 03:14, 19 September 2010 (UTC)[reply]