✦ LIBER ✦

An identity in combinatorial extremal theory

✍ Scribed by R Ahlswede; Z Zhang

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 533 KB
Volume: 80
Category: Article
ISSN: 0001-8708
DOI: 10.1016/0001-8708(90)90023-g

No coin nor oath required. For personal study only.

✦ Synopsis

Our main discovery is the following identity: non-empty subsets of D = [ I, 2. . 11) AHLSWEDE AND ZHANG THEOREM 1. For ever)! ,fbmil>~ .d qf' non-rrnpt?) suh.yet,s nf'Q = ( 1, 2, . . . . tl i i w+ ,=I i 0 i Proof: Note first that only the minimal elements in .d determine X,,, and therefore matter. We can assume therefore that .d is an antichain. Recall that in Lubell's proof of Sperner's Lemma all "saturated" chains which pass through members of .d, are counted: c IAl! (tz-(Al)!. .4 t .d No chain is counted twice, because .d is an antichain. Since there are n! saturated chains in total, clearly or c IA(! (tz-IAl)! <n! 4 E cd Our observation is that we can also count the saturated chains not passing

📜 SIMILAR VOLUMES

Extremal problems in graph theory

✍ Béla Bollobás 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract The aim of this note is to give an account of some recent results and state a number of conjectures concerning extremal properties of graphs.

Reciprocal extremal problems in function

Reciprocal extremal problems in function theory

✍ Peter D. Lax 📂 Article 📅 1955 🏛 John Wiley and Sons 🌐 English ⚖ 885 KB

An extremal problem in subconnectivity

✍ F. T. Boesch; J. A. M. McHugh 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB

Geometric Identities in Lattice Theory

✍ Matteo Mainetti; Catherine Huafei Yan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 385 KB

Some extremal results in cochromatic and

Some extremal results in cochromatic and dichromatic theory

✍ Paul Erdös; John Gimbel; Dieter Kratsch 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 289 KB

## Abstract For a graph __G__, the cochromatic number of __G__, denoted __z__(__G__), is the least __m__ for which there is a partition of the vertex set of __G__ having order __m__. where each part induces a complete or empty graph. We show that if {__G__~__n__~} is a family of graphs where __G__

Horn Sentences of Small Size in Identity

Horn Sentences of Small Size in Identity Theory

✍ G. Marongiu; S. Tulipani 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 322 KB