Topic outline

    • Assignment icon
      Scribe for Lecture 1: by Miika Leinonen Assignment
      Not available unless: Your Student number (from Sisu) is 479893
    • Assignment icon
      Scribe for Lecture 2: by Tarmo Nurmi and Sara Heydari Assignment
      Not available unless any of:
      • Your Student number (from Sisu) is 430955
      • Your Student number (from Sisu) is 546412
    • Assignment icon
      Scribe for Lecture 3: by Ly Orgo Assignment
      Not available unless: Your Student number (from Sisu) is 600853
    • Assignment icon
      Scribe for Lecture 4: by Hasti Nariman Zadeh Assignment
      Not available unless: Your Student number (from Sisu) is 662367
    • Assignment icon
      Scribe for Lecture 5: by Zhang Guangyi Assignment
      Not available unless: Your Student number (from Sisu) is 663256
    • Assignment icon
      Scribe for Lecture 6 by Minoo Zarsav Assignment
      Not available unless: Your Student number (from Sisu) is 685315
    • Assignment icon
      Scribe for Lecture 7 by Mehdi Saman Booy Assignment
      Not available unless: Your Student number (from Sisu) is 738987
    • Assignment icon
      Scribe for Lecture 8: Max Franck and Jon Galán Assignment
      Not available unless any of:
      • Your Student number (from Sisu) is 476508
      • Your Student number (from Sisu) is 424903
    • Assignment icon
      Scribe for Lecture 9: Tuomas Kyttä and Valtteri Lipiäinen Assignment
      Not available unless any of:
      • Your Student number (from Sisu) is 718871
      • Your Student number (from Sisu) is 480002
    • Assignment icon
      Scribe for Lecture 10 Assignment
      Not available unless: Your Student number (from Sisu) is xxxx
    • Assignment icon
      Scribe for Lecture 11 Assignment
      Not available unless: Your Student number (from Sisu) is xxxx
    • Assignment icon
      Bonus Question 1 (Graph Product) Assignment
      Not available unless: You are a(n) Student

      Let for any two undirected graphs \( G \) and  \( H \), the lexicographic graph product  \( G \times H \) be a graph such that

      • The vertex set of  \( G \times H \) is the cartesian product \( V(G) \times V(H) \);
      • Any two vertices \( (u,v) \) and \( (x,y) \) are adjacent in \( G \times H \) if and only if either \( u \) is adjacent with \( x \) in \( G \) or \( u=x \)and \( v \) is adjacent with \( y \) in \(H\).
      Prove that \(\omega(G \times H) = \omega(G) \omega(H) \), where \(\omega(G)\) represents the clique number for any graph \(G\).

    • Assignment icon
      Bonus Question 2 (Tight Example) Assignment
      Not available unless: You are a(n) Student

      From Lecture 1, generalize the tight example given on page 6 to an \( n \times n \) \(\{0, 1\}\)-matrix which forbids \( \left(\begin{array}   11 & 1 \\ 1 & 1 \end{array}\right) \) patterns and contains \(\Omega( n\sqrt{n}) \) many ones.

    • Assignment icon
      Bonus Question 3 (Shortest Cycle) Assignment
      Not available unless: You are a(n) Student

      Show a polynomial time algorithm to find a shortest cycle in any graph \( G \). Prove formally its correctness and running time. 

    • Assignment icon
      Bonus Question 4 (Nice tree decomposition) Assignment
      Not available unless: You are a(n) Student

      Show that for any graph \( G=(V, E) \), there exists a nice tree decomposition \( \mathcal{T} = (T, \{B_i\}_i) \) of width \( tw(G) \) such that  \( |V(T)| =O(tw(G).|V|)\).

    • Assignment icon
      Bonus Question 5 (Tree decomposition construction) Assignment
      Not available unless: You are a(n) Student

      Show that for any graph \( G=(V, E) \) and a family of subsets of vertices \( \mathcal{V} = \{V_1, V_2, \dots V_q\} \) such that 


      1.  \( \cup_i V_i = V(G) \)
      2.  For each edge \( uv \in E(G) \), \( u, v \in V_i \) for some \( i \in [q] \)
      3. For each \( V_i \) ( \( i\geq 2 \) ), there exists a \( j<i \), such that \( (\cup_{k=1}^{i-1}V_k) \cap V_i \subseteq V_j \)

      Show formally how to create a valid tree decomposition of \( G \) using such a family \( \mathcal{V} \) as the set of bags? 

    • Assignment icon
      Open Problem (Tuza's Conjecture) Assignment
      Not available unless: You are a(n) Student


      Given a graph \( G= (V, E) \), let \( \beta(G) \) be the maximum number of edge-disjoint triangles in \( G \) ang \( \tau(G) \) be the minimum number of edges such that there exists a subset of edges \( F \subseteq E \) of size \( \tau(G) \), such that \( G - F\) is triangle-free. 

      • (100 B-points, Full Conjecture) Prove that for any graph \( G \)\( \tau(G) \leq 2 \beta(G) \).
      • (50 B-points) Prove that for any graph \( G \)\( \tau(G) \leq (3- \epsilon) \beta(G) \), where \(\epsilon > 0\) is some fixed constant. This is already proven in a paper here. Points will be awarded only for proofs different than the paper.