Polytopes determined by hypergraph classes
type: Item
instance of: scholarly article
title: Polytopes determined by hypergraph classes
zbMATH Open document ID: 0588.05031
DOI: 10.1016/S0195-6698(85)80033-0
author: Peter Frankl
author: Gyula O. H. Katona
published in: European Journal of Combinatorics
publication date: 1985-01-01T00:00:00Z
review text: This very outstanding paper studies a new direction of extremal hypergraph problems: the theory of convex hulls of hypergraph families. Most extremal hypergraph problems can be formulated in the following way. There is given a non-negative weight function depending on the cardinality of the subsets. What is the maximum of the sum of this weight function over the subsets of hypergraphs of given type. With the help of the basic theorem of convex sets these can be formulated like this in general: Let \({\mathcal F}\) be hypergraph, and p(\({\mathcal F})=(f_ 0,...,f_ n)\) be the profile of \({\mathcal F}\) (n is the cardinality of groundset, \(f_ k=\) the number of k-element set in \({\mathcal F})\). The profiles of hypergraphs of given type form an \(n+1\) dimensional point set. What is the maximum of the sum of the weight function over the extreme points of the set. This approach yields very general theorems. This method applies strong instruments originally, but the present authors applying some well-known theorems of extremal hypergraph theory give new short proofs for some older theorems.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 52Bxx
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3943854
zbMATH Keywords: Sperner property
zbMATH Keywords: Erdős-Ko-Rado theorem
zbMATH Keywords: Katona-Kruskal theorem
zbMATH Keywords: extremal hypergraph problems
zbMATH Keywords: convex hulls
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: A minimization problem concerning subsets of a finite set
cites work: Q3942966
cites work: Existence theorems for Sperner families
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Intersecting Sperner families and their convex hulls
cites work: Extremal hypergraph problems and convex hulls
cites work: On Sperner families satisfying an additional condition
cites work: On Sperner families in which no k sets have an empty intersection
cites work: Q3901519
cites work: Q4071752
cites work: Two applications (for search theory and truth functions) of Sperner type theorems
cites work: Q5726070
cites work: Q3880849
cites work: A new short proof for the Kruskal-Katona theorem
full work available at URL: s0195-6698(85)80033-0
OpenAlex ID: W2014496760
description: scientific article; zbMATH DE number 3943854