Exam questions Flashcards
poset
Poset: A partially ordered set (poset) is a set 𝑋 equipped with a binary relation
⪯ that is reflexive, antisymmetric, and transitive.
Hasse diagram
A graphical representation of a finite poset, where elements are represented by vertices, and the order relation is represented by edges, without transitive edges.
Immediate predecessor/cover relation
In a poset (𝑋,⪯), x is an immediate predecessor of y if x≺y and there is no z such that
x≺z≺y.
Linear order
A poset where every pair of elements is comparable.
Lexicographic order
An order defined on the Cartesian product of ordered sets, extending the order of each set to the product.
Erdős–Szekeres theorem
For any sequence of n^2+1 distinct real numbers, there is a subsequence of n+1 numbers that is either strictly increasing or strictly decreasing.
Smallest/minimum element
An element a in a poset such that a⪯x for all x in the poset.
Minimal element
An element
a in a poset such that there is no x ≠a with x⪯a
Linear extension
A linear order that contains the original poset order.
Show that every finite poset has a linear extension.
Proof: Using the topological sorting algorithm, we can extend any finite poset to a linear order by iteratively removing minimal elements and maintaining the order constraints.
Show that every finite poset has a minimal element.
Proof: In a finite poset, consider any chain of elements. Since the set
Show that every finite poset has an embedding into (2^𝑋,⊆)
Using the concept of down-sets, we can map each element of the poset to a subset of X, preserving the order.
Chains
A subset of a poset where every two elements are comparable.
Anti-chains
A subset of a poset where no two elements are comparable.
α(P)
The size of the largest anti-chain in the poset.
ω(P)
The size of the largest chain in the poset.
Prove that 𝛼⋅𝜔≥∣𝑋∣
Using Dilworth’s theorem, which states that in any finite poset, the size of the largest anti-chain is equal to the minimum number of chains needed to cover the poset.
Letn=∣X∣ and m=∣Y∣. How many functions are there from X to Y?
Number of functions from m^n.
Letn=∣X∣ and m=∣Y∣. How many functions are there from X to Y? proof
Each of the n elements in X has m choices in Y. Therefore, the total number of functions is m^n.
Use the last question to show that there are 2^n subsets of X.
Each element can either be included or excluded, giving 2 choices per element. For n elements, this results in 2^n subsets.
Show that X has 2^(n-1) subsets of odd size.
Each subset either includes or excludes the new element, so half of the 2^n subsets have an odd size, which is 2^(n-1).
Let
n=∣X∣ and m=∣Y∣. How many injective functions are there from X to Y?
There are m(m−1)(m−2)…(m−n+1) injective functions.
Let
n=∣X∣ and m=∣Y∣. How many injective functions are there from X to Y? proof
The first element in
X has m choices, the second has m−1 choices, continuing until the last element has m−n+1 choices.
Permutation
Permutation: A permutation of a set is a bijection from the set to itself.
One-row notation
A permutation can be represented by listing the images of each element in order.
Cycle in a permutation
A cycle is a subset of the permutation where elements are cyclically permuted.
Show that the number of subsets of size 𝑘 of X equals (n k)
The number of ways to choose k elements from n elements is (𝑛𝑘), which counts the number of k-element subsets of X.
Let (𝑖_1,…,𝑖_𝑟)∈𝑁^𝑟 be integers adding to n. How many such tuples of integers are there?
The number of ways to partition n into r parts is
(
n+r−1
r−1
).
Let (𝑖_1,…,𝑖_𝑟)∈𝑁^𝑟 be integers adding to n. How many such tuples of integers are there? proof
This can be shown using the stars and bars method.
Describe Pascal’s triangle.
A triangular array where each entry is the sum of the two directly above it.
State the Binomial Theorem.
(x+y)^n=∑ ( n choose k )x^(n−k)y^k
Rearranging “MISSISSIPPI” count number of ways to do it
Using multinomial coefficients, the number of ways is
(11!)/(4!4!2!1!).
