Assignment 2 recall that a tournament is a complete graph

Question

Assignment 2-

1. Recall that a tournament is a complete graph with directed edges (so we think of the vertices as players in a tournament in which every pair of players play each other, with a directed edge (u, v) if u beats v). Fix a positive integer k. We say a tournament T has Property S_k if for every U ⊂ V (T) with |U| = k, there exists a vertex y ∉ U such (y, x) is an arc for every x ∈ U (i.e. there is a player y that beats every player in U). Show that if

then there exists a tournament on n vertices and Property S_k.

2. Suppose G is a graph. In this problem, we shall use the probabilistic method to show that G has a subgraph H that is bipartite and has at least half as many edges as G does. Choose a random subset S ⊆ V (G) by independently choosing each vertex to be in S with probability ½.

Let H be the subgraph of G consisting of all vertices in V (G), and all edges with exactly one end in S.

(a) For each edge e ∈ E(G), let X_e be the random variable that is 1 if e ∈ E(H) and 0 otherwise. Show that E(X_e) = ½.

(b) Use part (a) to show E[|E(H)|] = ½|E(G)| and conclude the result.

3. Let G be a graph. A dominating set in G is a set U ⊂ V (G) such that every vertex in V (G)\U is adjacent to at least one vertex in U. In this problem we will prove the following:

"Let G be a graph in which every vertex has degree at least δ (where δ > 1). Then G has a dominating set with at most n · (1 + ln(1 + δ)/1 + δ) vertices."

This is a surprisingly small fraction of the vertex set. To prove this, let p ∈ (0, 1) be arbitrary. Suppose we pick vertices in G randomly and independently with probability p. For any X ⊆ V (G), let Y_X be the set of all vertices in V (G)\X that do not have any neighbor in X.

(a) Show that X ∪ Y_X is a dominating set in G.

(b) Show that E[|X|] = np, and for any v ∈ V (G), P[v ∈ Y_X] ≤ (1 - p)^1+δ.

(c) Using part (a), show there exists X ⊆ V (G) such that

|X| + |Y_X| ≤ np + n(1 - p)^1+δ.

(d) By choosing p = ln(1 + δ)/1 + δ, and using the fact that 1 - p ≤ e - p for p ∈ (0, 1) (you can assume this without proof), conclude the proof of the theorem. (Using calculus, one can prove our choice of p is optimal).

4. Prove the following properties of G(n, p):

(a) G(n, p) is a probability space.

(b) If a property P happens almost surely in G(n, p) and a property Q happens almost surely in G(n, p), then the property P ∩ Q happens almost surely in G(n, p). (P ∩ Q is the property that both P and Q happen.)

5. (a) Suppose p = p(n) satisfies pn → 0 as n → ∞. Show that almost surely, a graph in G(n, p) does not contain K₃ as a subgraph.

(b) Suppose p = p(n) satisfies pn → ∞ as n → ∞. Show that almost surely, a graph in G(n, p) contains K₃ as a subgraph.

6. A fundamental problem in distributed computing is designing algorithms so that processors (think of these as vertices in a graph) in a network can communicate effectively via channels (think of these as edges in a graph). One approach to this is to centralize the network by picking one processor to coordinate all the actions. However, if a network has large diameter, this is inefficient. Another approach that is considered is partitioning the network into regions with small diameter. This motivates the study of the behavior of the following function:

Definition- Let n, d be fixed positive integers d < n, and choose ∈ with 0 < ∈ < 1/4. Define f(n, ∈, d) to be the smallest positive integer l such that for every graph G on n vertices, E(G) can be partitioned into sets E₀, E₁, . . . , E_l such that |E₀| ≤ ∈n² and the diameter of E_i is at most d for 1 ≤ i ≤ l.

Think of E₀ as small negligible subset of throw away edges that obstruct partitioning E(G) into small diameter subgraphs.

One would believe that, in order to partition a graph into graphs with diameter 2, one would need many subgraphs. This is in fact the case: in this problem we will prove that, for partitioning a graph into diameter 2 subgraphs, one needs at least a linear number of partitions.

"Let n be a fixed positive integer, and 0 < ∈ < 1/4. Then there exists a constant C > 0 depending only on ∈ such that

f(n, ∈, 2) ≥ Cn,

almost surely."

We now begin the proof of this statement. Let n be a positive integer, and p ∈ (0, 1). Let G(n, n, p) be the probability space whose objects are all the bipartite graphs with partition (A, B) with |A| = |B| = n, where each of the n² possible edges appears independently with probability p.

(a) Show that, almost surely, all complete bipartite graphs G ∈ G(n, n, p) have at most 2n/1 - p edges.

(b) It is known that, almost surely, a random graph in G(n, n, p) has at pn² + o(n²) edges. Suppose ∈ < 1/4, and let p = 3/4 + ∈. By considering G(n/2, n/2, p), conclude the desired result.