Homework 3

Problem 1.

Your company makes two kinds of sauces, a meat sauce and a mushroom sauce. Both are made by mixing three ingredients: minced beef, mushrooms, and tomato concentrate. The composition of the sauces must follow these specifications:

Ingredient meat sauce mushroom sauce
beef at least \(40\%\) of total weight no specification (can be any amount)
mushrooms no specification (can be any amount) at least \(30\%\) of total weight
tomato at most \(35\%\) of total weight at most \(50\%\) of total weight

Every day, you can buy 4,000 kg of minced beef for 4,200 Won per kg, 3,200 kg of mushrooms for 1,600 Won per kg, and 6,000 kg of tomato concentrate for 1,400 Won per kg.

The sales price is 8,400 Won per kg for the meat sauce and 7,200 Won per kg for the mushroom sauce.

Assuming that you can sell arbitrary amounts of sauce, write a linear program to compute the daily amounts (and sauce composition) that will maximize your profit. Explain the meaning of your variables and your constraints!

Problem 2.

Prove the following version of the Lovász Local Lemma:

Let \(A_1, A_2, \ldots, A_n\) be events in an arbitrary probability space, and let \(G = (V, E)\) be a graph on the vertices \(V = \{1, 2, \ldots, n\}\) such that event \(A_i\) is mutually independent of all the events \(A_{j}\) where \((i, j) \not\in E\).

Suppose there are real numbers \(\mu_{1}, \mu_{2}, \ldots, \mu_{n}\) with \(0 \leq \mu_{i} < 1\) such that for all \(1 \leq i \leq n\) we have

\[ Pr[A_{i}] \leq \mu_{i} \prod_{(i, j) \in E} (1 - \mu_{j}) \]
Then
\[ Pr[\bigcap_{i} \bar{A_{i}}] \geq \prod_{i=1}^{n} (1 - \mu_{i}) > 0. \]

Problem 3.

Using the previous result, prove the following so-called Asymmetric Lovász Local Lemma:

Let \(A_1, A_2, \ldots, A_n\) be events in an arbitrary probability space, and let \(G = (V, E)\) be a graph on the vertices \(V = \{1, 2, \ldots, n\}\) such that event \(A_i\) is mutually independent of all the events \(A_{j}\) where \((i, j) \not\in E\), and such that there are no isolated vertices in \(G\).

If \(\sum_{(i,j) \in E} Pr[A_{j}] \leq 1/4\) for all \(i\), then

\[ Pr[\bigcap_{i} \bar{A_{i}}] \geq \prod_{i=1}^{n} (1 - 2Pr[A_{i}]) > 0. \]

Problem 4.

Use the Asymmetric Lovász Local Lemma to prove the following Theorem:

Let \(G\) be a graph with maximum degree \(\Delta \geq \beta^{\beta}\), where \(\beta \geq 2\). Then \(G\) has a proper coloring with \(16\Delta^{1 + 1/\beta}\) colors such that no color appears more than \(\beta\) times in the neighbourhood of any vertex.

Problem 5.

Transform the following problem to equational form:

maximize \(3x_1 - 2x_2\)
subject to \(2x_1 - x_2 \leq 4\)
\(x_1 + 3x_2 \geq 5\)
\(x_2 \geq 0\)