英语原文共 18 页，支付完成后下载完整资料
调度问题
摘 要：本文引入了一个调度问题的概念，它是基于xile;xj形式的原子公式上的布尔函数S。将xi作为要执行的作业，考虑到xi作为待执行的作业，满足S的整数赋值调度作业受原子公式约束。调度计数函数对S的解的个数进行计数，证明了该计数函数是一个在允许的时隙数内的多项式。调度多项式包括图的色多项式、格的zeta多项式和拟阵的Billera-Jia-Reiner多项式。
对于任何调度问题，我们不仅将一个计数函数与解联系起来，而且将非交换变量中的一个准对称函数与一个准对称函数联系起来。这些调度函数包括Sagan、Gebhard和Stanley的半对称函数，以及Ehrenborg对于posets的准对称函数的近似变体。
在几何上，我们考虑了给定调度问题所有解的空间。我们通过证明解空间的h-向量是由调度多项式的移位给出的，从而扩展了Steingr msson的结果。此外，在布尔函数定义的一定条件下，证明了调度拟对称函数的解空间的可分性和基本展开的正性，以及调度多项式的H向量的正性。
1. 介绍
对于xi le; xj，i，jisin;[n]：= {1，...。。 ，n}，在原子式上，用布尔公式S给出了n个项目的调度问题。一个k-调度的解S是一个整数向量aisin;[k]n，被认为是xi的赋值，当xi＝ai时S是真的。我们将n项看作是要调度到离散时隙中的作业，原子公式被解释为对作业的约束。k-约束满足使用最多k个时隙的所有约束。
我们将对给定调度问题的解的个数感兴趣，并将调度计数函数chi;s(k)定义为k调度的解S的个数。我们的第一个结果表明，chi;s(k)实际上是k中的一个多项式函数。作为特殊情况，调度多项式包括图的色多项式、点阵的zeta多项式和poset的高阶多项式。
我们处理调度问题的方法包含代数和几何。从代数上讲，对于任何调度问题，我们不仅把解的计数函数联系起来，而且把非交换变量中的准对称函数和准对称函数联系起来，这些非交换变量连续记录了更多关于解本身的信息。在几何上，我们通过ehrhart理论、超平面安排和A型coxeter复形来考虑给定调度问题的所有解的空间。作为特殊情况，不同的调度结构包括Sagan和Gebhard[13]的色函数，以及Stanley[19]、Steingracute;msson[20]的色复形，以及Breuer、Dall和Kubitzke的超图着色复合物[9]、Gessel的p-分区准对称函数[14]、Billera、Jia、Reiner的Matroid不变量[5]和Posets的Ehrenborg的准对称函数变体[12]。
我们首先利用几何和代数的相互作用证明了希尔伯特级数型结果，证明了解空间的H矢量是由调度多项式移位的H矢量给出的。这包括并推广Steingracute;mmson关于色多项式和着色复数的结果到所有调度问题。在解的空间上施加一定的精细条件，可以得到更好的结果。我们关注的是布尔函数S可以被写成一种特殊的决策树的情况。这种决策树为调度问题提供了一个嵌套的if-then-else结构。在这种情况下，我们证明了解的空间是可分割的。这反过来又意味着调度拟对称函数在调度多项式的基本基和H向量上是积极的。
2. 准备工作和调度功能
定义2.1. 对原子公式xile;xj ，i，jisin;[n]，n个项的调度问题由布尔公式S给出。求解S的k时间表是整数向量aisin;[k]n，被认为是xi的赋值，使得当xi = ai时S为真。调度计数功能
chi;s(k) := #k-schedules solving S
计算解决给定S的k调度的数量。
假设我们有3个作业的调度问题。这三个工作中的任何一个都可以先开始，但根据先开始的工作类型，会有不同的要求。如果作业1或3首先启动，则另一个作业必须与作业2同时启动。如果作业2首先启动，则必须在下一个作业1之后才能启动作业3。我们将这些解解释为所有整数点，例如x1lt;x2=x3或x3lt;x1=x2或x2lt;x1lt;x3。重要的是，解只取决于坐标的相对顺序。
调度问题的解有一个自然的几何学，我们将在下面描述。有序集合划分或集合构成Phi;|=[N]是一系列非空集合(Phi;1，Phi;2，)。hellip;，Phi;k)，使得对于所有i，j，(Phi;icap;Phi;j=empty;)和(cup;iPhi;i=[n])。Phi;i是有序集划分的块，我们通常使用符号Phi;1|Phi;2|hellip;|Phi;k。注意，在每个块中，元素没有排序，所以排序集分区13|4|2|=[4]与31|4|2=[4]相同。我们将使用有序集分区来表示整数点，其坐标的相对顺序由分区块给出。例如，31|4|2表示所有整数点(x1、x2、x3、x4)，这样x1=x3lt;x4lt;x2。
辫状排列Beta;n是Rn中的超平面排列，对于所有i，jisin;[n]，Rn由超平面xi＝xj组成。超平面有一个公共交点，等于线x1=x2=hellip;=xn。将该排列投影到该线的正交补部，并与单位球面相交，得到一个称为A型Coxeter复合体的球面单纯形复合体，CoxAn-1。它可以作为单纯形边界的重心细分组合实现。
CoxAnminus;1的面由有序集分区自然标记。Coxeter复合体的每一个非空面都可以与一个由Beta;n在Rn上诱导的细胞分解面相关联。Beta;n的单元分解的面指定了每对i，j是否xi＜xj，xi＞xj，或xi＝xj，确切地说是调度问题的原子公式。固定面中的所有点具有相同的坐标相对顺序。这种相对排序在[n]上产生有序集分区。在这种对应关系下，我们看到每个最大的面对应于一个大小为1的块的划分(即完全排列)，见图1。此外，当且仅当对应于F的有序集分区使对应于G的有序集分区变粗时，面F包含在面G中；面格与置换面体的面格是对偶的。
图1. Coxeter复合体的正面和背面
组合数学中几何方法的主要内容之一是将一个单项式解释为空间中的一个整数点。标准构造是以换位变量中的一个单项式视为点(a1，a2，hellip;an)isin;Zeta;n。为了在非交换变量中发展准对称函数，我们需要一个不同的构造。设{x1，x2，hellip;}是非交换变量的集合。对于每一个aisin;Nu;n，将单项式xa1hellip;xan缩写为Chi;a。例如，x2x1x3对应于(2，1，3)isin;Zeta;3。向量a的条目由单项式的指数给出，这是明确定义的，因为我们正在使用非通勤变量，因此系数xi以固定的顺序出现。这样，我们就可以关联到每一组格点，Asub;Nu;n，一个单项式N(A)=sum;aisin;Axa的正式总和N(A)。解决给定调度问题的所有调度的集合，因此对应于生成函数
SS函数具有特殊的结构。给定aisin;Nn，设∆(a)为有序集分区(∆1|∆2|hellip;|∆l)，使a在每个集∆i上都是相同的，并且对于所有1le;ile;l，满足a∆ilt;a|∆i 1。将a的阶类定义为向量b的集合，使∆(b)=∆(a)。例如，对于a=(3，2，2，3，1)，∆(a)=5|23|14，a的阶类由所有向量xisin;Nu;5组成，使得x5lt;x2=x3lt;x1=x4。相反，有序集划分Phi;指定坐标的相对顺序，并包含辫状排列的圆锥体C(Phi;)={xisin;|∆(x)=Phi;}的相对内部的所有点。对于矩阵V，圆锥体C(Phi;)的形式为C(Phi;)=V，其列称为发生器，其条目在{0，1}中。锥体C(Phi;)是单纯形的；其发生器是线性独立的。此外，它们是单模的，这意味着它们的基本平行六面体V(0，1]l只包含一个整数向量。至关重要的是，如果两个向量a和b具有相同的阶类，那么s(a) hArr;s(b)，也就是说，锥C(Phi;)中的所有格点都能解出s，或者它们都不能求解。
图2.Mu;Phi;与C(Phi;)的对应关系
在前一种情况下，我们称为Phi;解出S，因此，可满足调度问题的解是这些锥的并集的整数点，它们对应于Coxeter复数的开放面并集。这种几何现象与代数相似。
定义2.1. 非交换变量中的一个函数称为准对称(NCQSym的一个元素)，如果forall;gamma;，tau;isin;Nu;n使得gamma;和tau;处于同一个阶类(∆(gamma;)=∆(tau;))，那么xgamma;1xgamma;2hellip;xgamma;n的系数与xtau;1xtau;2hellip;xtau;n的系数相同。我们简称这些函数为准对称函数。
用有序集配分Phi;表示的单项式nc-准对称函数Mu;Phi;是
例如，考虑整数点的顺序类，使第一个和第三个坐标相等且小于第二个和第四个同样相等的坐标。对应的有序集分区Phi;为(13|24)，且
单项式函数Mu;Phi;与锥C(Phi;)中的点阵点集精确对应，见图2，通过函数N，
非交换变量中的准对称函数可以表示为单项式Mu;Phi;的和。因此，我们可以把一项基中非负系数的任意nc-准对称函数F看作一组锥，其中C(Phi;)中的点阵点的重数由F中的Mu;Phi;系数给出。
定义2.3. 给定n个项目的调度问题S，是一个nc-准对称函数，调度nc-准对称函数的S
这些观测结果对调度计数函数chi;s也有直接影响。一般来说，一个nc-准对称函数对应一个k-调度，其中k被取为无穷大，即没有最后期限。设定最后期限或限制到k时隙，对应于设置第一个k变量x1、x2、hellip;，xk等于1，其余为零，即Ss(1k)=chi;s(k)。对于一个单项式的术语，我们有
其中l(Phi;)等于分区的长度，即块数。因此，从定义2.3可以看出，chi;s是此类二项式系数的线性组合。
从多面体几何的角度来看，将1k替换为Mu;Phi;相当于使圆锥体C(Phi;)与半开立方体(0，k]n相交。如图2所示，交叉点C(Phi;)cap;(0，k]n是半开单纯形。由于C(Phi;)cap;(0，k]n=k·(C(Phi;)cap;(0，1]n)，它可以看作半开单模单纯形的k次扩张，这在chi;s和ehrhart理论之间提供了有趣的联系。
对于任何有界集X sub;Rn，X的ehrhart函数ehrchi;: Zeta;gt;0→Zeta;ge;0计数X整数展开中的整数点数，即ehrchi;(k)= #(Zeta;ncap;k· X)。如果X是顶点坐标为整数的多面体，那么ehrchi;(k)是一个多项式，称为chi;的ehrhart多项式。当Rn的仿射自同构phi;与phi;(p)=q存在时，Rn中的两个集合P,Q是格等价的，它在整数格Zeta;n上产生一个双射。格子等价集具有相同的ehrhart函数。格子等价集具有相同的
ehrhart函数。我们特别感兴趣的是具有Ehrhart多项式的开面维数n的半开标准单纯形。
（1）
如果Phi;有l部分，那么单纯形C(Phi;)cap;(0，1]n等于半开标准单纯形的格。单纯形
资料编号：[3228]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
