报 告 人：JohnGoldwasser教授
报告题目：Maximum density of copies of a subgraph inthe n-cube and perfect cycles
报告时间：5月13日（周三）下午3：30
报告地点：静远楼1508学术报告厅
Abstract: Then-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 onecoordinate.Let H be a set of verticesin Qd, for some fixed d.Thed-cube-density of H, denoted 
(H,d), is the limit as n goes to infinityof the maximum fraction, over all subsets S of the vertices of Qn, ofsub-d-cubes whose intersection with S is an exact copy of H.It is not hard to show that 
(H,4) 
3/32for every set of vertices in Q4.Let C2ddenote a “perfect” 2d-cycle – a cycle where each pair of opposite vertices isHamming distance d apart.We show that 
(C8,4) = 3/32.So it is the subgraph of Q4 most difficult tocreate lots of copies of in a large n-cube.We conjecture that the same is true of C2d among all sub-graphs of Qdfor any d>3.
To obtain ourresult we found an equivalent problem counting the number of sequences oflength d of an n-set with a certain property.To solve the sequence problem we needed to determine which bipartitegraph with n vertices induces the most copies of the graph on four verticeswith two disjoint edges.
John Goldwasser 教授个人简介
John Goldwasserhas been a professor in the Department of Mathematics at West VirginiaUniversity for 25 years.Prior to thathe taught in Wisconsin, Iowa, and Massachusetts in the USA, as well as inMalawi, Thailand, and Hungary.
ProfessorGoldwasser’s main area of interest is extremal combinatorics, recentlyconcerning questions about the structure of the n-cube.