The Antichain King
Some readers should be familiar with the classic Kruskal-Katona Theorem. Well, legend came to life today... Gyula O. H. Katona (of the Renyi Institute in Hungary) just came to our department and gave a talk about his main area of expertise, extremal set theory.
Sperner's Theorem was the result that launched this now-sprawling field. It addresses the following question: How large a family of subsets {S_1, ... S_m} of {1, 2, ... n} can we find, such that no S_i contains another S_j? (Such a family is called an antichain in the lattice of subsets of {1, 2, ... n} partially ordered by set inclusion.)
Sperner states that the collection of all sets of size (floor-of-) n/2 gives the biggest such antichain you could hope for. It's clear that this set is a maximal antichain (can't be augmented); the claim is that it's also globally optimal.
Katona mentioned some nice applications of Sperner's Theorem. Here's a cute one: given a set of real numbers all greater than 1, use Sperner's Theorem to bound the number of subset sums taking on a value in any interval [x, x+1), x a positive real. This bounds the concentration of the random variable that outputs a randomly chosen subset-sum.
He mentioned many generalizations as well. Sperner's Theorem can be viewed as a statement about the number of sets necessary to guarantee an ordered pair, but we can ask about guaranteeing ordered triples, diamonds, or any poset P for that matter. He and colleagues have results of this form, and he conjectures that for any poset P, there exists a constant c depending only on P such that, for all n, there exists a maximum P-excluding family of subsets of {1, 2, ... n}, such that all sets in the family have size in the range (n/2 - c(P), n/2 + c(P)). So, the structure of optimality in Sperner's result could extend way further (Erdos proved a result of this type for all chains P).
Finally, Katona mentioned the 'group testing' problem that first drew him into this whole web of intrigue:
Given n, r, there are n boxes, r < n of which contain (say) radioactive material. We can in one step test any subset of the boxes for presence of radioactivity (but get no sense of how many radioactive boxes are in the group, just 'some' or 'none'). How many tests are necessary to determine the r hot boxes?
Sperner theory is relevant to the nonadaptive-query case.
Well? Can you see such an elegantly posed question and not try your hand at it? Thanks, Professor Katona!
Sperner's Theorem was the result that launched this now-sprawling field. It addresses the following question: How large a family of subsets {S_1, ... S_m} of {1, 2, ... n} can we find, such that no S_i contains another S_j? (Such a family is called an antichain in the lattice of subsets of {1, 2, ... n} partially ordered by set inclusion.)
Sperner states that the collection of all sets of size (floor-of-) n/2 gives the biggest such antichain you could hope for. It's clear that this set is a maximal antichain (can't be augmented); the claim is that it's also globally optimal.
Katona mentioned some nice applications of Sperner's Theorem. Here's a cute one: given a set of real numbers all greater than 1, use Sperner's Theorem to bound the number of subset sums taking on a value in any interval [x, x+1), x a positive real. This bounds the concentration of the random variable that outputs a randomly chosen subset-sum.
He mentioned many generalizations as well. Sperner's Theorem can be viewed as a statement about the number of sets necessary to guarantee an ordered pair, but we can ask about guaranteeing ordered triples, diamonds, or any poset P for that matter. He and colleagues have results of this form, and he conjectures that for any poset P, there exists a constant c depending only on P such that, for all n, there exists a maximum P-excluding family of subsets of {1, 2, ... n}, such that all sets in the family have size in the range (n/2 - c(P), n/2 + c(P)). So, the structure of optimality in Sperner's result could extend way further (Erdos proved a result of this type for all chains P).
Finally, Katona mentioned the 'group testing' problem that first drew him into this whole web of intrigue:
Given n, r, there are n boxes, r < n of which contain (say) radioactive material. We can in one step test any subset of the boxes for presence of radioactivity (but get no sense of how many radioactive boxes are in the group, just 'some' or 'none'). How many tests are necessary to determine the r hot boxes?
Sperner theory is relevant to the nonadaptive-query case.
Well? Can you see such an elegantly posed question and not try your hand at it? Thanks, Professor Katona!
Labels: general math
posted by Andy D at
9:57 PM
3 Comments:
I recently stumbled across your blog. It's brilliant and very informative. Well curiosity has nearly killed me. Can you tell me how to approach this brilliant problem i.e. radioactive box test(that is of course the idea of Sperner's theorem).
Just tell me the intution behind the approach or give me a hint.
By
Anonymous, at 11:12 AM
Thanks, anon--tell your friends!
I'm not sure what 'the' approach is here... and there are many proofs of Sperner's Thm; they're all clever and most tend to slip out of my head, so you really need to shop around for one that you really understand.
But as far as some positive approaches to the problem... let's take r = 1 for starters. n tests suffice; is that optimal, or can you do better? Note, the idea of binary search is adaptive, so doesn't quite directly apply here... or does it?
By
Andy D, at 5:09 PM
Or, for another approach, try choosing the test-subsets randomly... O(log n) tests suffice (at least for r = O(1)... I'd have to think about the other cases).
You wouldn't believe how often and how well this idea works in CS.
By
Andy D, at 5:17 PM
Post a Comment
<< Home