# 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 πΉ β π(π).