论文部分内容阅读
令Qn=[0,1]n表示维数为n的超立方.这篇论文的主要贡献是给出在Qn的对称群作用下维数为n的0/1-多面体的等价类计数问题的最新进展.在Qn的对称下维数为n的0/1-多面体的等价类也称作Qn的满维0/1-等价类.计数满维0/1-等价类是涉及0/1-多面体的组合学与几何学的基本问题之一.
通过系统的应用超立方的对称以及计算机程序,Oswin Aichholzer完成了维数不超过5的满维0/1-等价类计数.此工作被认为是一个相当可观的收获.在1998年10月,Aichholzer进一步完成了对顶点数不超过12的6维超立方Q6的满维0/1-等价类的计数.五维超立方Q5被认为是最后—个其满维0/1-等价类可被完全计数的超立方.
在此论文中,我们成功的将顶点数大于2n-3的Qn的满维0/1-等价类的计数与包含在由Qn的顶点所展成的超平面中的0/1-多面体的等价类的计算联系在一起.计算包含在由超立方的顶点所展成的超平面中的0/1-多面体的等价类可以通过Pólya计数定理实现.这使得我们能够系统的计算顶点数大于2n-3的Qn的满维0/1-等价类的数目.应用此方法,我们完成了顶点数大于12的6维超立方Q6的满维0/1-等价类的计数.因此,结合Aichholzer的工作我们完成了Q6的满维0/1-等价类的计数.
在第一章,我们介绍与此论文相关的0/1-多面体的基本资料,大家将清晰的认识到为什么在0/1-多面体的不同的组合类型中人们将注意力集中在满维0/1-等价类.此章节包含了已知的关于满维0/1-等价类的计数结果,同时也包含一些经常使用的记号.
在第二章,我们回顾作用在Qn的顶点集合上的Qn的对称群的轮换指标.此轮换指标可被用作计数超立方的具有任意顶点个数的0/1-等价类(不一定是满维).为了尽量保持论文的自包含性,我们同时给出Pó1ya计数定理的一个简要的介绍.
在第三章,我们考虑Qn上超平面的放置.此章有两个目的.
首先,我们研究超立方中包含在若干超平面的交中的顶点的个数.我们推广了Saks得到的超立方中能被一个超平面所覆盖的顶点的个数的结果.基于得到的结果,我们建立了一个关于0/1-多面体的不等式,这个不等式将0/1-多面体的维数与其顶点个数联系在一起.此不等式使我们给出了非满维的0/1-多面体的一个分类.这个分类将在本文所考虑的问题中起到关键的作用.
其次,我们考虑由超立方的顶点所展成的超平面.这类超平面已被广泛研究.基于我们的目的,我们将考虑此类超平面的在超立方的对称群作用下的等价类.这将为第四章建立计数公式做准备.
在第四章,我们聚焦于顶点数大于2n-3的Qn。的满维0/1-等价类的计算.特别的,我们完成了顶点数大于12的6维超立方的满维0/1-等价类的计数.