Skip to content

Homework for combinatorics 1 (part 2)

Tháng Mười Hai 1, 2010

(1) Let S be a set of at least n+2 points in R^n. Prove that S can be partitioned into two subsets whose convex hulls intersect.

(2) Let C_1, \dots, C_m be convex sets in R^n such that any n+1 of them intersect. Prove that all of them intersect.

(3) Let p be a fixed prime. Construct a family of \Omega (n^3) subsets of \{1, \dots, n \} such that each has cardinality p^3 but any two has intersection
either 0, 1, p or p^2.

(4)* Let F be a family of subsets of \{1, \dots, n \} such that the intersection of any three is even. Prove that for all sufficiently large n, |F| \le 2^{n/2}.

(*) is a bonus problem, it does not count if you cannot do it, but if you can, I am willing to hear the solution.


From → Không phân loại

4 phản hồi
  1. Very interesting problems!

    (1) If a point is inside the CH of the other n+1, can that be considered an answer?

    (4) I’m just curious, are you discussing the dimensionality argument in class? I think I’ve seen the version where the intersection of every two is even, where the dimensionality argument was used.

  2. BTW, bác Văn, what if somebody posts a solution here and a student in your class sees it?

    • The due date is next Thursday, so if you do after that, it is OK. Also if it is in Vietnamese, then it may be safe, unless they apply some good translating program.

Trả lờ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: Logo

Bạn đang bình luận bằng tài khoản Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

%d bloggers like this: