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.
Now you Không máy tính nào có thể tính toán được nó, nhưng các mảnh của nó có thể tính toán được. Thử một trong những cách dưới đây, hoặc gõ theo ý bạn.
Ký hiệu được dùng ở đây
Nhấn vào bất kỳ ký hiệu nào để xem định nghĩa đầy đủ, một bức ảnh, và ý nghĩa của từng chữ cái trong nó.
Câu hỏi người ta hỏi
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.
Một số phần của trang này được chuyển từ Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Được nén lại và giải thích lại ở đây; lỗi là của chúng tôi.
More in 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