Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Luận Văn - Báo Cáo
Báo cáo khoa học
Báo cáo toán học: "Proof of an intersection theorem via graph homomorphisms"
Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Proof of an intersection theorem via graph homomorphisms"
Xuân Thủy
44
4
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Proof of an intersection theorem via graph homomorphisms. | Proof of an intersection theorem via graph homomorphisms. Irit Dinur Ehud Friedgut t Submitted Mar 31 2005 Accepted Mar 15 2006 Published Mar 21 2006 Mathematics Subject Classification 05d05 Abstract Let 0 p 1 2 and let 0 1 ra be endowed with the product measure Pp defined by Pp x p h 1 p n- hl where x P Xị. Let I c 0 1 n be an intersecting family i.e. for every x y 2 I there exists a coordinate 1 i n such that xi yi 1. Then PP I p. Our proof uses measure preserving homomorphisms between graphs. One of the fundamental questions first studied in extremal graph theory is the question of bounding the size of an intersecting family of sets. The most basic theorem in this vein is the Erdos-Ko-Rado theorem 2 that states that if k n 2 and F is an intersecting family of k-subsets of 1 . n then F n-ỉ . The theorem we present here is the analogue of the EKR theorem in the setting of the discrete cube endowed with the product measure. This useful theorem and several generalizations thereof has been proven and reproven in several papers see e.g. 4 5 1 3 but curiously enough none of these proofs seem to be related to the one we present here which relies in a mysterious way on a decomposition of the n dimensional torus into 1-dimensional circles. Here is the main theorem Theorem 1.1 Let 0 p 1 2 and let 0 1 n be endowed with the product measure pp defined by pp x phl 1 p n lxl where x V Xị. Let I c 0 1 n be an intersecting family i.e. for every x y 2 I there exists a coordinate 1 i n such that xi yi 1. Then pp I p. Before proving the theorem we must introduce some notation. All graphs G considered in this note will come endowed with a probability measure pG defined on their vertex set. 0Key words and phrases Intersecting families Product measure. School of Computer Science and Engineering Hebrew University Jerusalem Israel. email dinuri at cs.huji.ac.il Institute of Mathematics Hebrew University Jerusalem Israel. email ehudf at math.huji.ac.il. Research supported in part by the .
TÀI LIỆU LIÊN QUAN
Báo cáo toán học: "A proof of a theorem on trace representation of strongly positive linear functionals on $OP*-algebras$ "
Báo cáo toán học: "A new proof of the Szegö limit theorem and new results for Toeplitz operators with discontinuous symbol "
Báo cáo toán học: "Combinatorial proof of a curious q-binomial coefficient identit"
Báo cáo toán học: "Proof of the combinatorial nullstellensatz over integral domains, in the spirit of Kouba"
Báo cáo toán học: "A combinatorial proof of a formula for Betti numbers of a stacked polytope"
Báo cáo toán học: "An entropy proof of the Kahn-Lov´sz theorem a"
Báo cáo toán học: "Proof of the (n/2 − n/2 − n/2) Conjecture for large n"
Báo cáo toán học: "A Bijective Proof of a Major Index Theorem of Garsia and Gessel"
Báo cáo toán học: "A short proof for the number of permutations containing pattern 321 exactly once"
Báo cáo toán học: "A Short Proof of the Rook Reciprocity"
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.