Definitions: Weak or Strong? January 29, 2009
Posted by David Speyer in Uncategorized.
trackback
I am currently writing a paper where I need to define an antimatroid, which is a combinatorial structure that can be axiomatized in several equivalent ways.
In the axiom system I am using, an antimatroid consists of a finite set 
and a collection 
of subsets of , obeying several conditions. One of these conditions is:
For any 
with 
and 
in , we can find a chain 
, such that all the 
lie in and 
is a singleton.
Of course, I could equivalently say
For any 
with 
and and in , we can find 
in such that 
.
For any 
with and in , we can find in such that 
and 
is a singleton.
Same as , with the roles of and switched.
My preference is for . What is yours? More generally, should definitions include the fewest conditions possible, so that the statement “
is a boojum” is easy to check, or the most, so that it is easy to apply?
Like this:
Be the first to like this post.
Leave a Reply
I’d say define with few conditions to make it easy to check. Then derive lots of properties to make it easy to apply.
I would assume that it would depend on how often you need to verify the antimatroid conditions in your paper, versus how often you need to use them. Also, once one decides on one form of the definition, one can put a short remark or lemma immediately after the definition to note the equivalence with the other form. “Remark. The following equivalent definition of an antimatroid is often more useful in applications: …”
A third, more “object-oriented” approach, is to put the commonly used routes into and out of a definition into a single lemma, with the actual technical details of the definition buried or encapsulated in the proof of the lemma itself. “Lemma: There exists a class of objects, which we will call antimatroids, with the following properties: (a) any object which obeys [easily verified condition] is an antimatroid. (b) any antimatroid obeys [useful properties]. (c) any [important operation] of an antimatroid yields another antimatroid. (d) …”. This approach is good for things like the tensor product construction, which is clean to use but somewhat ungainly to build by hand. The one catch with this approach is that if you ever need to use the definition in a new manner not covered by what is stated in the lemma, one may have to redo the lemma or repeat the technical constructions used in the proof of that lemma.
I’d say that the definition should go for whichever formulation that is easier to understand for your readers. In your particular example, the one that looks simpler in my mind is (1).
All the equivalent reformulations (easier to generalize, easier to apply, and so on) can go on a technical lemma, if a proof is required, or just on a remark if it isn’t.
Just my 2 cents.
Or, one could take the “Examples first!” approach: discuss a key example of an antimatroid at length (without calling it as such), observing both the easily verified properties and the useful properties, and noting that the latter can be deduced from the former. By that point, one can introduce the definition in either form (making the appropriate remarks towards the other form) and it should be clear to the reader what the definition is intended to capture, how it will be used, and how it will be verified.
A variation of what Terence said: Make a Definition-Proposition a la:
For a tuple X=(…) the following conditions are equivalent: … If X satisfies one (hence all) of the conditions we call X a Boojum.
I hope you’ll post to your blog (or otherwise let me know) when your paper is available — I’m always interested in learning about new applications of antimatroid theory.
I’ll let you know, but it may be a disappointment. From my perspective, I had a lemma I wanted to prove about Coxeter groups which involved proving lots of combinatorial properties of a collection
as above. After I had everything worked out, I suspected that I was rediscovering some standard combinatorial object, so I dug around and discovered that my hypotheses on 
stated that it was an anti-matroid. So, form my perspective, anti-matroids showed up as the appropriate language to describe various little combinatorial lemmas I was already proving.
By the way, I originally learned about anti-matroids from Drew Armstrong’s very nice paper The sorting order on a Coxeter group. If you are interested in new applications of anti-matroids, you might want to look at that.
Where I can learn about specific (“hands on”) examples of Coxeter groups? The finite ones are the Euclidean symmetry groups. Otherwise they seem to be examples of ordered, infinite, non-abelian groups. I didn’t think any ordered groups existed besides Z. My biggest anxiety is that an elderly lady will ask me for help with Coxeter groups and I will be at a loss for words “oh… uh… I… well…”
I should start by pointing out that, while there are several partial orders people consider on Coxeter groups, Coxeter groups are not ordered groups in the sense that
is an ordered group. (That is, it is not true that 
implies 
.)
As for examples of Coxeter groups, after you understand the finite ones, the next examples to think about are the affine groups. These are generated by reflections in periodic arrangements of hyperplanes in
. There are three 
examples, and John Stembridge has drawn nice pictures of all of them: A2-tilde, B2-tilde and G2-tilde.
After that, you should probably think about some higher affine examples, and some examples in the hyperbolic plane.
I’m not sure where to point you for a good guide to these examples, but I see that the founder of the Geometry Junkyard is reading our blog. Does he, or anyone else, have some good ideas?
Thanks, I’ll take a look at the Armstrong paper.
By the way, if you want a very weak definition of an antimatroid, here’s one (though I suspect it will be aesthetically displeasing due to its use of individual elements):
(1) If A is a nonzero set in the antimatroid, there is some x in A such that A \ {x} is in the antimatroid, and
(2) If A, A u {x}, and A u {y} are in the antimatroid, then so is A u {x,y}.
Any finite set system satisfying both is an antimatroid; (1) corresponds to the path axiom you’re looking for alternatives to.
Your “strong” path axiom can be rephrased as: there exists a path between any sets A and B with A subset B, such that each step on the path changes a single element and the length of the path is the size of the difference between A and B. But it would work as well to state that such paths exist only between the empty set and B (a weaker axiom) or between any two sets A and B without the subset assumption (a stronger axiom). I don’t have strong feelings about whether to define an antimatroid as using weak axioms and then prove a lemma that the strong axioms are still true, or whether to define an antimatroid as using strong axioms and then to prove a lemma that things satisfying the weak axioms are antimatroids; the length of the axiom system description and the number of lemmas you need seems to me about the same either way.
My favorite style is
1 Def (the shortest).
2 Lemma, or Remark: TFAE (full list).
3 Examples.
@Tao: I personally dislike the “Examples first!” approach; I find it very confusing and usually end up reading whatever-it-is backwards.
I guess this just shows that important topics should be written up repeatedly with different styles.
Some of the advice here (for example, Terry’s) seems to be much more appropriate for introducing a new object than one with enough of a history to have a thorough Wikipedia page. Give the definition(s) most convenient for you, give your best one paragraph explanation of why they’re interesting or why your reader should think about them, and then cite a good survey paper and the Wikipedia page.
One solution I like:
Theorem. Let L and E be blah blah blah.
The following are equivalent: 1), 2), 3).
Proof: Klar.
When these conditions hold we call L an _anti-matroid_.
Just to check in: Allen’s solution is generally my favorite as well. This particular example is kind of too small to be worth doing this for, but I meant this discussion to be more general than one example anyway.
So, David, how do weak order and bruhat order work on the permutation group, S_n ? As I understand, Coxeter groups are (finitely generated?) reflection groups and your description of a particular element depends on your choice of presentation. These two orders have to do with the length of the “reduced” word representing a particular element. I still don’t totally get how this works. Also, do they form a distributive lattice under these orders?
Also, the interpretation as reflection groups leads tautologically to a representation of the group.
In any case, I think (2) is a convoluted rephrasing of (3) with the added awkwardness of a cardinality. My favorite definition is (1) but you can easily construct the desired sequence of Z’s using (3). If you need multiple definitions of the same thing try to remind the reader of this fact often.
“This is a wolf. A wolf likes to wear sheep’s clothes and giraffe’s clothes”
[Later on]
“Look! it’s a giraffe… no it’s a wolf in giraffe clothing”
“Look! It’s a sheep… no it’s still a wolf in sheep’s clothing”
[...] Problem Set! January 30, 2009 Posted by davidspeyer in Uncategorized. trackback John Mangual asks: So, David, how do weak order and bruhat order work on the permutation group, S_n ? As I [...]
My reply to John’s question is here.
Antimatroids from sorting networks…
A conversation on the Secret Blogging seminar regarding axiomatizations for antimatroids led me to arXiv:0712.1047, an interesting paper on some connections between antimatroids and partial orders on the elements of Coxeter groups….
Most people gave strategies for avoiding this dilemma, which is reasonable. But sometimes you have to bless one or the other as the official definition, perhaps only because you’re worried that if you don’t, someone else will choose randomly. In that case, I second Javier: choose for understanding, not for weakness or strength.