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

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

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

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

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

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