这个作业是来自美国的关于完成颜色、三角形等数学问题的数学作业代写
Math 465 Homework 12
Problem 1. Suppose that we color the edges of K6 with two colors (say, red and blue). Prove that there are at least two monochromatic triangles.
Problem 2. Suppose that we colored each edge of K66 red, blue, green, or yellow. Prove that there is a monochromatic triangle (that is, a triangle whose three edges have the same color).
[Note: This says R(3, 3, 3, 3) ≤ 66.]
Problem 3. Let n be a positive integer, and suppose that we color the edges of K2n−1 with two colors (say, red and blue). Prove that if n is even, then there is a monochromatic K1,n.
Problem 4. Let n > 1 be an integer. Prove that R(n + 2, 3) > 3n.
[Hint: Homework 1 Problem 8]
Problem 5. Consider the network depicted below; the numbers near the edges are their capacities.
(a) Find a flow in the network with maximum value.
(b) Find a cut in the network with minimum capacity.
Problem 6. Let G = (U, V, E) be a simple bipartite graph, and let k = |U|. You are not allowed to use Hall’s Theorem in this problem (we’re going to prove the “hard” direction in part (e)).
(a) Define a network H = (W, A) on the vertex set W = U ∪V ∪ {s, t} with edges and capacities given by:
• an edge e : u → v with capacity c(e) = 1 whenever u ∈ U, v ∈ V are adjacent in G,
• an edge e : s → u with capacity c(e) = 1 whenever u ∈ U, and
• an edge e : v → t with capacity c(e) = 1 whenever v ∈ V .
Construct a bijection between matchings in G and flows in H.
(b) Define a network H0 = (W, A) on the vertex set W = U ∪V ∪{s, t} with edges and capacities given by:
• an edge e : u → v with capacity c(e) = k whenever u ∈ U, v ∈ V are adjacent in G,
• an edge e : s → u with capacity c(e) = 1 whenever u ∈ U, and
• an edge e : v → t with capacity c(e) = 1 whenever v ∈ V .
Prove that a function f : A → Z defines a flow in H if and only if it defines a flow in H0.
(c) What is the relationship between the size of a matching in G and the value of the corresponding flow in H0?
(d) Prove that if there is no matching of U into V , then there exists a cut (X, Y ) in the network
H0 such that c(X, Y ) < k.
(e) Prove that if there is no matching of U into V , then there exists a set S ⊆ U such that |S| > |NG(S)|.
Problem 7. Consider the bipartite graph G = (U, V, E) depicted below (left), and the corresponding network H = (W, A) as defined in Problem 6(a).
(a) Find a flow in the network with maximum value.
(b) Find a cut in the network with minimum capacity.
(c) Find a matching in the bipartite graph with the maximum number of edges.