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.
ഇപ്പോള്‍ നീ ഒരു കോംപൌണ്ടും ഇത് ഉറപ്പിക്കുന്നില്ല, പക്ഷേ അതിന്റെ കഷ്ണങ്ങള്‍ ചേര്‍ന്നു തീർക്കാന്‍ പറ്റും. താഴെയൊന്ന് ശ്രമിക്കൂ അല്ലെങ്കില്‍ നിങ്ങള്‍ക്കുതന്നെ ടൈപ്പ് ചെയ്യുക.
ഒരു സ്വതന്ത്ര അക്കൗണ്ട്, നിങ്ങൾ പഠിച്ച കാര്യങ്ങൾ, നിങ്ങളുടെ പ്രശ്‌നങ്ങൾ പരിഹരിച്ചിരിക്കുന്ന പ്രശ്‌നങ്ങൾ, ഒരു സ്ഥലത്ത്‌ ഒരു ടീച്ചർ, ഈ പേജിനെ കുറിച്ച് ചോദിക്കാവുന്നതാണ്‌.
മുകളില്‍ ഒപ്പ് വയ്ക്കുക ലോഗിന്ഇവിടെ ഉപയോഗിച്ചിരിക്കുന്ന ചിഹ്നങ്ങള്‍
ഒരു പ്രത്യേക പത്രികയിൽ, ഒരു ചിത്രത്തിന്‍റെ പ്രതീകം, അതിലുള്ള എല്ലാ അക്ഷരങ്ങൾ എന്നിവയ്‌ക്കും വേണ്ടിയുള്ളതാണ്‌.
ആളുകൾ ചോദിക്കുന്നു
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.
ഈ താളിലെ ഭാഗങ്ങൾ മാറ്റുന്നു Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). ഇവിടെ വളച്ചൊടിച്ച്, വീണ്ടും പ്രഹരം, തെറ്റുകള്‍ നമ്മുടേതാണ്.
കൂടുതല്‍ 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