Erdos' Combinatorial Geometry Problem Solved

Finally I can sleep! by adeft · 2011-02-25 03:13 · Score: 1

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

Re:Finally I can sleep! by fishexe · 2011-02-25 13:58 · Score: 1

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

--
"I don't care about the Constitution!" --Bill O'Reilly, November 17, 2009

Ham sandwich??? by gstoddart · 2011-02-25 03:17 · Score: 4, Funny

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!

--
Lost at C:>. Found at C.

Re:Ham sandwich??? by Anonymous Coward · 2011-02-25 03:26 · Score: 5, Informative

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.
Re:Ham sandwich??? by slimjim8094 · 2011-02-25 03:29 · Score: 1

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.

--
I have developed a truly marvelous proof of this comment, which this signature is too narrow to contain.
Re:Ham sandwich??? by werepants · 2011-02-25 03:36 · Score: 2

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??? by GlobalEcho · 2011-02-25 03:41 · Score: 1

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??? by neep · 2011-02-25 04:02 · Score: 1

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??? by drooling-dog · 2011-02-25 04:17 · Score: 1

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??? by CyberDragon777 · 2011-02-25 04:30 · Score: 2

Actually it's Erdo"s.
(Support Unicode already Slashdot!)
Erdo" is Forest in Hungarian, and Erdo"s would be "Foresty".
http://en.wikipedia.org/wiki/Paul_Erd%C5%91s

--
We both said a lot of things that you are going to regret.
Re:Ham sandwich??? by _0xd0ad · 2011-02-25 04:34 · Score: 1

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??? by sgunhouse · 2011-02-25 04:48 · Score: 1

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.
Re:Ham sandwich??? by _0xd0ad · 2011-02-25 05:02 · Score: 1

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??? by Jake+Griffin · 2011-02-25 05:09 · Score: 1

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!

--
SIG FAULT: Post index out of bounds.
Re:Ham sandwich??? by khallow · 2011-02-25 05:21 · Score: 1

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??? by _0xd0ad · 2011-02-25 05:39 · Score: 1

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??? by Kyont · 2011-02-25 06:16 · Score: 1

So the "top half" of Mt. Everest is obviously of equal volume to the "bottom half"?
Sure, if you make the cut in the right place!

--
You shall see a cow on the roof of a cotton house.
Re:Ham sandwich??? by ClickOnThis · 2011-02-25 06:17 · Score: 2

A mathematician is a machine that turns ham sandwiches into ... uh, never mind.

--
If it weren't for deadlines, nothing would be late.
Re:Ham sandwich??? by _0xd0ad · 2011-02-25 06:46 · Score: 1

There's no "right" or "wrong" place to cut it. There is only a "correct" place to cut it if you want to bisect it by volume, which most people don't want to do, and therefore it's quite wrong to do that in most situations.
There's a million different ways to cut it, and all of them are "right" answers to different questions. So what's the right question?
Suppose you're trying to divide an apple and an orange between two children, giving them equal portions. The boy says apples and oranges are both fruit, so it would be fair to give one of them the apple and the other the orange since they'll have equal amounts of fruit. The girl contradicts that and says that apples and oranges are not really the same and she likes both kinds, so in order to really be fair they should each get half an apple and half an orange. Then the boy retorts that he doesn't like oranges and she likes both kinds, and it wouldn't be fair for her to have two kinds of fruit that she likes while he only gets one kind that he likes and one that he doesn't... so to really be fair she should have to eat the orange and let him eat the apple. And then the girl suggests that to be fair they should be allowed to take turns on alternating days to decide how to divide their fruit!
Even in such a very simple situation there's more than one way that you could divide things to be "equal", and the only "obvious" answer is that there is no "obvious" answer. Also, I'd hate being a parent.
Re:Ham sandwich??? by khallow · 2011-02-25 06:57 · Score: 2

But is it obvious that you ought to?
Depends how you define "bisect". A usable definition gets you one or more "obvious optimizations" for free.

This is a subtle issue in mathematics. Vaguely defined operations on vague objects generally go nowhere. Concrete, well-defined stuff gives you both a working problem and insight in what are the real issues.

Nothing aside from your own diligence keeps you from making thousands or millions of rival mathematical definitions of objects and bisections. These are all valid and all just as "obvious".

The thing about bisections into equal volumes, is that it happens to be particularly parsimonious. That is, it requires very little information to define the concept and design an algorithm which yields the desired bisection. Further, it is stable, that is, you can tweak the definitions a little (there are concrete ways in which you can define that) and get bisections which are close (again defined in concrete ways) to the equal volume bisections.
Re:Ham sandwich??? by johanatan · 2011-02-25 07:26 · Score: 1

Center of mass *or* center of volume; but, yea, that's the way I am seeing it too.
Re:Ham sandwich??? by khallow · 2011-02-25 07:40 · Score: 1

What you're saying amounts to "but it's easier this way".
Yes, to such a degree that it is the difference between impossible and possible.

bisecting it into halves of equal volume would require, at the least, two pictures from different angles to give me a rough idea of its 3-dimensional shape.
You only know part of its shape. What is the shape of the part you can't see from the surface? does it get lopped off at the base, where the crust begins a few dozen km down, or is it a wedge straight to the core of the Earth?

Second, do you have a consist way to bisect this object? Or do you cut it differently each time you try?

It makes the most sense to take into consideration as many different properties as possible, because you can always just assign them constant values later and they'll fall out of the equation. If you define bisection in terms of bisecting something by mass, you can always simply assume that the density is near-uniform... lo and behold, now you're bisecting by volume.
And if you're bisecting by mood, you can just hang it up, until you get rid of that variable. You can always generalize an overly simple model and sure, you generally can simplify a complex model, but you can't always derive a complex model to simplify.
Re:Ham sandwich??? by khallow · 2011-02-25 08:27 · Score: 1

What you're saying amounts to "but it's too hard".
And what makes you think that's not a valid excuse? Too hard problems whip my ass all the time. I can beat my head on the immovable wall or I can try simplifications to see if I can get anywhere with that strategy.

Yes... because it's extremely hard to define a theoretical model to describe how you bisect something by mass. So hard, in fact, that scientists should just pretend mass doesn't exist and approximate everything as a uniform-density solid of a particular volume and shape.
Let's give a counterexample. We have three bounded measurable objects in three dimensional space which are not constant density. If they were, a plane could bisect them, splitting them into equal volume sets.

Now it turns out that I can use this result directly to prove the same for objects with variable density by adding a fourth dimension for density. The object becomes a 4-dimensional constant density object with the shadow onto 3 dimensions being the objects actual 3-D shape and the width of the object from the 3-D plane out being its density at that 3-D point. Think of the objects as buildings with the floor resting on the 3-D world and the height at a point on the floor of that building being the density of the solid at that point.

Now take a very small, very distant ball and move it around. By the Ham Sandwich theorem, there's always a 3-dimensional hyperplane which cuts through all four shapes, Because we can move it around, we eventually can orient the cutting plane so that it is parallel to the density axis. The projection of this hyperplane into 3-D space then is a plane that bisects my original three objects into equal mass pieces.

Alternately, we could modify the proof of the Ham Sandwich theorem so that the measure is not constant but is the density of the three objects when we're inside any of them and an arbitrary constant everywhere else. As the original proof, you get that there is a unique plane which bisects these shapes into equal "volume" pieces. But because our choice of metric turned out to be equal to the density of the objects while inside the objects, we then get that we've bisected each of our three objects into equal mass pieces.

So I've handwaved a couple of approaches. The first set up the original variable density problem in 3-D as a constant density problem in 4-D and found a 3-D hyperplane cut that projected down to the desired 2-D plane cut. Second attempt changed how I measured volume so that my new volume just so happened to agree with mass when I was inside the objects of variable mass.

That's two approaches for how you can extend the power of the original proof to more complex examples.

Sometimes it makes sense to come up with a very general version of the problem and then collapse it, but the strategy of developing simple examples and then extending those examples is usually a very effective strategy.
Re:Ham sandwich??? by _0xd0ad · 2011-02-25 09:19 · Score: 1

We've grown rather off-topic from the original point.
My original point was that "cutting through the center of mass" isn't any more "obviously wrong" than "splitting in two parts of equal volume" when you're trying to define the ambiguous phrase "cutting in half". Both of them are "obviously wrong" if you're talking about the most obvious way to split Mt. Everest into top and bottom halves.
Furthermore, there's absolutely no reason to define the problem as "divide x into two parts of equal volume" when you can just as easily define the problem as "divide x into two parts of equal mass", particularly since you can convert the latter into the former just by assuming constant density.
Re:Ham sandwich??? by bill_mcgonigle · 2011-02-25 09:32 · Score: 1

Can I sue a polynomial ham sandwich?
Really though, I was just posting to point out how many Maths geeks point to /. as AC. Interesting correlation.
Or maybe it's one Nash-type genius, I dunno.

--
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
Re:Ham sandwich??? by GlobalEcho · 2011-02-25 09:41 · Score: 1

While you are correct, the logic problem in the proof is not quite so recondite. Think set theory.
Re:Ham sandwich??? by _0xd0ad · 2011-02-25 09:44 · Score: 1

Yes, I'm well aware that the 2nd assertion doesn't grammatically mean what it's logically asserted to mean.
Re:Ham sandwich??? by khallow · 2011-02-25 09:52 · Score: 1

Ok, going way to the beginning, if you cut through the center of mass, you usually aren't cutting into two equal volumes or masses. I believe the original claim that the cut through the center of mass was "wrong" because it would not normally cut into equal volumes. That's all.

If the problem is to cut objects into equal volumes, then it doesn't make sense to define bisection in some way that is irrelevant to the problem.

