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


1 Problem 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


Since m,n>0,

n(n1)2m>n24m2nn22mnn2 (2(n2)>m)
(n2)m>r22(r1)n2. (r=n22m+n)


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.


By the linearity of expectation,


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.


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


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


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

3 Problem 3


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


For general k, we will show that


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


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}.



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


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


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.