- #1

- 618

- 0

Thanks.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter K.J.Healey
- Start date

- #1

- 618

- 0

Thanks.

- #2

mathwonk

Science Advisor

Homework Helper

2020 Award

- 11,266

- 1,468

Background on the problem, by John Milnor:

http://www.math.sunysb.edu/~jack/PREPRINTS/poi-04a.pdf

As a second step, see Milnor's next article on the progress towards

the conjecture & classifying three-manifolds:

http://www.math.sunysb.edu/~jack/PREPRINTS/tpc.pdf )

On the recent solution:

Speaker: Jason Parsley, University of Georgia

Title of talk: Introduction to the Poincare Conjecture

Abstract: In 1904, Poincare conjectured that every closed,

simply-connected three-dimensional manifold is homeomorphic to the

three-sphere. This problem remained unsolved for almost 100 years.

Recently, Perelman posted a couple of papers on the Ricci flow, an

equation of manifolds evolving based on their curvature, that implied

Poincare's conjecture was true.

In this talk, we will start by defining all relevant terms, then briefly

describe the history of the Poincare conjecture and mention analogs in

higher dimensions. We touch on Thurston's Geometrization Program, which

roughly says that there are exactly eight different types of geometries

that are possible for three-dimensional manifolds. If time allows, the

last few minutes will be devoted to how Hamilton and Perelman used

Riemannian Geometry to attack this problem.

*************************

R. Jason Parsley

VIGRE Postdoc

Department of Mathematics

University of Georgia

706.542.2562

*************************

- #3

- 746

- 13

Healey01 said:Does anyone have a list of decent sites which include a range of either unsolved mathematical problems, or unproven formulae? There used to be on liked from my employer's mathematical index, but it is no longer there.I understand that the possibility of doing something like finding all the zeros of the riemann zeta function is impossible for most of the world's population(including me), but regardless, I am curious as to where the mathematics train consistently runs into the wall. I'm mostly interested in the history of theory that went unproven for a long time and what it took (both time and ingenius mathematical concepts) to solve or prove these theories.

Thanks.

i think you deify mathematicians/profs too much. but just as there are good & bad dishwashers/janitors/7-11 attendants, i guess there are good & bad mathematicians. they're like everyone else really, some just don't like to admit it.

anyway, the rest of the clay math problems (besides the poincare conjecture) here:

http://www.claymath.org/millennium/ [Broken]

other unsolved problems include the following:

a. the invariant-subspace problem (= whether there is a separable, infinite-dimensional banach space on which every linear operator has an invariant subspace. i think it's a natural generalization of a theorem that burnside proved but i can't remember what it was)

b. whether every finite group H occurs as the Galois group of a finite Galois extension of the field of rational numbers. shafarevich proved this for solvable H & others (like hilbert) proved other special cases but the general problem is still unsolved.

Last edited by a moderator:

- #4

honestrosewater

Gold Member

- 2,132

- 5

mathworld lists several problems and links.

Last edited:

- #5

Alkatran

Science Advisor

Homework Helper

- 954

- 0

1: Take input and create a list of the students alongside the students they are incompatible with.

IE if roger can't go with tom, and the list is roger, tom, and becky, we get:

Roger -> tom

tom -> roger

Becky

2: Create a variable N and set it to 0. Then loop step 3 while remainingstudents > 0 and acceptedstudents < requirement

3: Construct a loop which goes through the list of students adding them to the list

3a: For(int m = 0, remainingstudents > m && acceptedstudents < requirement, m++)

-For the non Java types, that means start m at 0, check if the conditions are met, and for every new iteration of the loop, increase m by 1.

3b: Check if the number of students disallowed by the current student is equal to n.

If it is then add the student to the accepted list and remove all the students disallowed by this student from the entrance list. (adjust m as necessary)

3c: end of loop

4: end of loop involving n

5: Return wether or not the number of accepted students is at least the amount of needed students

There. That will run in...

n goes from 0 to a maximum of the number of students - 1

m goes from 0 up to at most the number of students

in the worst case scenario, where everyone is paired with everyone, removing students from the list will take the ~number of students squared operations. But n and m would not be looped at all, but I will just say that there can be a squared time inside that loop.

Final time (overestimated) ~ O(x^4)

(n from 0 to x, m from 0 to x, removing from list is (0 to ~x, 0 to x))

The logic behind this is to add any student who is paired with very few students. By adding this student you are forcing the exit of another student who would force the exit of at least, if not more, students. This method should work for all inputs.

- #6

- 591

- 0

Alkatran said:The logic behind this is to add any student who is paired with very few students. By adding this student you are forcing the exit of another student who would force the exit of at least, if not more, students. This method should work for all inputs.

I don't think your algorithm will actually work. It sounds like an algorithm that might find the correct solution, but might also fail when a solution exists.

- #7

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

Here's an example where we try to pick three students out of 7. Here's the list of unacceptable pairs:

14 15 16 17 24 25 26 27 34 35 36 37 56 57 67

So, for example, 14 means that 1 and 4 aren't compatable.

Now, here's the counts of how many students are incompatable with a selected student:

1 4

2 4

3 4

4 3

5 5

6 5

7 5

Here, the greedy pick is to first accept student #4. This means we cannot pick students 1, 2, or 3. Therefore, we must also accept two of the students numbered 5, 6, and 7, but they are all incompatable with each other!

The only solution here is to accept students 1, 2, and 3.

- #8

- 137

- 0

Hurkyl said:

Here's an example where we try to pick three students out of 7. Here's the list of unacceptable pairs:

14 15 16 17 24 25 26 27 34 35 36 37 56 57 67

So, for example, 14 means that 1 and 4 aren't compatable.

Now, here's the counts of how many students are incompatable with a selected student:

1 4

2 4

3 4

4 3

5 5

6 5

7 5

Here, the greedy pick is to first accept student #4. This means we cannot pick students 1, 2, or 3. Therefore, we must also accept two of the students numbered 5, 6, and 7, but they are all incompatable with each other!

The only solution here is to accept students 1, 2, and 3.

Nice points, but I think it's a little worse than that.

For simplicity let's call two students that can't be paired,

In this case N (or is it n?) never changes; it stays at 0. In fact it doesn't appear that n/N changes even if a student is removed from the candidate list and added to the accepted list. However, it does look like there is some kind of general plan to increment n/N; but when or why? That's an important detail.

There's not much point to guessing what was intended since "obvious" choices of what was intended lead to incorrect algorithms as well.

- #9

- 746

- 13

-- extend the mathematical model of general equilibrium theory to include price adjustments (introduce dymanics into economics)

-- is there a polynomial-time algorithm over the real numbers which decides the feasibility of the linear system of inequalities Ax >= b?

-- can a zero of n polynomial equations in n unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?

-- what are the limits of intelligence, both artificial and human?

those are from smale's article referenced in that mathworld page. there were 18 problems in total; some are on the clay list (navier-stokes equations, riemann hypothesis, poincare conjecture) & i don't really get the other ones

- #10

Alkatran

Science Advisor

Homework Helper

- 954

- 0

Hurkyl said:

Here's an example where we try to pick three students out of 7. Here's the list of unacceptable pairs:

14 15 16 17 24 25 26 27 34 35 36 37 56 57 67

So, for example, 14 means that 1 and 4 aren't compatable.

Now, here's the counts of how many students are incompatable with a selected student:

1 4

2 4

3 4

4 3

5 5

6 5

7 5

Here, the greedy pick is to first accept student #4. This means we cannot pick students 1, 2, or 3. Therefore, we must also accept two of the students numbered 5, 6, and 7, but they are all incompatable with each other!

The only solution here is to accept students 1, 2, and 3.

14 15 16 17 24 25 26 27 34 35 36 37 56 57 67

Create list

1 - 4, 5, 6, 7

2 - 4, 5, 6, 7

3 - 4, 5, 6, 7

4 - 1, 2, 3

5 - 1, 2, 3, 6, 7

6 - 1, 2, 3, 5, 7

7 - 1, 2, 3, 5, 6

I see the problem now. They're blocking the same people! Well, I guess I got snookered. Damn. Hmmmm problem is interesting now!

I know the problem is apparently unsolveable, but there's

I'm thinking of perhaps only counting equal sets once. But that can be beaten by adding 8 and 9 as enemies of eah other, 1 and 2... Perhaps grouping similar sets together... to get 3 * the set / 4... But then we need to sort since it's not integer...

- #11

- 746

- 13

http://en.wikipedia.org/wiki/Category:Conjectures

http://en.wikipedia.org/wiki/Unsolved_problems_in_mathematics

http://en.wikipedia.org/wiki/List_of_open_problems_in_computer_science

- #12

- 175

- 0

Take care.

Share: