✦ LIBER ✦

A continuous analogue of Sperner's theorem

✍ Scribed by Daniel A. Klain; Gian-Carlo Rota

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 149 KB
Volume: 50
Category: Article
ISSN: 0010-3640
DOI: 10.1002/(sici)1097-0312(199703)50:3<205::aid-cpa1>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

One of the best-known results of extremal combinatorics is Sperner's theorem, which asserts that the maximum size of an antichain of subsets of an n-element set equals the binomial coefficient n n/2 , that is, the maximum of the binomial coefficients. In the last twenty years, Sperner's theorem has been generalized to wide classes of partially ordered sets.

It is the purpose of the present paper to propose yet another generalization that strikes in a different direction. We consider the lattice Mod(n) of linear subspaces (through the origin) of the vector space R n . Because this lattice is infinite, the usual methods of extremal set theory do not apply to it. It turns out, however, that the set of elements of rank k of the lattice Mod(n), that is, the set of all subspaces of dimension k of R n , or Grassmannian, possesses an invariant measure that is unique up to a multiplicative constant. Can this multiplicative constant be chosen in such a way that an analogue of Sperner's theorem holds for Mod(n), with measures on Grassmannians replacing binomial coefficients? We show that there is a way of choosing such constants for each level of the lattice Mod(n) that is natural and unique in the sense defined below and for which an analogue of Sperner's theorem can be proven.

The methods of the present note indicate that other results of extremal set theory may be generalized to the lattice Mod(n) by similar reasoning.

📜 SIMILAR VOLUMES

Looking for an Analogue of Rice's Theore

Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory

✍ Bernd Borchert; Frank Stephan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB

Rice's Theorem says that every nontrivial semantic property of programs is undecidable. In this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. For generators [31] we show a perfect a

A simple proof of Moser's theorem

✍ Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

This article gives a simple proof of a result of Moser, which says that, for any rational number r between 2 and 3, there exists a planar graph G whose circular chromatic number is equal to r.

A weighted generalization of Tur�n's the

A weighted generalization of Tur�n's theorem

✍ Bondy, J. A.; Tuza, Zs. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

We obtain a generalization of Turán's theorem for graphs whose edges are assigned integer weights. We also characterize the extremal graphs in certain cases.

A quick proof of Riemann's mapping theor

A quick proof of Riemann's mapping theorem

✍ H. P. McKean 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 278 KB 👁 2 views

A short proof of K�nig's matching theore

A short proof of K�nig's matching theorem

✍ Rizzi, Romeo 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 43 KB 👁 2 views

We give a short proof of the following basic fact in matching theory: in a bipartite graph the maximum size of a matching equals the minimum size of a node cover.

Stepwise Replication of a Tröger's Base

Stepwise Replication of a Tröger's Base Analogue

✍ Braja G. Bag; Günter von Kiedrowski 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB