Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "An extremal theorem in the hypercube"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: An extremal theorem in the hypercube. | An extremal theorem in the hypercube David Conlon St John s College Cambridge CB2 1TP United Kingdom D.Conlon@dpmms.cam.ac.uk Submitted May 4 2010 Accepted Jul 18 2010 Published Aug 9 2010 Mathematics Subject Classification 05C35 05C38 05D99 Abstract The hypercube Qn is the graph whose vertex set is 0 1 n and where two vertices are adjacent if they differ in exactly one coordinate. For any subgraph H of the cube let ex Qn H be the maximum number of edges in a subgraph of Qn which does not contain a copy of H . We find a wide class of subgraphs H including all previously known examples for which ex Qn H o e Qn . In particular our method gives a unified approach to proving that ex Qn C2t o e Qn for all t 4 other than 5. 1 Introduction Given two graphs G and H ex G H is the maximum number of edges in a subgraph of G which does not contain a copy of H. The study of such numbers was initiated by Paul Turan 19 when he determined the maximum number of edges in a graph on n vertices which does not contain a clique of size r that is ex Kn Kr . For any graph H the value of ex Kn H is known 13 to be intimately connected to the chromatic number of H. In particular it is known 16 that ex Kn H o e Kn if and only if H is bipartite. In this note we will be similarly interested in determining subgraphs H of the hypercube Qn for which ex Qn H o e Qn . The hypercube Qn is the graph whose vertex set is 0 1 n and where two vertices are adjacent if they differ in exactly one coordinate. This graph has 2n vertices and being n-regular 2n-1n edges. Erdos 11 was the first to draw attention to Turan-type problems in the cube when he asked how many edges a C4-free subgraph of the cube can contain. He conjectured that the answer is 2 o 1 e Qn and offered 100 for a solution. Improving a long-standing result of Chung 8 Thomason and Wagner 18 recently gave an upper bound of roughly 0.6226e Qn for ex Qn C4 . This remains a long way Supported by a Junior Research Fellowship at St John s College. .