Recent ucdavismath_graduate items

Hierarchical graph Laplacian eigen transforms

Thu, 13 Jun 2019 00:00:00 +0000

Hierarchical graph Laplacian eigen transforms

Nearly Finitary Matroids

Thu, 13 Jun 2019 00:00:00 +0000

In this thesis, we study nearly finitary matroids by introducing new definitions and prove various properties of nearly finitary matroids. In 2010, an axiom system for infinite matroids was proposed by Bruhn et al. We use this axiom system for this thesis. In Chapter 2, we summarize our main results after reviewing historical background and motivation. In Chapter 3, we define a notion of spectrum for matroids. Moreover, we show that the spectrum of a nearly finitary matroid can be larger than any fixed finite size. We also give an example of a matroid with infinitely large spectrum that is not nearly finitary. Assuming the existence of a single matroid that is nearly finitary but not k -nearly finitary, we construct classes of matroids that are nearly finitary but not k -nearly finitary. We also show that finite rank matroids are unionable. In Chapter 4, we will introduce a notion of near finitarization. We also give an...

Crystal structure on rigged configurations and the filling map

Mon, 14 May 2018 00:00:00 +0000

© 2015, Australian National University. All rights reserved. In this paper, we extend work of the first author on a crystal structure on rigged con_gurations of simply-laced type to all non-exceptional affine types using the technology of virtual rigged con_gurations and crystals. Under the bijection between rigged configurations and tensor products of Kirillov-Reshetikhin crystals specialized to a single tensor factor, we obtain a new tableaux model for Kirillov-Reshetikhin crystals. This is related to the model in terms of Kashiwara-Nakashima tableaux via a filling map, generalizing the recently discovered filling map in typeD(1)n

Short rational functions for toric algebra and applications

Mon, 14 May 2018 00:00:00 +0000

We encode the binomials belonging to the toric ideal IAassociated with an integral d×n matrix A using a short sum of rational functions as introduced by Barvinok (Math. Operations Research 19 (1994) 769) and Barvinok and Woods (J. Amer. Math. Soc. 16 (2003) 957). Under the assumption that d and n are fixed, this representation allows us to compute a universal Gröbner basis and the reduced Gröbner basis of the ideal IA, 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 computations 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 applications to enumerative combinatorics, integer programming, and statistics. © 2004 Elsevier Ltd. All rights reserved.

Weak orientability of matroids and polynomial equations

Mon, 14 May 2018 00:00:00 +0000

© 2015 Elsevier Ltd. This paper studies systems of polynomial equations that provide information about orientability of matroids.First, we study systems of linear equations over F2, originally alluded to by Bland and Jensen in their seminal paper on weak orientability. The Bland-Jensen linear equations for a matroid M have a solution if and only if M is weakly orientable. We use the Bland-Jensen system to determine weak orientability for all matroids on at most nine elements and all matroids between ten and twelve elements having rank three. Our experiments indicate that for small rank, about half the time, when a simple matroid is not orientable, it is already non-weakly orientable, and further this may happen more often as the rank increases. Thus, about half of the small simple non-orientable matroids of rank three are not representable over fields having order congruent to three modulo four. For binary matroids, the Bland-Jensen linear systems provide a practical way to check...

Immersed boundary smooth extension: A high-order method for solving PDE on arbitrary smooth domains using Fourier spectral methods

Mon, 14 May 2018 00:00:00 +0000

© 2015 Elsevier Inc. The Immersed Boundary method is a simple, efficient, and robust numerical scheme for solving PDE in general domains, yet it only achieves first-order spatial accuracy near embedded boundaries. In this paper, we introduce a new high-order numerical method which we call the Immersed Boundary Smooth Extension (IBSE) method. The IBSE method achieves high-order accuracy by smoothly extending the unknown solution of the PDE from a given smooth domain to a larger computational domain, enabling the use of simple Cartesian-grid discretizations (e.g. Fourier spectral methods). The method preserves much of the flexibility and robustness of the original IB method. In particular, it requires minimal geometric information to describe the boundary and relies only on convolution with regularized delta-functions to communicate information between the computational grid and the boundary. We present a fast algorithm for solving elliptic equations, which forms the basis for simple,...

Software for exact integration of polynomials over polyhedra

Mon, 14 May 2018 00:00:00 +0000

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 by some of the authors. We provide a new software implementation and 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. © 2012 Elsevier B.V.

The visual boundary of Z^2

Thu, 22 Feb 2018 00:00:00 +0000

We introduce ideas from geometric group theory related to boundaries of groups. This is a mostly expository paper. We consider the visual boundary of a free abelian group, and show that it is an uncountable set with the trivial topology.

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case

Thu, 22 Feb 2018 00:00:00 +0000

We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We also present an extreme function that is a piecewise linear function with some irrational breakpoints, whose extremality follows from a new principle.

Structure and Interpretation of Dual-Feasible Functions

Thu, 22 Feb 2018 00:00:00 +0000

We study two techniques to obtain new families of classical and general Dual-Feasible Functions: A conversion from minimal Gomory--Johnson functions; and computer-based search using polyhedral computation and an automatic maximality and extremality test.

On tunnel number one knots that are not (1,n)

Thu, 22 Feb 2018 00:00:00 +0000

We show that the bridge number of a $t$ bridge knot in $S^3$ with respect to an unknotted genus $t$ surface is bounded below by a function of the distance of the Heegaard splitting induced by the $t$ bridges. It follows that for any natural number $n$, there is a tunnel number one knot in $S^3$ that is not $(1,n)$.

Finite volume methods for incompressible flow

Thu, 22 Feb 2018 00:00:00 +0000

Two finite volume methods are derived and applied to the solution of problems of incompressible flow. In particular, external inviscid flows and boundary-layer flows are examined. The firstmethod analyzed is a cell-centered finite volume scheme. It is shown to be formally first order accurate on equilateral triangles and used to calculate inviscid flow over an airfoil. The second method is a vertex-centered least-squares method and is second order accurate. It's quality is investigated for several types of inviscid flow problems and to solve Prandtl's boundary-layer equations over a flat plate. Future improvements and extensions of the method are discussed.

Set maps, umbral calculus, and the chromatic polynomial

Thu, 22 Feb 2018 00:00:00 +0000

Some important properties of the chromatic polynomial also hold for any polynomial set map satisfying p_S(x+y)=\sum_{T\uplus U=S}p_T(x)p_U(y). Using umbral calculus, we give a formula for the expansion of such a set map in terms of any polynomial sequence of binomial type. This leads to some new expansions of the chromatic polynomial. We also describe a set map generalization of Abel polynomials.

Solving deterministic and stochastic equilibrium problems via augmented Walrasian

Thu, 22 Feb 2018 00:00:00 +0000

We described a method to solve deterministic and stochastic Walras equilibrium models based on associating with the given problem a bifunction whose maxinf-points turn out to be equilibrium points. The numerical procedure relies on an augmentation of this bifunction. Convergence of the proposed procedure is proved by relying on the relevant lopsided convergence. In the dynamic versions of our models, deterministic and stochastic, we are mostly concerned with models that equip the agents with a mechanism to transfer goods from one time period to the next, possibly simply savings, but also allows for the transformation of goods via production

Unique Perfect Phylogeny Characterizations via Uniquely Representable Chordal Graphs

Thu, 22 Feb 2018 00:00:00 +0000

The perfect phylogeny problem is a classic problem in computational biology, where we seek an unrooted phylogeny that is compatible with a set of qualitative characters. Such a tree exists precisely when an intersection graph associated with the character set, called the partition intersection graph, can be triangulated using a restricted set of fill edges. Semple and Steel used the partition intersection graph to characterize when a character set has a unique perfect phylogeny. Bordewich, Huber, and Semple showed how to use the partition intersection graph to find a maximum compatible set of characters. In this paper, we build on these results, characterizing when a unique perfect phylogeny exists for a subset of partial characters. Our characterization is stated in terms of minimal triangulations of the partition intersection graph that are uniquely representable, also known as ur-chordal...

Splitting pairs and the number of clusters generated by random pair incompatibilities

Thu, 22 Feb 2018 00:00:00 +0000

We consider a random fitness landscape on the space of haploid diallelic genotypes with n genetic loci, where each genotype is considered either inviable or viable depending on whether or not there are any incompatibilities among its allele pairs. We suppose that each allele pair in the set of all possible allele pairs on the n loci is independently incompatible with probability p=c/(2n). We examine the connectivity of the viable genotypes under single locus mutations and show that, for 01, there are no viable genotypes with probability converging to one. The genotype space is equivalent to the n-dimensional hypercube and the viable genotypes are solutions to a random 2-SAT problem, so the same result holds for the connectivity of solutions in the hypercube to a random 2-SAT problem.

On Finite Rank Deformations of Wigner Matrices

Thu, 22 Feb 2018 00:00:00 +0000

We study the distribution of the outliers in the spectrum of finite rank deformations of Wigner random matrice under the assumption that the off-diagonal matrix entries have uniformly bounded fifth moment and the diagonal entries have uniformly bounded third moment. Using our recent results on the fluctuation of resolvent entries [31],[28], and ideas from [9], we extend results by M.Capitaine, C.Donati-Martin, and D.F\'eral [12], [13].

Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit

Thu, 22 Feb 2018 00:00:00 +0000

