✦ LIBER ✦

A new short proof for the Kruskal-Katona theorem

✍ Scribed by P Frankl

Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 96 KB
Volume: 48
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(84)90193-6

No coin nor oath required. For personal study only.

✦ Synopsis

We give a very short proof for the Kruskal-Katona theorem and Lovhsz's version of it: given (~) k-element sets there are at least (k~_l) (k -1)-element sets which are contained in at least one of the k-sets.

📜 SIMILAR VOLUMES

A new proof of the colored Kruskal—Katon

A new proof of the colored Kruskal—Katona theorem

✍ Eran London 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 386 KB

An extension of the Kruskal-Katona theorem to colored hypergraphs was given by Frankl, Fiiredi and Kalai in [Shadows of colored complexes, Mathematics Scandinavica]. Here we give a new simple proof.

A simple proof of the Kruskal-Katona the

A simple proof of the Kruskal-Katona theorem

✍ D.E Daykin 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 91 KB

A generalization of the Kruskal-Katona t

A generalization of the Kruskal-Katona theorem

✍ G.F Clements 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 289 KB

A Kruskal–Katona Type Theorem for the Li

A Kruskal–Katona Type Theorem for the Linear Lattice

✍ S Bezrukov; A Blokhuis 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 154 KB

We present an analog of the well-known Kruskal-Katona theorem for the poset of subspaces of PG(n, 2) ordered by inclusion. For given k, (k < ) and m the problem is to find a family of size m in the set of -subspaces of PG(n, 2), containing the minimal number of k-subspaces. We introduce two lexicogr

A short proof for a generalization of Vi

A short proof for a generalization of Vizing's theorem

✍ Claude Berge; Jean Claude Fournier 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 1 views

## Abstract For a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these re

A short proof of the Chen-Manalastas the

A short proof of the Chen-Manalastas theorem

✍ J.A. Bondy 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 232 KB

Gallai and Milgram (1960) proved that a digraph with stability number ct is spanned by ct disjoint directed paths. Chen and Manalastas Jr (1983) proved that a strong digraph with stability number at most two is spanned by at most two consistent directed circuits. We slightly simplify the proof of