Now maybe they were claiming that there was a "right way" to bisect (though that's not my impression), but I don't support that. I don't believe that there is any sense in which things are "right" or "wrong" mathematically, except for logical truth of statements.

As to splitting Mt. Everest, you have yet to tell me what it is. The part we see is only a partial surface of it. The hidden part can be relatively small or large depending on what you decide it is.

Finally, the equal volume bisection is interesting because it's something we might want to do on occasion and you can come up with significant theorems about equal volume bisection.
Re:Ham sandwich??? by _0xd0ad · 2011-02-25 14:49 · Score: 1

Ok, going way to the beginning, if you cut through the center of mass, you usually aren't cutting into two equal volumes or masses.
What? By definition if you cut through the center of mass you're cutting into two equal masses.

I don't believe that there is any sense in which things are "right" or "wrong" mathematically, except for logical truth of statements.
"There's no failure quite as dissatisfying as a complete and total solution to the wrong problem." - Slashdot footer quotation.
Re:Ham sandwich??? by _0xd0ad · 2011-02-25 14:59 · Score: 1

Crap. Never mind, you're right. Cutting through an object's center of mass doesn't necessarily result in two equal masses.
Re:Ham sandwich??? by Geminii · 2011-02-28 18:10 · Score: 1

Into coffee, thus reducing it to a previously solved joke.

Mathematics by Nerdfest · 2011-02-25 03:17 · Score: 1

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 by Webs+101 · 2011-02-25 05:26 · Score: 3, Interesting

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

--
"Even for Slashdot, that was a very obscure reference!" - Anonymous Coward
Re:Mathematics by SAU! · 2011-02-25 06:25 · Score: 1

Team Wiess!
Re:Mathematics by Webs+101 · 2011-02-25 07:00 · Score: 1

Lance?

--
"Even for Slashdot, that was a very obscure reference!" - Anonymous Coward
Re:Mathematics by Ginger+Unicorn · 2011-02-26 02:00 · Score: 1

Nets Hawk Katz looked to me like an anagram. But the only anagram I could find of this was Hawk Tank Zest.

--
(1.21 gigawatts) / (88 miles per hour) = 30 757 874 newtons
Re:Mathematics by SAU! · 2011-02-26 11:09 · Score: 1

Yes, it's me. I thought throwing that in there might shake a few people out of the hedges....

Real-world applications? by Jugalator · 2011-02-25 03:18 · Score: 2

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?

--
Beware: In C++, your friends can see your privates!

Re:Real-world applications? by intellitech · 2011-02-25 03:25 · Score: 2

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

--
vos nescitis quicquam, nec cogitatis quia expedit nobis ut unus moriatur homo pro populo et non tota gens pereat.
Re:Real-world applications? by pittaxx · 2011-02-25 03:31 · Score: 1

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? by gstoddart · 2011-02-25 03:32 · Score: 1

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.

--
Lost at C:>. Found at C.
Re:Real-world applications? by margeman2k3 · 2011-02-25 03:34 · Score: 1

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? by Burdell · 2011-02-25 03:41 · Score: 1

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!
Re:Real-world applications? by StuartHankins · 2011-02-25 04:29 · Score: 1

+1 Insightful. They want attention too and are usually more willing to work for it.
Re:Real-world applications? by gstoddart · 2011-02-25 05:11 · Score: 2

+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.

--
Lost at C:>. Found at C.
Re:Real-world applications? by aardwolf64 · 2011-02-25 08:37 · Score: 1

Yes yes, we all saw the movie too.
Re:Real-world applications? by lsatenstein · 2011-02-26 00:57 · Score: 1

I presume the solution method would allow optimizing the travelling salesman problem, or even in shipments of products from a sales organization to multiple clients in one truckload. Or do I not understand the practical solutions.

--
Leslie Satenstein Montreal Quebec Canada

Next problem on his list by paiute · 2011-02-25 03:20 · Score: 1

He is working on Einstein's Tonsorial Problem:

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

--
If Slashdot were chemistry it would look like this:Cadaverine

Re:Next problem on his list by Fnord666 · 2011-02-25 05:22 · Score: 1

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.

--
'The tyrant will always find pretext for his tyranny.' - Aesop's Fables

Subtraction by bunratty · 2011-02-25 03:22 · Score: 2

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.

--
What a fool believes, he sees, no wise man has the power to reason away.

Re:Subtraction by Anonymous Coward · 2011-02-25 03:27 · Score: 1

Summary is incorrect. TFA says 1946, which would be 65 years.
Re:Subtraction by olsmeister · 2011-02-25 03:28 · Score: 1

According to TFA, the problem was originally posed by Erdos in 1946.
Re:Subtraction by bunratty · 2011-02-25 03:31 · Score: 4, Funny

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

--
What a fool believes, he sees, no wise man has the power to reason away.

Mildly Ambiguous by mathcam · 2011-02-25 03:30 · Score: 3, Insightful

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

Re:Mildly Ambiguous by zaxus · 2011-02-25 03:43 · Score: 1

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

--
/. zen: Imagine a Beowulf cluster of Beowulf clusters...
Re:Mildly Ambiguous by Anonymous Coward · 2011-02-25 03:49 · Score: 2, Funny

Saying "Michael Jordan's dunk he made that one time." is a little bit like saying "Paul Erdos' combinatorial problem".
Re:Mildly Ambiguous by digitalsushi · 2011-02-25 05:23 · Score: 1

that's the funniest thing on here in 9 years.

--
slashdot: where everyone yells sarcastic metaphors to themselves to understand the issue
Re:Mildly Ambiguous by _0xd0ad · 2011-02-25 05:43 · Score: 1

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".
Re:Mildly Ambiguous by pjt33 · 2011-02-25 08:04 · Score: 1

Thank you. It's sad that I had to get 70% of the way through the comments before I found one which actually recognised this obvious fact.

Example of It in Use by eldavojohn · 2011-02-25 03:33 · Score: 4, Informative

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. Also, I screwed up the summary, the reward was offered in '46 not '35.

--
My work here is dung.

Re:Example of It in Use by gstoddart · 2011-02-25 03:41 · Score: 2

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).

--
Lost at C:>. Found at C.
Re:Example of It in Use by WhirlwindMonk · 2011-02-25 03:48 · Score: 2

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 by gstoddart · 2011-02-25 03:53 · Score: 1

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.

--
Lost at C:>. Found at C.
Re:Example of It in Use by swfranklin · 2011-02-25 04:13 · Score: 1

Six-dimensional hyper-ham
I don't think that's a kosher example...
Re:Example of It in Use by CraftyJack · 2011-02-25 04:54 · Score: 1

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 by gstoddart · 2011-02-25 06:15 · Score: 1

I think we all know where this is heading, so I'm just going to say it: Seven-dimensional hyper-bacon.
Dare to dream.
Sorry, but I think that might open up a rift in the pork-time continuum.

--
Lost at C:>. Found at C.
Re:Example of It in Use by davester666 · 2011-02-25 07:43 · Score: 2

to go along with the six degree's of bacon!

--
Sleep your way to a whiter smile...date a dentist!

Re:Polynomial ham sandwich theorem? by RevWaldo · 2011-02-25 03:38 · Score: 5, Funny

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

.

--
Prisencolinensinainciusol. Ol Rait!

Since I live in Abstract Hilbert Space by PolygamousRanchKid+ · 2011-02-25 03:43 · Score: 1

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

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,

--
Schroedinger's Brexit: The UK is both in and out of the EU at the same time!

Re:Since I live in Abstract Hilbert Space by gstoddart · 2011-02-25 04:14 · Score: 1

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

--
Lost at C:>. Found at C.
Re:Since I live in Abstract Hilbert Space by PolygamousRanchKid+ · 2011-02-25 21:51 · Score: 1

examples of Hilbert spaces include spaces of square-integrable functions, spaces of sequences, Sobolev spaces consisting of generalized functions, and Hardy spaces of holomorphic functions.
Well, that pretty much describes the closet where my girlfriend keeps her shoes. I call it Fibber McGee's closet, but she is German, and doesn't understand the joke: http://en.wikipedia.org/wiki/Fibber_McGee_and_Molly#The_Closet
It is a simple radio gag, but I still laugh my ass off whenever I hear it. "Oh, Molly, I'll get that, it must be here in my closet . . ."

--
Schroedinger's Brexit: The UK is both in and out of the EU at the same time!

Re:Polynomial ham sandwich theorem? by _0xd0ad · 2011-02-25 03:46 · Score: 1

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.

Actual authors by domulys · 2011-02-25 03:46 · Score: 2

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 by Infiniti2000 · 2011-02-25 04:15 · Score: 1

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 by swfranklin · 2011-02-25 04:34 · Score: 1

The article is about Katz, published by Indiana University.
Re:Actual authors by eulerizeit · 2011-02-25 05:09 · Score: 1

In mathematics they alphabetize authors so there is no assumption of primary, secondary, etc.

Re:Polynomial ham sandwich theorem? by gstoddart · 2011-02-25 03:47 · Score: 1

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.

--
Lost at C:>. Found at C.

Re:Polynomial ham sandwich theorem? by _0xd0ad · 2011-02-25 03:50 · Score: 2

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 Theorem by anwaya · 2011-02-25 03:52 · Score: 2

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 by CyberDragon777 · 2011-02-25 04:37 · Score: 1

A plane is a 2D surface, therefore it is flat.

--
We both said a lot of things that you are going to regret.
Re:Ham Sandwich Theorem by mapkinase · 2011-02-25 04:44 · Score: 1

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.)?

