๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A lower bound on the size of a complex generated by an antichain

โœ Scribed by P. Frankl

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
427 KB
Volume
76
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A short proof of the following result of Kleitman is given: the total number of sets contained in some member of an antichain of size (i) over the n-set is at least (E) + l --+ (i) for 0 < k G in. An equally short proof of Harper's isoperimetric theorem is provided as well.

๐Ÿ“œ SIMILAR VOLUMES

An Exponential Lower Bound for the Size
An Exponential Lower Bound for the Size of Monotone Real Circuits
โœ Armin Haken; Stephen A. Cook ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 118 KB

We prove a lower bound, exponential in the eighth root of the input length, on the size of monotone arithmetic circuits that solve an NP problem related to clique detection. The result is more general than the famous lower bound of Razborov and Andreev, because the gates of the circuit are allowed t

On a Lower-Bound for the Absolute Value
On a Lower-Bound for the Absolute Value of a Polynomial of Several Complex Variables
โœ B. Paneah ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 268 KB

For an arbitrary polynomial \(P\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) in complex space \(\mathbb{C}^{n}\) we describe a set of nonnegative multi-indices \(\alpha=\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}\right)\) such that for any \(n\)-tuple \(\delta=\left(\delta_{1}, \delta_{2}, \ldots,