Skip to content

Homework for Combinatorics 1

Tháng Mười Một 7, 2010

This is a homework from my Introductory course in Combinatorics at Rutgers. Some of the problems do not require any sophisticated tools, just an open mind. Enjoy !!

(1) Deduce Erdos-Ko-Rado theorem from Katona-Kruskal theorem.

(2) Prove that if F and G are two upsets, then 2^n |F \cap G| \ge |F||G| . (Recall that a upset is a collection of subsets of the group set such that if
A \in F then $B \in F$ for any $A \subset B$.)

(3) Prove that in the random graph G(2k, 1/2) (having 2k vertices and edge probability 1/2), P(maximum \,\,\, degree \le k-1) \ge 4^{-k}.

(4) Prove the 2-part Sperner theorem. If X is partitioned into two non-empty sets X_1 and X_2 and F is a family such that for any A \subset B in F, A \backslash B is not in X_1 or in X_2, then |F| \le { n \choose \lfloor n/2 \rfloor } .

(5) Prove that g_d (n,r) \le 2^{d-1} \lceil rd^{1/2} \rceil   { n \choose \lfloor n/2 \rfloor } .

(6) Let F be a upset. Prove that the average size of an element of F is at least n/2.

From → Khác

9 phản hồi
  1. Thang permalink

    Anh Văn ơi, em hỏi câu lạc đề tí chút.
    Em đang làm hồ sơ apply vào posgraduate programgs of US universities.
    Không biết ở US người ta dịch “toán cao cấp” là gì ?
    Các môn Đại số tuyến tính, Giải tích (cổ điển) 1 biến, nhiều biến ở VN bị ghi chung tất là Toán cao cấp.
    Toán cao cấp = Advanced Math hay Higher Math ?

    Sinh viên VN được >= 8.0/10 thì là loại giỏi. Quy ra thành 3.25/4 thì là loại B – trung bình, thế thì thiệt quá.
    Mà em cũng chả biết làm thế nào, trường nó cứ bắt qui ra.

    • We cover basic counting techniques (such as inclusion-exclusion), extremal set system (theorems such as Sperner), linear algebraic method (spectral of graphs,
      dimension argument), and some probability (Littlewood-Offord problem, correlation inequalities). I planed to write notes, but lots of things come unexpected, so maybe next time.
      I will post some selected sub-topics, though.

      • Lê Đại Trí Mẫn permalink

        Thanks for your reply! You can ask your students to scribe notes! It works very well with the courses I took, and you only need to proofread the notes. A lot of books grew out of notes like these!

    • 1. Đại số tuyến tính = Linear Algebra
      2. Bạn nói giải tích nào? Theo suy đoán thì chắc là Calculus, Multivariable Calculus.
      Viết 1 cái courses description nộp là ok thôi.
      Có thể để Linear Algebra and Calculus 1, Calculus 2, blah.
      Bạn có thể tham khảo description form này (từ trang 2 thôi nhé)
      http://www.math.washington.edu/Grads/Applying/supplementalform.pdf

  2. Cac mon thi anh thay tot nhat la dich ra tung mon mot, nhu DSTT la Linear Algebra vv, ghi chung nhu the khong co y nghia gi.

    Nue 8.00 la gioi thi em cu de la A, va neu can viet them mot bang chu thich ve he thong cho diem o VN (tren 10).

  3. Lê Đại Trí Mẫn permalink

    Would you please let us know what topics you cover in your course? Similarly to Tao’s blog, students like us will benefit a great deal by studying lecture notes from a great researcher like you. All best wishes!!!

  4. Blue permalink

    Chúc mừng anh Văn nhân ngày Nhà giáo Việt Nam 20/11. Kính chúc anh sức khỏe dồi dào, có nhiều niềm vui trong cuộc sống, và tiếp tục có những đóng góp trong việc giảng dạy cho sinh viên Việt nam.

  5. vu ha van permalink

    @Blue

    Cam on Blue nhieu. Dan My rat lac hau, chua nghi ra ngay hien chuong :=))

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: