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.
Manje Akukho kalkuli yokuxazulula le nto, kodwa amaphuzu ayo anga kalkuli. Zama enye ngezansi, noma ubhale yakho.
Amaphawu asetshenziswa lapha
Chofoza noma yiluphi uphawu lwesibonakaliso ukuze uthole ukuchaza okuphelele, isithombe, kanye nokuthi iyiphi inhlamvu ekhona ekhuluma ngaso.
Imibuzo abantu bebuza
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.
Amangxenye wale khasi aguqulwe kusuka Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). I-condensed futhi iphinde icaciswe lapha; amaphutha awusizo.
Okuningi 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