×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Erdos' Combinatorial Geometry Problem Solved

Soulskill posted more than 2 years ago | from the math-that's-way-over-your-head dept.

Math 170

eldavojohn writes "After 65 years, Paul Erdos' combinatorial problem has been solved by Indiana University professor Nets Hawk Katz. The problem involved determining the minimum number of distinct distances between any finite set of points in a plane and its applications range from drug development to robot motion planning to computer graphics. You can find a description of the problem here and the prepublication of the paper on arXiv. The researchers used the existing work on the problem and included two new ideas of their own, like using the polynomial ham sandwich theorem, to reach a solution that warranted at least half of Erdos' $500 reward posted for solving this problem way back in 1935."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

170 comments

Finally I can sleep! (1)

adeft (1805910) | more than 2 years ago | (#35312176)

Showing absolute ignorance here, but anyone else think the "polynomial ham sandwich theorem" sounds like it was perhaps concocted by someone overweight?

Polynomial ham sandwich theorem? (0)

Anonymous Coward | more than 2 years ago | (#35312188)

Seriously ... you're not making this up?

Re:Polynomial ham sandwich theorem? (5, Funny)

RevWaldo (1186281) | more than 2 years ago | (#35312450)

Doesn't sound very kosher to me....

.

Re:Polynomial ham sandwich theorem? (-1)

Anonymous Coward | more than 2 years ago | (#35312500)

Doesn't sound very kosher to me.... .

These are math nerds, not bankers, politicians, or owners of media conglomerates. They aren't worried about eating kosher.

Re:Polynomial ham sandwich theorem? (1)

_0xd0ad (1974778) | more than 2 years ago | (#35312532)

Actually it's a theorem that was postulated by a pig named Ben who ruminated for a while and realised that in 4-space pigs would be kosher because there would be a specific 3-dimensional hyperplane which would split their 4 feet precisely in halves.

Re:Polynomial ham sandwich theorem? (1)

Dog-Cow (21281) | more than 2 years ago | (#35313052)

Except, of course, it isn't their feet that make them not-Kosher. /feels a strange blast of air over-head.

Re:Polynomial ham sandwich theorem? (1)

_0xd0ad (1974778) | more than 2 years ago | (#35313170)

Yeah... of the two applicable requirements for kosher (cloven hooves and ruminating), pigs actually do have cloven hooves.

It was kinda backward but I don't know how to make it into a proper joke the correct way. :/

Re:Polynomial ham sandwich theorem? (0)

Anonymous Coward | more than 2 years ago | (#35313498)

Not in 3-space, you insensitive hyperclod.

Re:Polynomial ham sandwich theorem? (1)

gstoddart (321705) | more than 2 years ago | (#35312548)

Doesn't sound very kosher to me....

Well, the "polynomial brisket sandwich" problem sounds more complicated, and the "polynomial reuben sandwich" actually involves a greater number of objects due to the increased number of pieces of meat, the sauerkraut and the pickle ... so it's actually higher complexity. You could wave away some of that by saying the meat is all one "piece" for purposed of discussion, but that might only appease the physicists and engineers.

It's only hypothetical ham, it's OK.

Re:Polynomial ham sandwich theorem? (2)

_0xd0ad (1974778) | more than 2 years ago | (#35312582)

You could wave away some of that by saying the meat is all one "piece" for purposed of discussion, but that might only appease the physicists and engineers.

No, the physicists have already approximated the pieces as point masses and they are all trying to figure out why you want to cut them in half.

Ham sandwich??? (4, Funny)

gstoddart (321705) | more than 2 years ago | (#35312206)

like using the polynomial ham sandwich theorem

Really? That's the coolest name for something I don't understand ever.

Hell, I'd have posted some of the google links to try to explain WTF it means ... but, quite frankly, I have no idea what any of them say. Can anybody put this wonderful sounding theorem into something that a layman has at least a passing chance of getting the gist of?

I'm sure whatever else the authors did was cool, but frickin' ham sammiches ... in math!! Awesome!

Re:Ham sandwich??? (5, Informative)

Anonymous Coward | more than 2 years ago | (#35312316)

Ham Sandwich theorem says that if you have n objects in n dimensional space, you can cut them all in half with a cut using an n-1 dimensional surface.

It's called Ham Sandwich because the analogy says if you have a chunk of ham, a chunk of cheese, and a chunk of bread (n = 3) in 3-D space, you can make a single "cut" to cut them all in exactly half. This single cut is achieved by finding the plane (3-1 = 2 dimensions) that goes through all of them.

Alternately, there's Pancake theorem that says if you have two flat pancakes on a 2-D surface (like on your countertop), there's a single line (1-D) that can cut both pancakes exactly in half. That might be easier to think of.

Example of It in Use (4, Informative)

eldavojohn (898314) | more than 2 years ago | (#35312396)

The Fields Medal winner named in the article has a blog about using it to prove the Szemeredi-Trotter theorem [wordpress.com] and of course there's the wikipedia article [wikipedia.org] on the generalized form of it. Also, I screwed up the summary, the reward was offered in '46 not '35.

Re:Example of It in Use (2)

gstoddart (321705) | more than 2 years ago | (#35312480)

The Fields Medal winner named in the article has a blog about using it to prove the Szemeredi-Trotter theorem and of course there's the wikipedia article on the generalized form of it.

You know, when I googled for "Ham Sandwich Theorem", wiki didn't even show up in the first page, so I assumed there wasn't one.

Oddly enough, the first paragraph nicely summarized what it boils down to:

In measure theory, a branch of mathematics, the ham sandwich theorem, also called the Stone-Tukey theorem after Arthur H. Stone and John Tukey, states that given n measurable "objects" in n-dimensional space, it is possible to divide all of them in half (according to volume) with a single (n - 1)-dimensional hyperplane. Here the "objects" should be sets of finite measure (or, in fact, just of finite outer measure) for the notion of "dividing the volume in half" to make sense.

So, cutting a sandwich in half, but expanded to a higher number of dimensions. Specifically, where the number of objects corresponds to the number of dimensions -- so, by crude extension, add lettuce, tomato and cheese to your sandwich and do it in six dimensions (yes, I know, that is a horrible over-simplification and I can't think of a car analogy).

Re:Example of It in Use (2)

WhirlwindMonk (1975382) | more than 2 years ago | (#35312560)

Specifically, where the number of objects corresponds to the number of dimensions -- so, by crude extension, add lettuce, tomato and cheese to your sandwich and do it in six dimensions (yes, I know, that is a horrible over-simplification and I can't think of a car analogy).

When expanding beyond three dimensions, you have to prefix the word "hyper" onto all objects. So you would add "hyper-lettuce," "hyper-tomato," and "hyper-cheese." Or if you really want to be exact, "six-dimensional hyper-lettuce," etc.

Re:Example of It in Use (1)

gstoddart (321705) | more than 2 years ago | (#35312610)

When expanding beyond three dimensions, you have to prefix the word "hyper" onto all objects.So you would add "hyper-lettuce," "hyper-tomato," and "hyper-cheese." Or if you really want to be exact, "six-dimensional hyper-lettuce," etc.

Six-dimensional hyper-ham ... I know people who would weep tears of joy at those words.

Re:Example of It in Use (1)

CraftyJack (1031736) | more than 2 years ago | (#35313248)

I think we all know where this is heading, so I'm just going to say it: Seven-dimensional hyper-bacon.
Dare to dream.

Re:Example of It in Use (0)

Anonymous Coward | more than 2 years ago | (#35313068)

Its call the Ham Sandwich theorem because it is easier to visualize slicing a ham sandwich than it is to slice a Turkey and a Stone...

?What?

Erdos Prizes (2)

SoVeryTired (967875) | more than 2 years ago | (#35312930)

Erdos offered many prizes for the solution of problems that he thought were difficult or out of reach of the mathematics of his time. These prizes were sometimes huge, worth tens or even hundreds of thousands of US dollars in today's money.

Erdos used to joke that he would get in trouble for violating minimum wage laws.

Since I live in Abstract Hilbert Space (1)

PolygamousRanchKid (1290638) | more than 2 years ago | (#35312512)

I have no idea how to cut the sandwich . . . I can't even manage to find the bugger: http://en.wikipedia.org/wiki/Hilbert_space [wikipedia.org]

Ham Sandwich theorem says that if you have n objects in n dimensional space, you can cut them all in half with a cut using an n-1 dimensional surface.

It's called Ham Sandwich because the analogy says if you have a chunk of ham, a chunk of cheese, and a chunk of bread (n = 3) in 3-D space, you can make a single "cut" to cut them all in exactly half. This single cut is achieved by finding the plane (3-1 = 2 dimensions) that goes through all of them.

Alternately, there's Pancake theorem that says if you have two flat pancakes on a 2-D surface (like on your countertop), there's a single line (1-D) that can cut both pancakes exactly in half. That might be easier to think of.

Does the pancake come with bacon?

Contingent on my alcohol intake, my counter-top can have 3-D, 4-D and 5-D dimensions. And scary green monsters on top. I guess that they like ham sandwiches . . . and pancakes,

Re:Since I live in Abstract Hilbert Space (1)

gstoddart (321705) | more than 2 years ago | (#35312838)

Contingent on my alcohol intake, my counter-top can have 3-D, 4-D and 5-D dimensions. And scary green monsters on top.

That's not alcohol ... that's something out of a Hunter S. Thompson novel. :-P

Re:Ham sandwich??? (1)

drooling-dog (189103) | more than 2 years ago | (#35312868)

Assuming that "cutting in half" means cutting through the center of mass, doesn't that boil down to saying that two points define a line (1D) in 2-space, three points define a plane (2D) in 3-space, etc? Or is there a subtlety I'm missing here?

Re:Ham sandwich??? (0)

Anonymous Coward | more than 2 years ago | (#35313206)

Why assume such an obviously wrong thing? Cutting in half means splitting in two parts of equal volume.

Re:Ham sandwich??? (1)

_0xd0ad (1974778) | more than 2 years ago | (#35313314)

Cutting in half means splitting in two parts of equal volume.

So the "top half" of Mt. Everest is obviously of equal volume to the "bottom half"?

Re:Ham sandwich??? (1)

khallow (566160) | more than 2 years ago | (#35313584)

Once you've defined what Mt. Everest is as an object with a fixed, finite volume, then yes, you can split it in that way.

Re:Ham sandwich??? (1)

_0xd0ad (1974778) | more than 2 years ago | (#35313878)

Of course you can bisect anything by volume. But is it obvious that you ought to? Most people, I suspect, would logically bisect Mt. Everest into "top" and "bottom" halves by altitude, not by volume. I was countering Anonymous Coward's claim that the "obvious" way to bisect something is by volume.

If we approximated Mt. Everest as a perfect sphere of constant density, it wouldn't matter how you bisected it, because no matter which method you selected (height, cross-sectional area, volume, or mass) they would all give exactly identical results. But real-world objects usually aren't perfect spheres, and often don't have a reasonably-constant density.

Re:Ham sandwich??? (0)

Anonymous Coward | more than 2 years ago | (#35313558)

"Cutting in half" means cutting something into two pieces with the same volume.

The trick is that the ham and bread don't need to be lined up in a nice sandwich shape. If you take *any* three (measurable, three-dimensional) objects in (three-dimensional) space, located *anywhere*, you can find a single plane which simultaneously cuts all three in half. (And if you replace all those threes with some other number, you can do the same thing.)

Of course, this paper uses the "polynomial ham sandwich theorem," in which you add more objects than dimensions and make up the difference by using a general algebraic surface instead of a plane. Using polynomials allows the slice to curve around, giving more freedom.

Re:Ham sandwich??? (1)

slimjim8094 (941042) | more than 2 years ago | (#35312352)

You know, I was considering posting a snarky comment to that effect when it occurred to me that they probably couldn't. I barely appreciate the subtleties of the problem (that is, why it's hard).

This is the kind of proof I could maybe understand in my Algorithms class, given a week and a very good explanation. But I'm not exactly a 'layman' in that context...

Though I will agree - the polynomial ham sandwich theorem sounds badass.

Re:Ham sandwich??? (2)

werepants (1912634) | more than 2 years ago | (#35312428)

As a really (really) rough idea: For any 3d objects of finite size, there exists a plane which could bisect all three of them.

Disclaimer:
IANAMBITCO (I am not a mathemetician, but I took calculus once)

Re:Ham sandwich??? (0)

Anonymous Coward | more than 2 years ago | (#35312446)

The general version states that for n objects in n-dimensional space, there is an (n-1)-dimensional hyperplane that can partition each object into two pieces of equal measure. Note: The measure can be thought as volume (hypervolume?), but measure theory allows for many other choices. Also, it should be surprising that a hyperplane ( a copy of R^(n-1) living in R^n given by fixing one coordinate) is enough freedom to make the cut, and you don't need anything more complicated.

In the case for 3D, we have three objects (slice of ham and two pieces of bread) and we have a 2D plane (knife) that, in one slice, can cut each in half, no matter their orientation or shape.

Now, if they used the Hairy Ball Theorem...

Re:Ham sandwich??? (1)

GlobalEcho (26240) | more than 2 years ago | (#35312494)

You also encounter the ham sandwich in some logic / philosophy classes, as follows.

Proposition
A ham sandwich is better than eternal happiness

Proof
- A ham sandwich is better than nothing.
- Nothing is better than eternal happiness.
- Therefore, a ham sandwich is better than eternal happiness. QED.

Re:Ham sandwich??? (-1)

Anonymous Coward | more than 2 years ago | (#35312812)

Yeah, but there is a logical fallacy in step 2. The phrasing "Nothing is better than eternal happiness" is a backwards way of saying "Eternal happiness is better than anything else". The only way the proof would hold up is if the reader really believed that it would be better to have absolutely nothing than to be eternally happy.

BUSTED! IN YOUR FACE!

Re:Ham sandwich??? (1)

Jake Griffin (1153451) | more than 2 years ago | (#35313410)

Actually "Nothing is better than eternal happiness" is a way of saying "Eternal happiness is at least as good as anything else". It doesn't have to be better.

BUSTED! IN YOUR FACE!

Re:Ham sandwich??? (1)

_0xd0ad (1974778) | more than 2 years ago | (#35313050)

If the subjective states of "better" and "worse" are defined in such a way that "nothing" is, in fact, preferred over "eternal happiness", then yes, a ham sandwich is "better" than eternal happiness.

For instance, if the problem is referring to someone you hate, you'd prefer them to have a ham sandwich instead. Especially if they can't eat pork.

Re:Ham sandwich??? (1)

neep (160155) | more than 2 years ago | (#35312714)

The Polynomial Ham Sandwich Theorem!
The ham sandwich theorem, states that given n measurable "objects" in n-dimensional space, it is possible to divide all of them in half (according to volume) with a single (n - 1)-dimensional hyperplane.

The ham sandwich theorem takes its name from the case when n = 3 and the three objects of any shape are a chunk of ham, a hunk of cheese, and a piece of bread -- notionally, a sandwich -- which can then each be bisected with a single cut (i.e., a plane). The theorem then states that it is possible to slice the sandwich in half such that each half contains the same amount of bread, cheese, and ham.
              -- paraphrased from Wikipedia
-----

Basically, given a bunch of objects (N) in an N-dimensional space, you can divide it into two halves both containing the same amount of stuff in both halves using a single cut (an N-1object).

Definitely beyond my mathematics skills nowadays to use it, but I hope the explanation helps.

Re:Ham sandwich??? (1)

sgunhouse (1050564) | more than 2 years ago | (#35313198)

The Sandwich Theorem in common terms:

If you have a function (the "ham") whose known values lie between two other functions (the "bread") and you are taking a limit at a point, then the limit of the "ham" is bounded by the limits of the "bread". They'll usually make some reference about the point you're taking the limit at as being where you're biting (or squeezing) the sandwich at.

Of course, it is nicest when the two limits for the bread are the same (hence the "squeezing"), but the bounds could still be useful even if they are not the same.

Mathematics (1)

Nerdfest (867930) | more than 2 years ago | (#35312208)

As someone not well versed in the field of mathematical proofs, all I can really add to this discussion is that "Nets Hawk Katz" is a really cool name.

Re:Mathematics (0)

Anonymous Coward | more than 2 years ago | (#35313452)

If they make a movie of this, the part of Nets Hawk Katz should be played by Lex Shrapnel.

Re:Mathematics (3, Interesting)

Webs 101 (798265) | more than 2 years ago | (#35313664)

I was friends with Nets when we were undergrads. He was just Nets Katz, then. Hawk is a translation of his Hebrew name "Nets".

Real-world applications? (2)

Jugalator (259273) | more than 2 years ago | (#35312216)

The problem involved determining the minimum number of distinct distances between any finite set of points in a plane

So will this assist me in traversing a crowded pub more effeciently to get me more quickly to a well-defined set of interesting girls, according to my parameters?

Re:Real-world applications? (2)

intellitech (1912116) | more than 2 years ago | (#35312304)

Yes, but you'll have to refer to Nash theory in order for everybody in your group to get one in the first place.

Re:Real-world applications? (1)

gstoddart (321705) | more than 2 years ago | (#35312394)

Yes, but you'll have to refer to Nash theory in order for everybody in your group to get one in the first place.

Ignore the hot blond, go for her plainer friends.

Words to live by.

Re:Real-world applications? (1)

StuartHankins (1020819) | more than 2 years ago | (#35312994)

+1 Insightful. They want attention too and are usually more willing to work for it.

Re:Real-world applications? (2)

gstoddart (321705) | more than 2 years ago | (#35313440)

+1 Insightful. They want attention too and are usually more willing to work for it.

And, if you all go for the hot blond, get shot down, and then go for her friends ... they'll all know they were second choices and be unhappy about it.

Pretty much what the poster meant when he said the Nash theorem.

Re:Real-world applications? (1)

pittaxx (2003818) | more than 2 years ago | (#35312376)

Most likely, however the process of entering all of those parameters into a computer might have an undesired side effect on the set of girls in question.

Re:Real-world applications? (1)

margeman2k3 (1933034) | more than 2 years ago | (#35312400)

When you define your set of interesting girls, you need to watch out for the Axiom of Choice. It's known to make things like this quite complicated.

Re:Real-world applications? (1)

Burdell (228580) | more than 2 years ago | (#35312486)

Yeah, but if you accept the Axiom of Choice, you can decompose the hot girl and recompose the non-discrete pieces into two hot girls, each equal to the original!

Nets Hawk Katz (0)

Anonymous Coward | more than 2 years ago | (#35312230)

The Professor's name, unfortunately, sounds like a sports headline. Should be "Katz Wins over Erdos in Second Half".

Next problem on his list (1)

paiute (550198) | more than 2 years ago | (#35312254)

He is working on Einstein's Tonsorial Problem:

http://www.math.indiana.edu/people/profile.phtml?id=nhkatz [indiana.edu]

Re:Next problem on his list (1)

Fnord666 (889225) | more than 2 years ago | (#35313598)

Next problem on his list :
He is working on Einstein's Tonsorial Problem

Really? There is a more generalized version of this problem that extends into higher dimensions. I figured he would have been working on extending the solution into dimensions >= 3. Maybe it's only tenured academics that milk such things for all they're worth.

Erdos' (0, Offtopic)

Anonymous Coward | more than 2 years ago | (#35312256)

Can we finally kill this awful grammar meme? Proper names that end in "s" still get the apostrophe-s treatment. You only drop the final "s" if the word is plural. You would go to Mr. Jones's used car lot, and you might mow the Joneses' lawn. It's gotten ridiculous.

Re:Erdos' (1)

jdpars (1480913) | more than 2 years ago | (#35312608)

Mod parent up. It's not a commonly known grammar fact, but it is an important one. Of course, I may be biased with a last name that ends in "s."

Re:Erdos' (1)

gstoddart (321705) | more than 2 years ago | (#35312780)

It's not a commonly known grammar fact, but it is an important one.

Sadly, some of us know this, but apparently even grammar experts seem to think it doesn't apply anymore. I actually disagreed out loud to my copy of Eats, Shoots, and Leaves [wikipedia.org] when she said to not do it that way.

Given how thoroughly drilled into my be rather stern old teachers, I still cringe when I see it used wrong.

Re:Erdos' (1)

fmobus (831767) | more than 2 years ago | (#35312642)

also, his name is not written like that. I would write the correct spelling, but this frakup called slashcode can't get utf-8 right in 2011.

Re:Erdos' (1)

Anonymous Coward | more than 2 years ago | (#35313424)

Yep. The first bloody paragraph of Strunk and bloody White. Learn it by heart, motherfuckers!

1. Form the possessive singular of nouns with 's.

Follow this rule whatever the final consonant. Thus write,

  • Charles's friend
  • Burns's poems
  • the witch's malice

This is the usage of the United States Government Printing Office and of the Oxford University Press.

Exceptions are the possessives of ancient proper names in -es and -is, the possessive Jesus', and such forms as for conscience' sake, for righteousness' sake. But such forms as Achilles' heel, Moses' laws, Isis' temple are commonly replaced by:

  • the heel of Achilles
  • the laws of Moses
  • the temple of Isis

The pronominal possessives hers, its, theirs, yours, and oneself have no apostrophe.

Subtraction (2)

bunratty (545641) | more than 2 years ago | (#35312272)

The reward was posted in 1935 but it's been solved after 65 years? Someone needs to brush up on their subtraction or current events -- the year is currently 2011. I don't think I would trust the person who made that mistake to accurately explain this advanced mathematical research.

Re:Subtraction (1)

Anonymous Coward | more than 2 years ago | (#35312318)

Summary is incorrect. TFA says 1946, which would be 65 years.

Re:Subtraction (4, Funny)

bunratty (545641) | more than 2 years ago | (#35312380)

Ah, eldavojohn, posting math research stories but unable to do subtraction.

Thanks for the Reminder (2)

eldavojohn (898314) | more than 2 years ago | (#35313368)

Ah, eldavojohn, posting math research stories but unable to do subtraction.

Don't worry, I only posted it here because I was unable to post it to reddit due to heavy usage. You won't have to put up with me or my apologies [slashdot.org] anymore.

Times...? (0)

Anonymous Coward | more than 2 years ago | (#35312288)

So he offered up a reward 11 years before he created the problem?

Nets Hawk Katz? (0)

Anonymous Coward | more than 2 years ago | (#35312324)

Isn't he one of the Harlem Globetrotters from Futurama?

Mildly Ambiguous (3, Insightful)

mathcam (937122) | more than 2 years ago | (#35312368)

Saying "Paul Erdos' combinatorial problem" is like saying "Michael Jordan's dunk he made that one time."

Re:Mildly Ambiguous (1)

zaxus (105404) | more than 2 years ago | (#35312508)

I'm sorry, I'm a geek; I don't understand sports metaphors. :-)

Re:Mildly Ambiguous (2, Funny)

Anonymous Coward | more than 2 years ago | (#35312572)

Saying "Michael Jordan's dunk he made that one time." is a little bit like saying "Paul Erdos' combinatorial problem".

Re:Mildly Ambiguous (1)

_0xd0ad (1974778) | more than 2 years ago | (#35313950)

And... for those of us who are neither scientists nor athletes (which should be pretty much all of us)... it's a bit like saying "Ford's truck model they built that one year".

He should make sure to patent it. (-1)

Anonymous Coward | more than 2 years ago | (#35312372)

He should make sure to patent it.

Guth (0)

Anonymous Coward | more than 2 years ago | (#35312464)

The summary here doesn't mention the other author Larry Guth, who pioneered the use of the polynomial ham sandwich theorem in this context.

Can they still cash that in? (1)

atari2600a (1892574) | more than 2 years ago | (#35312502)

$500 in 1935 would be roughly $8K today...

Re:Can they still cash that in? (0)

Anonymous Coward | more than 2 years ago | (#35313928)

I was thinking that too. What does "posted" mean. Does it mean that $500 was pledged? In that case the guy might be dead, and his estate disolved. Forget about it. OTOH, if "posted" means "deposited in an interest bearing account with legal instructions to only release the money under given circumstances" then it could be a nice sum. Interest rates are terrible now, but for much of the period in question they were 5%. Over the course of a few decades, compounding does some nice things.

Actual authors (2)

domulys (1431537) | more than 2 years ago | (#35312538)

After 65 years, Paul Erdos' combinatorial problem has been solved by Indiana University professor Nets Hawk Katz.

It was actually solved by Larry Guth and Nets Hawk Katz. Not sure how it is that authors magically disappear from press releases, especially principal authors...

Re:Actual authors (1)

Infiniti2000 (1720222) | more than 2 years ago | (#35312844)

It was actually solved by Larry Guth and Nets Hawk Katz. Not sure how it is that authors magically disappear from press releases, especially principal authors...

Larry Guth seems to be some sort of graduate student, though it's not clear that that's so. That would certainly explain it, however. Graduate students are scum compared to the professors. Didn't you know that?

Re:Actual authors (0)

Anonymous Coward | more than 2 years ago | (#35313796)

Guth got his Ph.D. in 2005; he's a member of the School of Mathematics at the Institute for Advanced Study, which doesn't have any students at all, graduate or undergrad. And in math there are no principal or secondary authors: you're either a coauthor or you're not, and all names appear in alphabetical order. It isn't some sort of lab science where the grad students spend 60+ hours a week doing their advisors' bitch work and getting little or no credit for it.

In any case, the article is a press release from Katz's home institution, which is why it credits him in the title. The main text repeatedly credits "Katz and Guth" for their joint work, though, so I don't see a problem here.

taking back our hearts, minds, ability to thrive (0)

Anonymous Coward | more than 2 years ago | (#35312580)

never a better time? see you there? check the #'s. it's 100% legit. probably can be marked by an outbreak of spontaneous care for one another/our young. you can feel it?

Ham Sandwich Theorem (2)

anwaya (574190) | more than 2 years ago | (#35312600)

The Stone–Tukey version of this theorem is a generalization of a simple case.

Consider a ham sandwich, with two slices of bread around a slice of ham. Each of these components has a center of gravity, and if you slice any one of these with a plane that passes through the center of gravity, then the two halves will be equal in mass.

Three points in 3-space define a plane, so the unique plane that passes through the three centers of gravity divides both slices of bread and the ham in half.

The general case states that you can divide n finitely measurable objects in n-space with an n-1 dimensional hyperplane.

Re:Ham Sandwich Theorem (0)

Anonymous Coward | more than 2 years ago | (#35312808)

Are planes allowed to curve or do they have to be "flat"? Because the only way a flat plane is going to perfectly bisect 2 pieces of bread and a piece of ham is if their centers of volume (or mass, gravity or however you're quantifying the bisection units) were all perfectly aligned in the first place, which makes (at least to me) the theorem self-evident.

Re:Ham Sandwich Theorem (0)

Anonymous Coward | more than 2 years ago | (#35313014)

Warning: I have no idea what I'm talking about.

I believe that's the nonintuitive part that makes it an interesting theorem: It's apparently true even when they're not aligned, using a single flat plane.
Consider the 2D/1D version - pancakes lying flat on a desk, and you get one straight line. Can you align the pancakes in a (non-overlapping, I believe) way such that it's not possible to split both in equal-weight halves with the line? (The answer is apparently "no".)

The "three 3D objects, one 2D plane"-version is the same thing, scaled up one dimension. Imagine three objects, and a triangle between their centers of mass - a plane with the same orientation as that triangle would obviously split them in two. The surprising thing is that it seems those halves would have the same mass.

Re:Ham Sandwich Theorem (1)

mapkinase (958129) | more than 2 years ago | (#35313158)

Seems like you know what you are doing. What the heck is "distinct distance"? Is it the number of distances larger than some characteristic distance of this set (average, diameter, etc.)?

Re:Ham Sandwich Theorem (0)

Anonymous Coward | more than 2 years ago | (#35313606)

You need to split stuff in two parts of equal volume. This doesn't necessarily involve cutting trough center of gravity of anything.

Re:Ham Sandwich Theorem (1)

_0xd0ad (1974778) | more than 2 years ago | (#35314078)

Why would you want to divide a sandwich by volume? To check you'd have to dunk it in water and then it'd be all soggy. Gross.

You divide it into halves by weight, and then you check it with a grocer's scale, dummy.

Re:Ham Sandwich Theorem (1)

anwaya (574190) | more than 2 years ago | (#35314092)

A volume of uniform (non-zero) density has a center of volume at the same place as the center of mass.

Don't Run! (0)

Anonymous Coward | more than 2 years ago | (#35312708)

It's only Ham!!!! hahahaha

whooshi (0)

Anonymous Coward | more than 2 years ago | (#35312724)

doesn't this touch the border of whats possible with a computer? isn't this somehow a generalization of dependency graph models? dealing with how to put points in a hierarchical tree, where there are many different ways to base the tree, a very amorphous situation in a phathomed incremental algorithm? it feels like a generalization of graph models to the plane, a generalization of the graph (points = nodes). or, more harsh, it feels like a modulo-type of equality of point sets. i don't know how to put it, but it deals with a fundamental aspect when thinking together with modern day computers, a useful framework on the purpose and the limits of orderings in program text / memory arrays.

Prank (0)

Anonymous Coward | more than 2 years ago | (#35312912)

This sounds like a prank. Graph theory 101 covers this: http://en.wikipedia.org/wiki/Handshaking_lemma

These names (1)

Even on Slashdot FOE (1870208) | more than 2 years ago | (#35312920)

What is it with scientists and mathematicians and their crazy names? Nets Hawk Catz? Ham Sandwich Theorem?

What's next, a Ninja Pirate Zombie Fractal theorem written by Buster Rabbits?

Re:These names (0)

Anonymous Coward | more than 2 years ago | (#35313570)

Nets in Hebrew translates to "Hawk". This is actually not an uncommon pattern with Hebrew. One of the most common example names is "Dov Ber", where Dov in Hebrew means "Bear" and Ber in Yiddish means, well, Bear.

Either way, I imagine that seeing the name Nets Hawk truly confuses basketball fans.

NB: I tried to write out the Hebrew, but slashcode seems to eat the characters.

Re:These names (0)

Anonymous Coward | more than 2 years ago | (#35314004)

LOLOLOL OMG ur so randome!!! Idiot.

Oblig. Homer Simpson (0)

Anonymous Coward | more than 2 years ago | (#35313040)

Mmmmm... ham sandwhich.... /slobbers

Show me the money! (2)

Xer0ss (1136189) | more than 2 years ago | (#35313272)

Well shit. If I had known there was 500 bucks on the line I would have given it a shot!

Elegant Simplicity (1)

MacGyver2210 (1053110) | more than 2 years ago | (#35313306)

For being such a complex problem, the solution seems rather simple.

Guess it's one of those "Right in front of us the whole time" answers.

Graphics? (1)

DissociativeBehavior (1397503) | more than 2 years ago | (#35313538)

It's supposed to be a 2D problem yet there is not a single graph in the proof. I don't think they found the theorem using mathemical formulas alone. I wish they were more graphics to show the origin of the problem and its connection to the real world.
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...