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 𝐹 βŠ† 𝑃(𝑋).