×

Extremal problems for finite sets and convex hulls—a survey. (English) Zbl 0878.05079

Author’s abstract: Let \(\mathcal F\) be a family of distinct subsets of an \(n\)-element set. Define \(p_i({\mathcal F})\) \((0\leq i\leq n)\) as the number of \(i\)-element members of \(\mathcal F\). Consider the profile vectors \((p_0({\mathcal F}),\dots,p_n({\mathcal F}))\) for all families \(\mathcal F\) belonging to a certain class \(A\) (e.g. \(A\) can be the class of all families where any two members have a nonempty intersection). Let \(\varepsilon(A)\) denote the set of extreme points of the convex hull of the set of these profile vectors. Results determining \(\varepsilon(A)\) for some classes \(A\) are surveyed. Facets and edges of these convex hulls are also described for some \(A\). Connections to the classical extremal problems are shown.
Reviewer: K.Engel (Rostock)

MSC:

05D05 Extremal set theory
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B., On generalized graphs, Acta Math. Hungar., 16, 447-452 (1965) · Zbl 0138.19404
[2] Bollobás, B., Spemer systems consisting of pairs of complementary subsets, J. Combin. Theory Ser. B, 15, 363-366 (1973) · Zbl 0281.05001
[3] Clements, G. F., A minimization problem concerning subsets of a finite set, Discrete Math., 4, 123-128 (1973) · Zbl 0257.05003
[4] Daykin, D. E.; Frankl, P.; Greene, C.; Hilton, A. J.W., A generalization of Sperner’s theorem, J. Austral. Math. Soc. A, 31, 481-485 (1981) · Zbl 0484.05011
[5] Daykin, D. E.; Godfrey, J.; Hilton, A. J.W., Existence theorems for Sperner families, J. Combin. Theory Ser. A, 17, 245-251 (1974) · Zbl 0287.05003
[6] Engel, K., Convex hulls for intersecting-or-noncointersecting families, Rostock Math. Kolloq., 46, 11-16 (1993) · Zbl 0785.05084
[7] K. Engel, personal communication.; K. Engel, personal communication.
[8] Engel, K.; Erdős, Péter L., Sperner families satisfying additional conditions and their convex hulls, Graphs Combin., 5, 47-56 (1989) · Zbl 0709.05038
[9] Engel, K.; Erdős, Péter L., Polytopes determined by complementfree Sperner families, Discrete Math., 81, 165-169 (1990) · Zbl 0733.05002
[10] K. Engel, G.O.H. Katona and G. Schild, paper in preparation.; K. Engel, G.O.H. Katona and G. Schild, paper in preparation.
[11] Erdős, P.; Ko, Chao; Rado, R., Intersection theorems for systems of finite sets, Q. J. Math. Oxf. II Ser., 12, 313-318 (1961)
[12] Erdős, Péter L.; Faigle, U.; Kern, W., On the average rank of LYM-sets, Discrete Math., 144, 11-22 (1995) · Zbl 0835.05083
[13] Erdős, Péter L.; Frankl, P.; Katona, G. O.H., Intersecting Sperner families and their convex hulls, Combinatorica, 4, 21-34 (1984) · Zbl 0544.05001
[14] Erdős, Péter L.; Frankl, P.; Katona, G. O.H., Extremal hypergraph problems and convex hulls, Combinatorica, 5, 11-26 (1985) · Zbl 0579.05033
[15] Erdős, Péter L.; Katona, G. O.H., Convex hulls of more-part Sperner families, Graphs Combin., 2, 123-134 (1986) · Zbl 0665.05002
[16] Erdős, Péter L.; Katona, G. O.H., All maximum 2-part Sperner families, J. Combin. Theory Ser. A, 43, 58-69 (1986) · Zbl 0613.05002
[17] Erdős, Péter L.; Katona, G. O.H., A 3-part Sperner theorem, Studia Sci. Math. Hungar., 22, 383-393 (1987) · Zbl 0712.05002
[18] Frankl, P., The Erdős-Ko-Rado theorem is true for \(n = ckt \), Coll. Math. Soc. Bolyai, 18, 365-375 (1978)
[19] Frankl, P., A new short proof of the Kruskal-Katona theorem, Discrete Math., 48, 327-329 (1984) · Zbl 0539.05006
[20] Frankl, P.; Katona, G. O.H., Polytopes determined by hypergraph classes, Europ. Combinat., 6, 233-243 (1985) · Zbl 0588.05031
[21] Frankl, P.; Matsumoto, M.; Ruzsa, I. Z.; Tokushige, N., Minimum shadows in uniform hypergraphs and a generalization of the Takagi function, J. Combin. Theory Ser. A, 69, 125-138 (1995) · Zbl 0820.05059
[22] Fulkerson, D. R., Blocking and anti-blocking pairs of polyhedra, Math. Program, 1, 168-194 (1971) · Zbl 0254.90054
[23] Fulkerson, D. R., Anti-blocking polyhedra, J. Combin. Theory Ser. B, 12, 50-71 (1972) · Zbl 0227.05015
[24] Greene, C.; Katona, G. O.H.; Kleitman, D. J., Extensions of the Erdős-Ko-Rado theorem, SIAM Stud. Appl. Math., 55, 1-8 (1976) · Zbl 0341.05004
[25] Katona, G., Intersection theorems for system of finite sets, Acta Math. Acad. Sci. Hungar., 15, 329-337 (1964) · Zbl 0134.25101
[26] Katona, G., A theorem of finite sets, (Theory of Graphs (1968), Akademiai Kiadó: Akademiai Kiadó Budapest) · Zbl 0313.05003
[27] Katona, G. O.H., A simple proof of Erdős-Ko-Rado theorem, J. Combin. Theory Ser. B, 13, 183-184 (1972) · Zbl 0262.05002
[28] Katona, G. O.H., Two applications of Sperner type theorems, Periodica. Math. Hungar., 3, 3, 19-26 (1973) · Zbl 0266.05001
[29] Katona, G. O.H., Shedding some light on shadows, (Alavi, Y.; Lick, D. R.; Liu, Jivqiang, Combinatorics, Graph Theory, Algorithms and Applications, Beijing (1994), World Scientific: World Scientific singapore), 99-109, 1993
[30] Katona, G. O.H.; Schild, G., Linear inequalities describing the class of intersecting Sperner families of subsets, 1, (Bodendiek, R.; Henn, R., Topics in Combinatorics and Graph Theory (1990), Physica-Verlag: Physica-Verlag Heidelberg), 413-420 · Zbl 0748.05005
[31] Katona, G. O.H.; Woyczynski, W., Optimization of the reliability polynomial in presence of mediocre elements, Networks, 23, 327-332 (1993) · Zbl 0774.90032
[32] Kleitman, D. J.; Milner, E. C., On the average size of sets in a Sperner family, Discrete Math., 6, 141-147 (1973) · Zbl 0267.05001
[33] Kruskal, J. B., The number of simplices in a complex, (Math Optimization Technics (1963), Univ. of California Press: Univ. of California Press Berkeley) · Zbl 0165.32801
[34] Lubell, D., A short proof of Sperner’s lemma, J. Combin. Theory, 1, 299 (1966) · Zbl 0151.01503
[35] Meshalkin, L. D., A generalization of Sperner’s theorem on the number of a finite set (in Russian), Teor. Verojatnost. i Primen., 8, 219-220 (1963) · Zbl 0123.36303
[36] Milner, E. C., A combinatorial theorem on systems of sets, J. London Math. Soc., 43, 204-206 (1968) · Zbl 0155.02804
[37] Schrijver, A., Theory of linear and integer programming, (Wiley-Interscience Series in Discrete Mathematics (1986), Wiley: Wiley Chichester) · Zbl 0665.90063
[38] S. Shahriari, On the structure of maximum 2-part Sperner families, Discrete Math., to appear.; S. Shahriari, On the structure of maximum 2-part Sperner families, Discrete Math., to appear. · Zbl 0897.05083
[39] Sperner, E., Ein Satz über Untermengen einer endlichen Menge, Math. Z., 27, 544-548 (1928) · JFM 54.0090.06
[40] Wilson, R. M., The exact bound in the Erdős-Ko-Rado theorem, Combinatorica, 4, 247-257 (1984)
[41] Yamamoto, K., Logarithmic order of free distributive lattices, J. Math. Soc. Japan, 6, 347-357 (1954)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.