# Corticol superficial siderosis

1) A and B being a finite set with |A| > |B| and f : A -> B f being a linear mapping. Show that f is not
injective
2) 𝑘 ∈ ℕ

• being a positive natural Number. A and B being a finite set with |A| > k |B| and f : A -> B f
being a linear mapping. Prove that there is a 𝑏 ∈ 𝐵 with |𝑓
−1
({𝑏})| ≥ 𝑘 +1
𝑓
−1
: P(B) -> P(A) being the inverse image of f.
3) A being a non empty, finite set. An image f called 2-Colouring of a, if you assign a colour to every
element from A. Show through complete induction that there are 2
|𝐴|
variations of 2-Colouring from
A.
4) A Word with the length 𝑙 ∈ ℕ from the Alphabet ∑ := {0, 1} is a
Squence w = (𝑤0
, 𝑤1
, … , 𝑤𝑙−1) ∈ ∑
𝑙
. In the case 𝑙 =0 it’s the empty word/sequence(). 𝑛 ∈ ℕ .
Prove that there are 2
𝑛+1 − 1 Words with a length of maximum n over the Alphabet ∑
5) 𝑛 ∈ ℕ, A a finite set with |A|=n and ∑ := {0, 1}. F being the amount of all 2-Colouring from A, and W
the amount of all Words of the length 𝑛 over the Alphabet ∑.
Show that there is a Bijection between F and W.
6) G is a connected graph and 𝑘 ∈ ℕ is chosen that for all blocks 𝐵 ⊆ G applies |𝑉(𝐵)| ≤ 𝑘.
a) State an algorithm (without reasoning) that provides a largest (concerning Cardinality)
independent set in G and it’s runtime is in 𝑂(𝑓(𝑘)𝑝(|𝑉(𝐺)|)).
f being a function described by f: ℕ → ℕ that only depends on k while p: ℕ → ℕ is a
polynomial that only depends on |𝑉(𝐺)|.
b) Prove the correctness of the algorithm from a
c) Justify why the runtime from a is in 𝑂(𝑓(𝑘)𝑝(|𝑉(𝐺)|)).
7) 𝑐 ∈ ℕ
• a positive natural number. We know one Graph G, that is able to be made c-planar, that if
there is a set 𝑆 ⊆ V(G) with maximum of c nodes that: G – S planar.
a) Give an example graph G with a maximum of 10 nodes that can’t be made 2-planar but 3-planar.
Show that your example is correct by selecting a set 𝑆 ⊆ V(G) of Cardinality 3 so that G-S
planar.
b) G is a Graph that can be made 5-planar. How many pairwise node-disjoint copies of 𝐾5 can G
contain at a maximum. Provide the best boundaries and reasons for your answer.
c) G is a Graph with 𝑐 ∈ ℕ
• blocks, all blocks are able to be made into c-planars. How many pairwise
node-disjoint copies of 𝐾5 can G contain at a maximum? State the best boundaries in dependency
to b and c plus your reasoning behind it.
d) G being a graph and B a block from G, prove 𝑥
(𝐺) = 𝑚𝑎𝑥𝐵⊆G𝑥
(𝐵)
8) X is a finite set with n:= |𝑋|. A set 𝐹 ⊆ 𝑃(𝑋) is a Clutter, if for all 𝐴,𝐵 ∈ 𝐹 applies: If 𝐴 ⊆ 𝐵 then A=B
a) X:={1,2,3,4}. State a Clutter 𝐹 ⊆ 𝑃(𝑋) with |𝐹| = (
4
2
)
b) Clutter 𝐹 ⊆ 𝑃(𝑋). Show that |𝐹| ≤ (
𝑛
|
𝑛
2
|
)
9) X is a finite set with n:= |𝑋|. A set 𝐹 ⊆ 𝑃(𝑋) is a Clutter.
F is simple, if for all 𝐴, 𝐵 ∈ 𝐹 with 𝐴 ≠ 𝐵 applies: |𝐴 ∩ 𝐵| ≤ 1 and |𝐴| ≥ 2.
F is forestlike, if for all sub-families 𝑊 ⊆ 𝐹 an 𝐴 ∈ 𝑊 and an element 𝑎 ∈ 𝐴 exists, that 𝐵 ∈ 𝑊
with 𝐴 ≠ 𝐵 applies: if 𝐴 ∩ 𝐵 ≠ 0 then 𝐴 ∩ 𝐵 = {𝑎}.
C ⊆ 𝑃(𝑋) is a set that is a subset of X. A real 2-colouring of C is a transformation f:X->{red,blue},
so that 𝐴 ∈ 𝐶 applies 𝐴 ∩ 𝑓
−1
({𝑟𝑒𝑑}) ≠ 0 and 𝐴 ∩ 𝑓
−1
({𝑏𝑙𝑢𝑒}) ≠ 0.
a) G is a connected graph with a minimum of 2 nodes. We define the following set:
𝐵(𝐺) ≔ {𝑉(𝐵)|𝐵 ⊆ 𝐺 and 𝐵 is a block from 𝐺} ⊆ 𝑃(𝑉(𝐺))
Prove that B(G) is a simple and forestlike Clutter.
b) Show that there is a real 2-colouring for every simple and forestlike Clutter 𝐹 ⊆ 𝑃(𝑋). 