--
I do not believe in karma. "Funny"=-6. Do good and forbid evil. Yours, Oft-Offtopic Flamebaiting Troll.
Re:Ham Sandwich Theorem by _0xd0ad · 2011-02-25 05:50 · Score: 1

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 by anwaya · 2011-02-25 05:51 · Score: 1

A volume of uniform (non-zero) density has a center of volume at the same place as the center of mass.
Re:Ham Sandwich Theorem by anwaya · 2011-02-25 05:54 · Score: 1

The centers of mass do not have to be aligned, if by aligned you mean that they lie on a straight line. They just all have to lie on a plane, which is always true of any three points - unless they all lie on a straight line or coincide, and in either of these cases there is an infinite number of planes that bisect.
Re:Ham Sandwich Theorem by _0xd0ad · 2011-02-25 06:05 · Score: 2

center of gravity ... mass
I'm not sure which makes me want to slap you more... the fact that you needlessly restricted the attribute of matter to its "center of gravity" instead of its "center of mass", or the fact that you then relaxed back to the general word "mass" in referring to the property which you'd just indicated was specifically its gravitational mass.
/pedant
Re:Ham Sandwich Theorem by Noughmad · 2011-02-25 06:50 · Score: 1

Actually, the correct term in this case would be center of volume.

--
PlusFive Slashdot reader for Android. Can post comments.
Re:Ham Sandwich Theorem by _0xd0ad · 2011-02-25 06:59 · Score: 1

Actually, no it wouldn't be.
Re:Ham Sandwich Theorem by larsbars · 2011-02-25 07:03 · Score: 1

What you call the Ham Sandwich Theorem is true, trivial, and most definitely _not_ the Ham Sandwich Theorem. The theorem states that there is a plane that has equal portions of ham and of each slice of bread on either side. If you cut a body by a plane through its center of gravity you _do not_ necessarily have equal volumes on either side of the plane.
Re:Ham Sandwich Theorem by sxeraverx · 2011-02-25 07:42 · Score: 1

Excellent description, and it helped me understand it, but I have a minor correction.
The plane that cuts the three pieces (or the nth-dimension generalization that cuts n pieces) isn't necessarily unique, specifically in the case where the three points are colinear (or the nth-dimension generalization thereof).
Re:Ham Sandwich Theorem by SleazyRidr · 2011-02-25 09:16 · Score: 1

So... does that change the meaning of what he said? The centre of gravitational mass will be the same point as the centre of mass.
In reference to your reply to Noughmad, the ham sandwich theorem deals with volume rather than with mass, so referring to the centre of volume would be more directly attributable to the topic at hand.

--
Is 1563649 a prime number?
Re:Ham Sandwich Theorem by _0xd0ad · 2011-02-25 09:35 · Score: 1

What you call the Ham Sandwich Theorem is true, trivial, and most definitely _not_ the Ham Sandwich Theorem.
So? He added another dimension (density) and called it the ham sandwich theorem.

If you cut a body by a plane through its center of gravity you _do not_ necessarily have equal volumes on either side of the plane.
He didn't say you have equal volumes. He said you have equal masses.
Re:Ham Sandwich Theorem by _0xd0ad · 2011-02-25 09:41 · Score: 1

The centre of gravitational mass will be the same point as the centre of mass.
So? Just because they coincide doesn't make them the same concept. That's like calling the kilogram a unit of weight.

the ham sandwich theorem deals with volume rather than with mass
Why? That's dumb. I want to slap whoever decided that, too. If you want to approximate ham and bread as uniform-density solids, fine... I'd rather leave density in the equation. I damn well know that if the ham has a big chunk of fat on one side I still don't want one half of the sandwich being mostly fat.
Re:Ham Sandwich Theorem by larsbars · 2011-02-25 12:21 · Score: 1

If you cut a body by a plane through its center of gravity you _do not_ necessarily have equal volumes on either side of the plane.
He didn't say you have equal volumes. He said you have equal masses.
Cutting a body through it's center of mass doesn't still doesn't necessarily leave equal masses on either side of the (hyper-)plane. The center of mass lets you ignore the distribution of mass as a function of position (density) for certain types of problems. This is not one of them. What you are saying is still trivial, still wrong, and still not the ham sandwich theorem.
Re:Ham Sandwich Theorem by _0xd0ad · 2011-02-25 15:01 · Score: 1

Cutting a body through it's center of mass doesn't still doesn't necessarily leave equal masses on either side of the (hyper-)plane.
You're right. I don't know why I had that stuck in my head.

Re:Erdos' by jdpars · 2011-02-25 03:53 · Score: 1

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' by fmobus · 2011-02-25 03:56 · Score: 1

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' by gstoddart · 2011-02-25 04:09 · Score: 1

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 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.

--
Lost at C:>. Found at C.

These names by Even+on+Slashdot+FOE · 2011-02-25 04:22 · Score: 1

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 by Geminii · 2011-02-28 18:15 · Score: 1

Oh, you've read the synopsis? :)

Erdos Prizes by SoVeryTired · 2011-02-25 04:23 · Score: 2

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.

--
Slashdot: news for Apple. Stuff that Apple.

Re:Erdos Prizes by afabbro · 2011-02-25 08:46 · Score: 1

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.
Too bad he didn't put that $500 in some kind of long-term savings instrument. $500 in 1935 at 5% compounded annually = $20,387.16 in 2011.
If you believe the stock market truly compounds at 10.5% annually over the long haul, then $500 in 1936 at 10.5% compounded annually = $987,422.76 in 2011.
Of course, he could have just waited a few years and bought 5,000 copies of Superman's first appearance in Action #1 and encased them in argon.

--
Advice: on VPS providers

Re:Polynomial ham sandwich theorem? by Dog-Cow · 2011-02-25 04:35 · Score: 1

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

Bonus! by WDancer · 2011-02-25 04:43 · Score: 1

He should get bonus points for style with the name "Nets Hawk Katz"

Re:Polynomial ham sandwich theorem? by _0xd0ad · 2011-02-25 04:45 · Score: 1

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. :/

Show me the money! by Xer0ss · 2011-02-25 04:57 · Score: 2

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

Elegant Simplicity by MacGyver2210 · 2011-02-25 05:02 · Score: 1

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.

--
If the only way you can accept an assertion is by faith, then you are conceding that it can't be taken on its own merits

Thanks for the Reminder by eldavojohn · 2011-02-25 05:06 · Score: 2

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 anymore.

--
My work here is dung.

Re:Thanks for the Reminder by EMeta · 2011-03-01 06:00 · Score: 1

I hope you're joking. You provide a sizable fraction of the interesting stories here.

Re:Erdos' by Anonymous Coward · 2011-02-25 05:09 · Score: 1

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.

Graphics? by DissociativeBehavior · 2011-02-25 05:17 · Score: 1

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.

Re:Graphics? by St.Creed · 2011-02-25 13:29 · Score: 1

A lot of computer graphics, especially the field of Computational Geometry, deals with sorting points and lines, finding the closest convex shape around a set of points and stuff like that. All these things are used in algorithms to draw 3D-objects faster, or detect collisions between objects, etc.
You'd need a specialist to answer the question as to what actual use this will be put - but theorems like this form the underpinnings of all computer graphics beyond just putting a few pixels on a 2D-plane.

--
Therefore, by the (faulty) logic you're using, you're just a cow with a keyboard - osu-neko (2604)
Re:Graphics? by Prune · 2011-02-25 19:44 · Score: 1

I have an MSc in CS specializing in computer graphics, but my specific area is in rendering, not computational geometry. My real question is then, is this useful for rendering specifically?

--
"Politicians and diapers must be changed often, and for the same reason."

Re:Polynomial ham sandwich theorem? by _0xd0ad · 2011-02-25 06:20 · Score: 1

What's more, they've applied the known fact that any 3 points define a plane in 3-space and if you could "cut" a point in half with a plane, obviously its two halves on the two sides of the plane would have equal masses, so it's quite bleedingly obvious that any plane that cuts all 3 points also bisects the 3 objects they represent.

Like by davemurphy · 2011-02-25 07:50 · Score: 1

I like

Re:Erdos' by pjt33 · 2011-02-25 08:02 · Score: 1

Can we finally kill the idea that orthography is part of grammar?

Re:Polynomial ham sandwich theorem? by billstewart · 2011-02-25 08:53 · Score: 1

Isn't brisket topologically congruent to ham? Reubens, yeah, they're more complex, especially with the potential for knots in the sauerkraut, but ham and brisket are usually just slices....

--

Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks

Re:Erdos' by Xtifr · 2011-02-25 09:07 · Score: 1

The first bloody paragraph of Strunk and bloody White.

Yes, and that's only one of the many many things that misguided and horribly out-of-date book is wrong about.

This post by Prof. Arnold Zwicky (Linguistics, Stanford) only gives a hint of how much that little book is loathed by people who actually know something about language and style. Especially on the other side of the pond where many of its "rules" were never ever considered correct.

Strunk & White is to language as BASIC is to programming--you can learn something from it, but it's likely to cause damage that will take years to repair.

Re:Erdos' by Xtifr · 2011-02-25 09:18 · Score: 1

According to whom? From the Chicago Manual of Style FAQ:

Q. Which is the correct singular possessive form? “Professor Davis’ class” or “Professor Davis’s class”? [...]
A. In its 15th edition, CMOS allowed the style shown in your first example, but the new 16th edition (7.21) no longer recommends it, although it is not incorrect...

Graphics? by Prune · 2011-02-25 10:25 · Score: 1

The summary mentions that this is useful for computer graphics. Can someone elaborate?

--
"Politicians and diapers must be changed often, and for the same reason."

questions, queries, posers by eyenot · 2011-02-25 10:41 · Score: 1

"The new proof used a geometric reformulation of the original problem that was devised by Gyorgy Elekes (Eotvos University, Hungary) and Micha Sharir (Tel Aviv University). Using that framework, Katz and Guth then implemented the polynomial ham sandwich theorem to create the new kind of cell decomposition that left points in the plane either in the interior of cells or on the walls of the cells. "

The way this reads for me is that anybody can fly into the room where some people have been sitting for decades, brows in their heads, trying hard to solve some math problem but only successfully attracting cobwebs, and just plough through it with the pOlyNoMIal hAm SaNdwIch method.

It seems like all the time in the news there is some huge problem with some totally, barf-ass, simplistic way of solving it that makes you slap the hell out of your forehead and scream "any first year student could have solved that if they were actually interested in the problem in the first place!"

Q: How many distinct math/chemistry/physics/logic problems are out there, waiting for somebody to say "just dangle a string in it dummy" or "hey you could've just evaporated it across the surface of grape juice" or whatever? Given progress of science "n" can we predict how many loose-ends there are waiting around for somebody to show half an interest in and solve immediately?

--
"Stratigraphically the origin of agriculture and thermonuclear destruction will appear essentially simultaneous" -- Lee

Aphorism Update by hutsell · 2011-02-26 05:48 · Score: 1

"My brain is open." -- Paul Erdos.
"My stomach is empty." -- Nets Hawk Katz.

--
Yesterday's Weirdness is Tomorrow's Reason Why

Re:Erdos' by Xtifr · 2011-02-26 09:49 · Score: 1

There are so many bad/clueless style guides out there that sheer quantity doesn't really say much. The Chicago Manual of Style—one of the few really widely-respected guides to American English style and usage—recommends using the apostrophe with 's', but explicitly says that just the apostrophe is not incorrect. (This is a change from the previous edition where they didn't even state a preference.)

Slashdot Mirror

Erdos' Combinatorial Geometry Problem Solved

122 of 170 comments (clear)