CS-E4555 - Combinatorics, 07.01.2019-12.04.2019
This course space end date is set to 12.04.2019 Search Courses: CS-E4555
Topic outline
-
-
Scribe for Lecture 1: by Miika Leinonen Assignment
-
Scribe for Lecture 2: by Tarmo Nurmi and Sara Heydari Assignment
-
Scribe for Lecture 3: by Ly Orgo Assignment
-
Scribe for Lecture 4: by Hasti Nariman Zadeh Assignment
-
Scribe for Lecture 5: by Zhang Guangyi Assignment
-
Scribe for Lecture 6 by Minoo Zarsav Assignment
-
Scribe for Lecture 7 by Mehdi Saman Booy Assignment
-
Scribe for Lecture 8: Max Franck and Jon Galán Assignment
-
Scribe for Lecture 9: Tuomas Kyttä and Valtteri Lipiäinen Assignment
-
Scribe for Lecture 10 Assignment
-
Scribe for Lecture 11 Assignment
-
Bonus Question 1 (Graph Product) Assignment
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\).
-
Bonus Question 2 (Tight Example) Assignment
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.
-
Bonus Question 3 (Shortest Cycle) Assignment
Show a polynomial time algorithm to find a shortest cycle in any graph \( G \). Prove formally its correctness and running time.
-
Bonus Question 4 (Nice tree decomposition) Assignment
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|)\).
-
Bonus Question 5 (Tree decomposition construction) Assignment
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
- \( \cup_i V_i = V(G) \)
- For each edge \( uv \in E(G) \), \( u, v \in V_i \) for some \( i \in [q] \)
- 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?
-
Open Problem (Tuza's Conjecture) Assignment
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.
- (100 B-points, Full Conjecture) Prove that for any graph \( G \), \( \tau(G) \leq 2 \beta(G) \).
-