Talk:Kruskal–Katona theorem

Questions

Two things:

I believe the proper ordering to take is the colexicographical ordering.

Second, I don't understand the connection between the statement of the theorem, and the decomposition of $m$ and subsequently $|\partial (A)|$ into the sum of binomial coefficients. Could this be expanded on?

129.93.181.33 17:57, 13 June 2006 (UTC)Josh Brown Kramer

I think you're right about it needing to be colex, but I wasn't positive. And, IIRC, the reason we want to write it that way is because it lets us bound the size of $|\partial A|$. Don't quote me on it. I'm pretty sure there's a section on this in Brualdi's book on combinatorics, which I have, so I'll check it later and see if I can learn enough to modify the article to be clearer. Sopoforic 14:42, 16 June 2006 (UTC)

Why is the theorem stated in the context of hypergraphs? It's most famous today as a complete characterization of simplicial complex f-vectors, and it's actually easier to state it that way. —The preceding unsigned comment was added by D Haggerty (talk • contribs) 14:08, 19 May 2007 (UTC).

Possibly because it's stated that way in low-level combinatorics textbooks? My copy of Brualdi's Introductory Combinatorics states it this way, IIRC. It was taught that way in a course I took that used that text, anyway. I, for one, don't know what a 'simplical complex f-vector' is, so I can't do anything about it, unfortunately. If you can add this information to the article (with sources, of course), then you are most welcome to do so. Positively encouraged, even. --Sopoforic 14:35, 19 May 2007 (UTC)

I hope things are now clear. --Doronshaf May 2008 —Preceding comment was added at 20:42, 5 May 2008 (UTC)

I don't want to completely redo the page myself, but I can assure you that at least 95% of the references to this theorem concern the complete classification of simplicial complex f-vectors. (see Stanley's Combinatorics and Commutative Algebra, for example.) D haggerty (talk) 16:15, 15 October 2008 (UTC)

Also, I believe that there's a consensus to rename this theorem the "Kruskal-Katona-Schuzenberger Theorem," as the third author proved an equivalent theorem at roughly the same time. D haggerty (talk) 16:17, 15 October 2008 (UTC)

New version

I agree with the sentiments expressed above. I rewrote the article along the lines of Stanley's "Combinatorial commutative algebra" and integrated generalizations of the extremal graph theory statements from the old version. I don't have a definitive combinatorial reference close at hand, so the notation in that part may not be standard. Arcfrk (talk) 06:22, 30 March 2010 (UTC)

Thanks! D Haggerty (talk) 03:03, 26 October 2010 (UTC)