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 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 Qn for ex Qn C4 . This remains a long way Supported by a Junior Research Fellowship at St John s College. .
