题目：Maximum density of copies of a subgraph in the n-cube and perfect cycles

讲座人： John Goldwasser(west Virginia University)

时间： 2015年6月3日（星期三）下午4：00-5：00

地点：信息楼四层学术报告厅

讲座内容:The n-cube, denoted Qn, is the graph whose vertices are the set of binary n-tuples, with two vertices adjacent if and only if they differ in precisely one coordinate. Let H be a set of vertices in Qd, for some fixed d. The d-cube-density of H, denoted π(H,d), is the limit as n goes to infinity of the maximum fraction, over all subsets S of the vertices of Qn, of sub-d-cubes whose intersection with S is an exact copy of H. It is not hard to show that π(H,4) ≥ 3/32 for every set of vertices in Q4. Let C2d denote a “perfect” 2d-cycle – a cycle where each pair of opposite vertices is Hamming distance d apart. We show that π(C8,4) = 3/32. So it is the subgraph of Q4 most difficult to create lots of copies of in a large n-cube. We conjecture that the same is true of C2d among all sub-graphs of Qd for any d>3.

To obtain our result we found an equivalent problem counting the number of sequences of length d of an n-set with a certain property. To solve the sequence problem we needed to determine which bipartite graph with n vertices induces the most copies of the graph on four vertices with two disjoint edges.

讲座人简介:John Goldwasser has been a professor in the Department of Mathematics at West Virginia University for 25 years. Prior to that he taught in Wisconsin, Iowa, and Massachusetts in the USA, as well as in Malawi, Thailand, and Hungary.

Professor Goldwasser’s main area of interest is extremalcombinatorics, recently concerning questions about the structure of the n-cube.

讲座人简介:John Goldwasser has been a professor in the Department of Mathematics at West Virginia University for 25 years. Prior to that he taught in Wisconsin, Iowa, and Massachusetts in the USA, as well as in Malawi, Thailand, and Hungary. Professor Goldwasser’s main area of interest is extremalcombinatorics, recently concerning questions about the structure of the n-cube.