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.
Dabar tu Joks skaičiuotuvas nenusistato, bet jo dalys yra skaičiuojamos. Pabandykite vieną žemiau arba įveskite savo.
Nemokama paskyra prideda pastabas apie kiekvieną pamoką, įrašą apie tai, ką baigėte, savo išspręstas problemas vienoje vietoje ir mokytoją, kurį galite paklausti apie šį puslapį. Pati matematika yra atvira visiems, kurie yra ar nėra užsiregistravę.
Prisijungti PrisijungtiČia naudojami simboliai
Bakstelėkite visus simbolius, kad būtų galima apibrėžti visą apibrėžimą, paveikslėlį ir ką reiškia kiekviena raidė.
Klausimai, kuriuos klausia žmonės
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.
Šio puslapio dalys pritaikytos nuo Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Čia yra įtikinamų ir iš naujo paaiškintų klaidų.
Daugiau informacijos 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