Combin.PS4

My Solution for Combinatorics for the Fall 2015 semester, Problem Set 4. Keep your Academic Integrity plz.

Try Firefox if your web browser (e.g. Chrome, IE) does not support MathML, a part of HTML5.

Combinatorics: Problem Set 4

Himemya

1 Problem 1

1.1

Recall the Turán theorem: if some graph G(V,E) has no r-clique, then |E|r22(r1)n2. Here is the contrapositive theorem: if |E|>r22(r1)n2, then the graph G(V,E) has r-clique.

Now consider the complement graph G(V,E) of G(V,E). Clearly, G has an independent set of size |S| if G has a |S|-clique. Let r=n22m+n, |E|=(n2)m. Due to the contrapositive theorem, we have done if we can prove

(n2)m>r22(r1)n2.

Since m,n>0,

4m2+4mn+n2>0
(n22mn)2n2(n24m2n)>0
(n22mn)2>n2(n24m2n)
n(n1)2m>n24m2nn22mnn2 (2(n2)>m)
(n2)m>r22(r1)n2. (r=n22m+n)

1.2

We uniformly sample a permutation π of [n] at random. For each vV, if for all neighbor v of uV it holds that πu>πv, we include v into the set S. Clearly S will be an independent set.

Consider a vertex u and its d neighbors. There are (d+1)! permutatoins for them, and only d! permutatoin usch that u is included into S, i.e.

Pr[uS]=d!(d+1)!=1d+1.

By the linearity of expectation,

?[|S|]=iVPr[iS]=iV1d(i)+1

where d(x) is the degree of the vertex x. Recall that iVd(i)=2m. The expectation will be minimized when vV,d(v)=2m/n, i.e.

?[|S|]iV12mn+1=n22m+n.

Therefore G must have an independent set S of size n22m+n.
Thanks hint from Song Renjie.

1.3

The equality holds when the complement graph is Turán graph.

2 Problem 2

Let ME be the largest matching of G. If Mk, we have done. Otherwise we can safely assume |M|k1. Let Y={vV|eM(e is incident to v)}. Then |Y|=2|M|2(k1). Clearly any edge is incident to at least one vertex in Y, otherwise M will not be the largest matching of G.

By the Pigeonhole Principle, some vertex yY must has degree of at least

|E||Y|>2(k1)22(k1)=k1.

In another word, there is a star of size k.

3 Problem 3

3.1

We show that N(k) is finite by induction on k. For the base case, it is easy to verify that

N(2)=2.

For general k, we will show that

N(k)2N(k1).

Suppose we have an n-player tournament where n=2N(k1). Take an arbitrary vertex v, and split V{v} into two subset S and T, where

S={uV{v}|u<v},
T={uV{v}|u>v}.

Since |S|+|T|+1=n=2N(k1), we have either |S|N(k1) or |T|N(k1).

If |S|N(k1). By induction hypothesis, there exists transitive tournament of size (k1) in S. Plusing the v such that uS,v<u, there exists transitive tournament of size k in S{v}.

If |T|N(k1). By induction hypothesis, there exists transitive tournament of size (k1) in T. Plusing the v such that uT,v>u, there exists transitive tournament of size k in T{v}.

3.2

N(k)=R(k,k).

We construct a bijective mapping between the universe of two-colorings of Kn and the universe of tournaments.

Given a two-coloring of Kn, we construct a unique tournament. For any u,vV such that u’s label is smaller that v’s, if (u,v) is red in the two-coloring, then let u<v, otherwise let v>u.

Obviously the mapping is injective. For all tournament, we can easily find the two-coloring which will be mapped to it. Thus the mapping is surjective. In conclusion, the mapping is bijective.

4 Problem 4

Consider any subset UU and their neighbors V={vV|uU((u,v)E)}. By counting the edges between the two sets, we have

uUd(u)=vVd(v)

where d(x) is the degree of vertex x. Since uU,d(u)δU, vV,d(v)ΔV, we have

δU|U|ΔV|V|
|U|ΔVδU|V|.

Recall that δUΔV, we have |U||V|. Due to the Hall’s theorem, there must be a matching in G such that all vertices in U are matched.

5 Problem 5

Let U={S1,S2,,Sn} be poset about the relation . We claim two obviously facts:

  • Fact 1.

    any subset U satisfies that for any different A,B,C we have ABC, if is an antichain.

  • Fact 2.

    any subset U satisfies that for any different A,B,C we have ABC, if is a chain.

If the largest antichain of U is larger than n, due to the fact 1, we have done. Otherwise, by the Dilworth theorem, U can be partitioned into at most n chains. Due to the Pigeonhole Principle, there is a chain which contains at least n sets. Due to the fact 2, we have done.

CC BY-SA 4.0 Combin.PS4 by himemeizhi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.