Multicoloured extremal problems
type: Item
instance of: scholarly article
title: Multicoloured extremal problems
zbMATH Open document ID: 1052.05067
author: Béla Bollobás
author: Peter Keevash
author: Benny Sudakov
published in: Journal of Combinatorial Theory. Series A
publication date: 2004-10-01T00:00:00Z
review text: Let \({\mathcal A}_1,\dots,{\mathcal A}_k\) be set systems on the finite underlying set \(X\) which are called colours. A finite configuration of subsets of \(X\) with \(f\) elements is multicoloured (for this set of colours) if one can find a listing \(H_1,\dots,H_f\) of the configuration and a permutation \(\pi\) of \(\{1,\dots,k\}\) such that \(H_i\) belongs to \({\mathcal A}_{\pi(i)}\) for all \(i\). A very general extremal problem class can be formulated as follows: Assume there is a list of forbidden configurations, and a natural number \(k.\) Find \(k\) set systems, that is, \(k\) colours with maximum total number of elements such that there is no multicoloured forbidden configuration (for this set of colours). If \(k=2\) and the two colour families are the same then we may get back to the classical extremal problems: If the forbidden configuration is a two-element chain, then we have the Sperner problem, while two disjoint subsets give us the Erdős-Ko-Rado problem. If, in more generality, we have \(k\) identical colour classes and the forbidden configuration is a \(k\)-chain, then we get back to the classical Erdős problem on \(k\)-chains. The problem for two-uniform colour systems (graphs) was introduced by the second author and the third author (with others). The paper under review starts a systematic investigation of the general problem. Results on multicoloured chains, intersecting set systems and Sauer-Shelah type set systems are proved.
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 2105515
zbMATH Keywords: Sperner theorem
zbMATH Keywords: BLYM inequality
zbMATH Keywords: Erdős-Ko-Rado theorem
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: j.jcta.2004.05.003
OpenAlex ID: W2167591244
cites work: On the density of sets of vectors
cites work: On generalized graphs
cites work: Q3726125
cites work: SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
cites work: Q3942966
cites work: On a lemma of Littlewood and Offord
cites work: Q5510578
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: On the trace of finite sets
cites work: Q4050598
cites work: Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
cites work: Q4276003
cites work: A short proof of Sperner's lemma
cites work: Generalization of Sperner’s Theorem on the Number of Subsets of a Finite Set
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Logarithmic order of free distributive lattice
DOI: 10.1016/J.JCTA.2004.05.003
description: scientific article; zbMATH DE number 2105515