西弗吉尼亞大學(xué)John Goldwasser教授在中國人民大學(xué)信息學(xué)院作了題為子圖的拷貝在n立方體和完美周期的最大密度的講座，信息產(chǎn)業(yè)需要計(jì)算機(jī)科學(xué)與技術(shù)、信息系統(tǒng)與信息管理、數(shù)學(xué)基礎(chǔ)與理論等各方面的專業(yè)人才和復(fù)合人才。中國人民大學(xué)信息學(xué)院正是培養(yǎng)信息領(lǐng)域高素質(zhì)專業(yè)人才的基地。John Goldwasser教授講座的主要內(nèi)容是：

　　在n-立方體，記QN，是圖，其頂點(diǎn)是組二進(jìn)制正元組，具有兩個(gè)頂點(diǎn)相鄰的，當(dāng)且僅當(dāng)它們的不同之處正是一個(gè)坐標(biāo)。設(shè)H是一組頂點(diǎn)的在QD，對于某些固定e。對d立方體密度的H，表示為π(H，D)，是限制如正進(jìn)行到的最大分?jǐn)?shù)的無窮大，過QN的頂點(diǎn)的所有子集S，子的d的立方體，其交叉點(diǎn)以S是H的(H，4)≥3/32的精確副本不難證明π，每一套在第四季度的頂點(diǎn)。讓C2D表示一個(gè)“完美”的二維周期 - 周期，其中每對相對的頂點(diǎn)是漢明距離d分開。我們表明，π(C8,4)= 3/32。因此，第四季度是最困難的子圖在一個(gè)大的正立方體創(chuàng)造大量的副本。我們猜想，同樣是C2D的適用于任何D> 3的所有子圖QD之間。

　　以得到我們的結(jié)果，我們發(fā)現(xiàn)了一個(gè)等效問題計(jì)數(shù)的n組的長度d的序列的數(shù)目具有一定的特性。為了解決我們需要確定哪個(gè)偶圖有n個(gè)頂點(diǎn)誘導(dǎo)的曲線圖的最副本上四個(gè)頂點(diǎn)與兩個(gè)不相交的邊緣序列的問題。

　　John Goldwasser是美國西弗吉尼亞大學(xué)數(shù)學(xué)系教授，上海交通大學(xué)客座教授。他是極值組合和圖論研究領(lǐng)域的著名學(xué)者，在JCTA，JGT等國際著名的雜志上發(fā)表了50多篇論文，是立方體上圖論問題的研究專家。

　　原文：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.