We demonstrate a simple greedy algorithm that can reliably recover a d-dimensional vector v from incomplete and inaccurate measurements x. Here our measurement matrix is an N by d matrix with N much smaller than d. Our algorithm, Regularized Orthogonal Matching Pursuit (ROMP), seeks to close the gap between two major approaches to sparse recovery. It combines the speed and ease of implementation of the greedy methods with the strong guarantees of the convex programming methods. For any measurement matrix that satisfies a Uniform Uncertainty Principle, ROMP recovers a signal with O(n) nonzeros from its inaccurate measurements x in at most n iterations, where each iteration amounts to solving a Least Squares Problem. The noise level of the recovery is proportional to the norm of the error, up to a log factor. In particular, if the error vanishes the reconstruction is exact. This stability result...

Promotion operator on rigged configurations of type A

Thu, 22 Feb 2018 00:00:00 +0000

Recently, the analogue of the promotion operator on crystals of type A under a generalization of the bijection of Kerov, Kirillov and Reshetikhin between crystals (or Littlewood--Richardson tableaux) and rigged configurations was proposed. In this paper, we give a proof of this conjecture. This shows in particular that the bijection between tensor products of type A_n^{(1)} crystals and (unrestricted) rigged configurations is an affine crystal isomorphism.

Crystal analysis of type C Stanley symmetric functions

Wed, 21 Feb 2018 00:00:00 +0000

Combining results of T.K. Lam and J. Stembridge, the type C Stanley symmetric function FCw(x), indexed by an element w in the type C Coxeter group, has a nonnegative integer expansion in terms of Schur functions. We provide a crystal theoretic explanation of this fact and give an explicit combinatorial description of the coefficients in the Schur expansion in terms of highest weight crystal elements.

Transition Probabilities of the Bethe Ansatz Solvable Interacting Particle Systems

Wed, 21 Feb 2018 00:00:00 +0000

This paper presents the exact expressions of the transition probabilities of some non-determinantal Bethe ansatz solvable interacting particle systems: the two-sided PushASEP, the asymmetric avalanche process and the asymmetric zero range process. The time integrated currents of the asymmetric avalanche process and the asymmetric zero range process are immediate from the results of the asymmtric simple exclusion process.

Infinite Order Differential Operators in Spaces of Entire Functions

Wed, 21 Feb 2018 00:00:00 +0000

We study infinite order differential operators acting in the spaces of exponential type entire functions. We derive conditions under which such operators preserve the set of Laguerre entire functions which consists of the polynomials possessing real nonpositive zeros only and of their uniform limits on compact subsets of the complex plane. We obtain integral representations of some particular cases of these operators and apply these results to obtain explicit solutions to some Cauchy problems for diffusion equations with nonconstant drift term.

The Triangle Closure is a Polyhedron

Wed, 21 Feb 2018 00:00:00 +0000

Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel [ An analysis of mixed integer linear sets based on lattice point free convex sets, Math. Oper. Res. 35 (2010), 233--256] and Averkov [On finitely generated closures in the theory of cutting planes, Discrete Optimization 9 (2012), no. 4, 209--215], some basic questions have remained unresolved. For example, maximal lattice-free triangles are the natural family to study beyond...

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

Wed, 21 Feb 2018 00:00:00 +0000

We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory--Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand's two-sided discontinuous extreme functions and Basu--Hildebrand--K\"{o}ppe's piecewise linear extreme function with irrational breakpoints. The new function only admits piecewise microperiodic perturbations. We present an algorithm for computations with a restricted class of such perturbations.

Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

Wed, 21 Feb 2018 00:00:00 +0000

Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert's Nullstellensatz certificates for polynomial systems arising in combinatorics and on large-scale linear-algebra computations over K. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph problem instances having thousands of nodes and tens of thousands of edges.

A convexity theorem for real projective structures

Wed, 21 Feb 2018 00:00:00 +0000

Given a finite collection P of convex n-polytopes in RP^n (n>1), we consider a real projective manifold M which is obtained by gluing together the polytopes in P along their facets in such a way that the union of any two adjacent polytopes sharing a common facet is convex. We prove that the real projective structure on M is (1) convex if P contains no triangular polytope, and (2) properly convex if, in addition, P contains a polytope whose dual polytope is thick. Triangular polytopes and polytopes with thick duals are defined as analogues of triangles and polygons with at least five edges, respectively.

Infinite Excess Entropy Processes with Countable-State Generators

Wed, 21 Feb 2018 00:00:00 +0000

We present two examples of finite-alphabet, infinite excess entropy processes generated by invariant hidden Markov models (HMMs) with countable state sets. The first, simpler example is not ergodic, but the second is. It appears these are the first constructions of processes of this type. Previous examples of infinite excess entropy processes over finite alphabets admit only invariant HMM presentations with uncountable state sets.

Berline-Vergne valuation and generalized permutohedra