Riemann-Roch Theory for Graph Orientations
Riemann-Roch Theory for Graph Orientations
复制标题
图方向的黎曼-罗赫理论
DOI：
10.1016/j.aim.2017.01.005
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Spencer Backman
中科院分区：
文献类型：
--
作者：
Spencer Backman
我们开发了一个新的框架，调查线性等价的因子图使用的推广Gioan的循环上循环反转系统的部分方向。介绍了达尔燃烧算法的一个有向版本，并将其应用于部分有向无环性的研究.然后，我们表明，贝克-诺林秩的部分定向因子是一个小于最小数量的有向路径需要被逆转的广义循环-上循环反转系统，以产生一个无环的部分方向。这些结果被应用于图的Riemann-Roch定理以及Luo的秩决定集的拓扑刻画中。我们证明了最大流最小割定理等价于可定向因子的欧拉特征描述，并将这一特征描述推广到部分定向的情形。此外，我们证明了P i c g− 1（G）作为P i c 0（G）-torsor与有向路径反转作用下的圈-上圈反转系统中的全定向的等价类正则同构。提出了计算断裂因子和构造部分方向的有效算法。
We develop a new framework for investigating linear equivalence of divisors on graphs using a generalization of Gioan's cycle–cocycle reversal system for partial orientations. An oriented version of Dhar's burning algorithm is introduced and employed in the study of acyclicity for partial orientations. We then show that the Baker–Norine rank of a partially orientable divisor is one less than the minimum number of directed paths which need to be reversed in the generalized cycle–cocycle reversal system to produce an acyclic partial orientation. These results are applied in providing new proofs of the Riemann–Roch theorem for graphs as well as Luo's topological characterization of rank-determining sets. We prove that the max-flow min-cut theorem is equivalent to the Euler characteristic description of orientable divisors and extend this characterization to the setting of partial orientations. Furthermore, we demonstrate that P i c g− 1 (G) is canonically isomorphic as a P i c 0 (G)-torsor to the equivalence classes of full orientations in the cycle–cocycle reversal system acted on by directed path reversals. Efficient algorithms for computing break divisors and constructing partial orientations are presented.