maths.free › Combinatorics & Graph Theory › The Many Faces of Combinatorics › Extremal Set Theory
Extremal Set Theory
Let n be a positive integer and let [n]=1,2,\dots,n. In this section, we consider problems having the following general form: What is the maximum size of a family of subsets of [n] when the family is required to satisfy…
Extremal Set Theory
Let \(n\) be a positive integer and let \([n]=1,2,\dots,n\). In this section, we consider problems having the following general form: What is the maximum size of a family of subsets of \([n]\) when the family is required to satisfy certain properties.
Here is an elementary example.
Example
The maximum size of a family \(\cgF\) of subsets of \([n]\), with \(A\cap B\neq\emptyset\) for all \(A,B\in\cgF\), is \(2^{n-1}\).
For the lower bound, consider the family \(\cgF\) of all subsets of \([n]\) that contain\(1\). Clearly this family has \(2^{n-1}\) elements and any two sets in the family have non-empty intersection.
For the upper bound, let \(\cgF\) be a family of subsets with each pair of sets in \(\cgF\) having non-empty intersection. Then whenever a subset \(S\) is a member of \(\cgF\), the complement \(S'\) of \(S\) cannot belong to \(\cgF\). Since the entire family of all \(2^n\) subsets of \([n]\) can be considered as \(2^{n-1}\) complementary pairs, and at most one set from each pair can belong to \(\cgF\), we conclude that \(|\cgF|\le 2^{n-1}\).
As a second example, we can revisit from and restate the result as follows.
Example
The maximum size of a family \(\cgF\) of subsets of \([n]\) subject to the constraint that when \(A\) and \(B\) are distinct sets in \(\cgF\), then neither is a subset of the other, is \(\binom{n}{\lfloor n/2\rfloor}\).
It is worth noting that in , there is a very small number (one or two) of extremal families, , when \(\cgF\) is a family of subsets of \([n]\), \(|\cgF|= \binom{n}{\lfloor n/2\rfloor}\), and no set in \(\cgF\) is a proper subset of another, then either \(\cgF=\{S\subseteq[n]: |S|=\lfloor n/2\rfloor\}\) or \(\cgF=\{S\subseteq[n]: |S|=\lceil n/2\rceil\}\). And of course, when \(n\) is even, these are exactly the same family.
On the other hand, for , there are many extremal families, since for every complementary pair of sets, either member can be selected.
We close this brief tasting of extremal set theory with a real classic.
Condensed: the full section is in Keller & Trotter, Applied Combinatorics.
Tani ti. Asnjë kalkulator nuk e zgjidh këtë, por pjesët e saj janë të llogaritura. Provo një më poshtë, ose shkruaj tënde.
Një llogari e lirë shtohet shënime në çdo mësim, një regjistrim të asaj që ju keni përfunduar, problemet tuaja të zgjidhura në një vend, dhe një mësues që ju mund të pyesni rreth kësaj faqeje. Matematika vetë është e hapur për të gjithë, të regjistruar apo jo.
Regjistrohu HyrSimbolet e përdorura këtu
Prek çdo simbol për përkufizimin e plotë, një fotografi dhe se çfarë do të thotë çdo shkronjë në të.
Pyetja që bëjnë njerëzit
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Pjesa e kësaj faqeje është adaptuar nga Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). E përmbledhur dhe ri-shkruar këtu; gabimet janë tona.
Më shumë në Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs