Question 1

For the following sets of timings of dance classes, figure out what is the largest number of classes that you can attend in a conflict-free fashion: The number of classes is N = 9. The timings of the classes are given by: 1. [1 - 5] 2. [6 - 10] 3. [11- 15] 4. [16 - 20] 5. [2 - 8] 6. [3 - 8] 7. [2 - 7] 8. [9 - 12] 9. [13 - 17] Consider 4 sets as follows: $W = \{w_1, w_2, w_3\}$, $X = \{x_1, x_2\}$, $Y = \{y_1, y_2, y_3\}$ and $Z = \{z_1, z_2\}$. Given capacity constraints are as follows: $$c(w_2) = c(y_1) = c(y_3) = 1,$$ $$c(w_1) = c(w_3) = c(x_2) = c(y_2) = c(z_1) = 2,$$ $$c(x_1) = c(z_2) = 3$$ $$c(w_i, x_i) = 1, \text{ for all } w_i \in W \text{ and all } x_i \in X,$$ $$c(y_i, z_i) = 1, \text{ for all } y_i \in Y \text{ and all } z_i \in Z$$ $$c(x_1, y_1) = 1, c(x_1, y_2) = 2, c(x_1, y_3) = 1$$ $$c(x_2, y_1) = 0, c(x_2, y_2) = 2, c(x_2, y_3) = 1.$$ Identify the size of a largest collection of 4-tuples from the sets $W, X, Y$ and $Z$ satisfying the given constraints Let $G$ be a simple, undirected, unweighted graph. We use $V(G)$ to denote the vertex set of $G$ and $E(G)$ to denote the edge set of $G$. Recall that if we have an empty graph (i.e, a graph where $V(G) = E(G) = \emptyset$), then by convention it (vacuously) satisfies the properties suggested in the given subquestions Consider the set system $(U, \mathcal{F})$ defined as follows. - The universe $U$ is $V(G)$. - A subset of vertices $S \subseteq V(G)$ belongs to $\mathcal{F}$ if the subgraph induced by $S$ has maximum degree three. Which of the following properties is/are NOT satisfied by $\mathcal{F}$?