0-1-多面體的計數(shù)性質(zhì).pdf

1、令Qn=[0，1]n表示維數(shù)為n的超立方.這篇論文的主要貢獻是給出在Qn的對稱群作用下維數(shù)為n的0/1-多面體的等價類計數(shù)問題的最新進展.在Qn的對稱下維數(shù)為n的0/1-多面體的等價類也稱作Qn的滿維0/1-等價類.計數(shù)滿維0/1-等價類是涉及0/1-多面體的組合學與幾何學的基本問題之一.
　　 通過系統(tǒng)的應(yīng)用超立方的對稱以及計算機程序，Oswin Aichholzer完成了維數(shù)不超過5的滿維0/1-等價類計數(shù).此工作被認為是一

2、個相當可觀的收獲.在1998年10月，Aichholzer進一步完成了對頂點數(shù)不超過12的6維超立方Q6的滿維0/1-等價類的計數(shù).五維超立方Q5被認為是最后—個其滿維0/1-等價類可被完全計數(shù)的超立方.
　　 在此論文中，我們成功的將頂點數(shù)大于2n-3的Qn的滿維0/1-等價類的計數(shù)與包含在由Qn的頂點所展成的超平面中的0/1-多面體的等價類的計算聯(lián)系在一起.計算包含在由超立方的頂點所展成的超平面中的0/1-多面體的等價類可以

3、通過Pólya計數(shù)定理實現(xiàn).這使得我們能夠系統(tǒng)的計算頂點數(shù)大于2n-3的Qn的滿維0/1-等價類的數(shù)目.應(yīng)用此方法，我們完成了頂點數(shù)大于12的6維超立方Q6的滿維0/1-等價類的計數(shù).因此，結(jié)合Aichholzer的工作我們完成了Q6的滿維0/1-等價類的計數(shù).
　　 在第一章，我們介紹與此論文相關(guān)的0/1-多面體的基本資料，大家將清晰的認識到為什么在0/1-多面體的不同的組合類型中人們將注意力集中在滿維0/1-等價類.此章節(jié)包

4、含了已知的關(guān)于滿維0/1-等價類的計數(shù)結(jié)果，同時也包含一些經(jīng)常使用的記號.
　　 在第二章，我們回顧作用在Qn的頂點集合上的Qn的對稱群的輪換指標.此輪換指標可被用作計數(shù)超立方的具有任意頂點個數(shù)的0/1-等價類（不一定是滿維）.為了盡量保持論文的自包含性，我們同時給出Pó1ya計數(shù)定理的一個簡要的介紹.
　　 在第三章，我們考慮Qn上超平面的放置.此章有兩個目的.
　　 首先，我們研究超立方中包含在若干超平面的交

5、中的頂點的個數(shù).我們推廣了Saks得到的超立方中能被一個超平面所覆蓋的頂點的個數(shù)的結(jié)果.基于得到的結(jié)果，我們建立了一個關(guān)于0/1-多面體的不等式，這個不等式將0/1-多面體的維數(shù)與其頂點個數(shù)聯(lián)系在一起.此不等式使我們給出了非滿維的0/1-多面體的一個分類.這個分類將在本文所考慮的問題中起到關(guān)鍵的作用.
　　 其次，我們考慮由超立方的頂點所展成的超平面.這類超平面已被廣泛研究.基于我們的目的，我們將考慮此類超平面的在超立方的對稱群