Skip to main content
Open Access Publications from the University of California

Department of Mathematics

Undergraduate bannerUC Davis

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case


We present software for investigations with cut-generating functions in the Gomory--Johnson model and extensions, implemented in the computer algebra system SageMath.

Software for cut-generating functions in the Gomory--Johnson model and beyond


We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath.

A Basis for Slicing Birkhoff Polytopes


We present a change of basis that may allow more efficient calculation of the volumes of Birkhoff polytopes using a slicing method. We construct the basis from a special set of square matrices. We explain how to construct this basis easily for any Birkhoff polytope, and give examples of its use. We also discuss possible directions for future work.

Lifschitz Tails for Random Schr\"{o}dinger Operator in Bernoulli Distributed Potentials


This paper presents an elementary proof of Lifschitz tail behavior for random discrete Schr\"{o}dinger operators with a Bernoulli-distributed potential. The proof approximates the low eigenvalues by eigenvalues of sine waves supported where the potential takes its lower value. This is motivated by the idea that the eigenvectors associated to the low eigenvalues react to the jump in the values of the potential as if the gap were infinite.

A bound for orderings of Reidemeister moves


We provide an upper bound on the number of ordered Reidemeister moves required to pass between two diagrams of the same link. This bound is in terms of the number of unordered Reidemeister moves required.

Software for Exact Integration of Polynomials over Polyhedra


We are interested in the fast computation of the exact value of integrals of polynomial functions over convex polyhedra. We present speed ups and extensions of the algorithms presented in previous work. We present the new software implementation and provide benchmark computations. The computation of integrals of polynomials over polyhedral regions has many applications; here we demonstrate our algorithmic tools solving a challenge from combinatorial voting theory.

On Volumes of Permutation Polytopes


This paper focuses on determining the volumes of permutation polytopes associated to cyclic groups, dihedral groups, groups of automorphisms of tree graphs, and Frobenius groups. We do this through the use of triangulations and the calculation of Ehrhart polynomials. We also present results on the theta body hierarchy of various permutation polytopes.

The Kontsevich constants for the volume of the moduli of curves and topological recursion


We give an Eynard-Orantin type topological recursion formula for the canonical Euclidean volume of the combinatorial moduli space of pointed smooth algebraic curves. The recursion comes from the edge removal operation on the space of ribbon graphs. As an application we obtain a new proof of the Kontsevich constants for the ratio of the Euclidean and the symplectic volumes of the moduli space of curves.

Short Rational Functions for Toric Algebra and Applications


We encode the binomials belonging to the toric ideal $I_A$ associated with an integral $d \times n$ matrix $A$ using a short sum of rational functions as introduced by Barvinok \cite{bar,newbar}. Under the assumption that $d,n$ are fixed, this representation allows us to compute the Graver basis and the reduced Gr\"obner basis of the ideal $I_A$, with respect to any term order, in time polynomial in the size of the input. We also derive a polynomial time algorithm for normal form computation which replaces in this new encoding the usual reductions typical of the division algorithm. We describe other applications, such as the computation of Hilbert series of normal semigroup rings, and we indicate further connections to integer programming and statistics.

Non-commutative matrix integrals and representation varieties of surface groups in a finite group


A graphical expansion formula for non-commutative matrix integrals with values in a finite-dimensional real or complex von Neumann algebra is obtained in terms of ribbon graphs and their non-orientable counterpart called Moebius graphs. The contribution of each graph is an invariant of the topological type of the surface on which the graph is drawn. As an example, we calculate the integral on the group algebra of a finite group. We show that the integral is a generating function of the number of homomorphisms from the fundamental group of an arbitrary closed surface into the finite group. The graphical expansion formula yields a new proof of the classical theorems of Frobenius, Schur and Mednykh on these numbers.