http://www.rssboard.org/rssspecification
720
Recent ucdavismath_graduate items
https://escholarship.org/uc/ucdavismath_graduate/rss
Recent eScholarship items from Graduate
Thu, 1 Dec 2022 00:58:24 +0000

Hierarchical graph Laplacian eigen transforms
https://escholarship.org/uc/item/5j79p8ng
Hierarchical graph Laplacian eigen transforms
https://escholarship.org/uc/item/5j79p8ng
Thu, 13 Jun 2019 00:00:00 +0000

Nearly Finitary Matroids
https://escholarship.org/uc/item/03t3s201
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 <em>
<strong>k</strong>
</em>nearly finitary, we construct classes of matroids that are nearly finitary but not <em>
<strong>k</strong>
</em>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...
https://escholarship.org/uc/item/03t3s201
Thu, 13 Jun 2019 00:00:00 +0000

Crystal structure on rigged configurations and the filling map
https://escholarship.org/uc/item/86v883p8
© 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 simplylaced type to all nonexceptional affine types using the technology of virtual rigged con_gurations and crystals. Under the bijection between rigged configurations and tensor products of KirillovReshetikhin crystals specialized to a single tensor factor, we obtain a new tableaux model for KirillovReshetikhin crystals. This is related to the model in terms of KashiwaraNakashima tableaux via a filling map, generalizing the recently discovered filling map in typeD(1)n
https://escholarship.org/uc/item/86v883p8
Mon, 14 May 2018 00:00:00 +0000

Short rational functions for toric algebra and applications
https://escholarship.org/uc/item/5d18n90g
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.
https://escholarship.org/uc/item/5d18n90g
Mon, 14 May 2018 00:00:00 +0000

Weak orientability of matroids and polynomial equations
https://escholarship.org/uc/item/4827g1tw
© 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 BlandJensen linear equations for a matroid M have a solution if and only if M is weakly orientable. We use the BlandJensen 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 nonweakly orientable, and further this may happen more often as the rank increases. Thus, about half of the small simple nonorientable matroids of rank three are not representable over fields having order congruent to three modulo four. For binary matroids, the BlandJensen linear systems provide a practical way to check...
https://escholarship.org/uc/item/4827g1tw
Mon, 14 May 2018 00:00:00 +0000

Immersed boundary smooth extension: A highorder method for solving PDE on arbitrary smooth domains using Fourier spectral methods
https://escholarship.org/uc/item/27n8r19q
© 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 firstorder spatial accuracy near embedded boundaries. In this paper, we introduce a new highorder numerical method which we call the Immersed Boundary Smooth Extension (IBSE) method. The IBSE method achieves highorder 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 Cartesiangrid 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 deltafunctions 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,...
https://escholarship.org/uc/item/27n8r19q
Mon, 14 May 2018 00:00:00 +0000

Software for exact integration of polynomials over polyhedra
https://escholarship.org/uc/item/13r6m7sb
We are interested in the fast computation of the exact value of integrals of polynomial functions over convex polyhedra. We present speedups 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.
https://escholarship.org/uc/item/13r6m7sb
Mon, 14 May 2018 00:00:00 +0000

The visual boundary of Z^2
https://escholarship.org/uc/item/9zb2b11r
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.
https://escholarship.org/uc/item/9zb2b11r
Thu, 22 Feb 2018 00:00:00 +0000

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The
OneDimensional Case
https://escholarship.org/uc/item/9xq8n2b2
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.
https://escholarship.org/uc/item/9xq8n2b2
Thu, 22 Feb 2018 00:00:00 +0000

Structure and Interpretation of DualFeasible Functions
https://escholarship.org/uc/item/9wc9g4ss
We study two techniques to obtain new families of classical and general DualFeasible Functions: A conversion from minimal GomoryJohnson functions; and computerbased search using polyhedral computation and an automatic maximality and extremality test.
https://escholarship.org/uc/item/9wc9g4ss
Thu, 22 Feb 2018 00:00:00 +0000

On tunnel number one knots that are not (1,n)
https://escholarship.org/uc/item/9vm8m75s
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)$.
https://escholarship.org/uc/item/9vm8m75s
Thu, 22 Feb 2018 00:00:00 +0000

Finite volume methods for incompressible flow
https://escholarship.org/uc/item/9vj0f7g9
Two finite volume methods are derived and applied to the solution of problems of
incompressible flow. In particular, external inviscid flows and boundarylayer flows are
examined. The firstmethod analyzed is a cellcentered 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 vertexcentered leastsquares method and is
second order accurate. It's quality is investigated for several types of inviscid flow
problems and to solve Prandtl's boundarylayer equations over a flat plate. Future
improvements and extensions of the method are discussed.
https://escholarship.org/uc/item/9vj0f7g9
Thu, 22 Feb 2018 00:00:00 +0000

Set maps, umbral calculus, and the chromatic polynomial
https://escholarship.org/uc/item/9v34f836
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.
https://escholarship.org/uc/item/9v34f836
Thu, 22 Feb 2018 00:00:00 +0000

Solving deterministic and stochastic equilibrium problems via augmented
Walrasian
https://escholarship.org/uc/item/9tj4571t
We described a method to solve deterministic and stochastic Walras equilibrium
models based on associating with the given problem a bifunction whose maxinfpoints 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
https://escholarship.org/uc/item/9tj4571t
Thu, 22 Feb 2018 00:00:00 +0000

Unique Perfect Phylogeny Characterizations via Uniquely Representable Chordal
Graphs
https://escholarship.org/uc/item/9sz001dw
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 urchordal...
https://escholarship.org/uc/item/9sz001dw
Thu, 22 Feb 2018 00:00:00 +0000

Splitting pairs and the number of clusters generated by random pair
incompatibilities
https://escholarship.org/uc/item/9r30r8mn
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 ndimensional hypercube and the
viable genotypes are solutions to a random 2SAT problem, so the same result holds for the
connectivity of solutions in the hypercube to a random 2SAT problem.
https://escholarship.org/uc/item/9r30r8mn
Thu, 22 Feb 2018 00:00:00 +0000

On Finite Rank Deformations of Wigner Matrices
https://escholarship.org/uc/item/9r22z621
We study the distribution of the outliers in the spectrum of finite rank
deformations of Wigner random matrice under the assumption that the offdiagonal 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.DonatiMartin, and D.F\'eral [12],
[13].
https://escholarship.org/uc/item/9r22z621
Thu, 22 Feb 2018 00:00:00 +0000

Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal
Matching Pursuit
https://escholarship.org/uc/item/9q66r6g5
We demonstrate a simple greedy algorithm that can reliably recover a ddimensional
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...
https://escholarship.org/uc/item/9q66r6g5
Thu, 22 Feb 2018 00:00:00 +0000

Promotion operator on rigged configurations of type A
https://escholarship.org/uc/item/9pr105j0
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
LittlewoodRichardson 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.
https://escholarship.org/uc/item/9pr105j0
Thu, 22 Feb 2018 00:00:00 +0000

Crystal analysis of type C Stanley symmetric functions
https://escholarship.org/uc/item/9nk8q79r
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.
https://escholarship.org/uc/item/9nk8q79r
Wed, 21 Feb 2018 00:00:00 +0000

Transition Probabilities of the Bethe Ansatz Solvable Interacting Particle
Systems
https://escholarship.org/uc/item/9n89x56z
This paper presents the exact expressions of the transition probabilities of some
nondeterminantal Bethe ansatz solvable interacting particle systems: the twosided
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.
https://escholarship.org/uc/item/9n89x56z
Wed, 21 Feb 2018 00:00:00 +0000

Infinite Order Differential Operators in Spaces of Entire Functions
https://escholarship.org/uc/item/9mp6s0r2
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.
https://escholarship.org/uc/item/9mp6s0r2
Wed, 21 Feb 2018 00:00:00 +0000

The Triangle Closure is a Polyhedron
https://escholarship.org/uc/item/9mp2x7jm
Recently, cutting planes derived from maximal latticefree 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
latticefree 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), 233256] and Averkov [On finitely generated closures in the theory
of cutting planes, Discrete Optimization 9 (2012), no. 4, 209215], some basic questions
have remained unresolved. For example, maximal latticefree triangles are the natural
family to study beyond...
https://escholarship.org/uc/item/9mp2x7jm
Wed, 21 Feb 2018 00:00:00 +0000

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The
Curious Case of TwoSided Discontinuous Functions
https://escholarship.org/uc/item/9mg813wn
We construct a twosided discontinuous piecewise linear minimal valid function for
the 1row GomoryJohnson 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 twosided discontinuous extreme functions and
BasuHildebrandK\"{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.
https://escholarship.org/uc/item/9mg813wn
Wed, 21 Feb 2018 00:00:00 +0000

Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial
Infeasibility
https://escholarship.org/uc/item/9g5835pj
Systems of polynomial equations over an algebraicallyclosed field K can be used to
concisely model many combinatorial problems. In this way, a combinatorial problem is
feasible (e.g., a graph is 3colorable, 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
largescale linearalgebra computations over K. We report on experiments based on the
problem of proving the non3colorability of graphs. We successfully solved graph problem
instances having thousands of nodes and tens of thousands of edges.
https://escholarship.org/uc/item/9g5835pj
Wed, 21 Feb 2018 00:00:00 +0000

A convexity theorem for real projective structures
https://escholarship.org/uc/item/9b9659hz
Given a finite collection P of convex npolytopes 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.
https://escholarship.org/uc/item/9b9659hz
Wed, 21 Feb 2018 00:00:00 +0000

Infinite Excess Entropy Processes with CountableState Generators
https://escholarship.org/uc/item/99v835nt
We present two examples of finitealphabet, 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.
https://escholarship.org/uc/item/99v835nt
Wed, 21 Feb 2018 00:00:00 +0000

BerlineVergne valuation and generalized permutohedra
https://escholarship.org/uc/item/98w5p3f0
Generalizing a conjecture by De Loera et al., we conjecture that all the integral
generalized permutohedra have positive Ehrhart coefficients. BerlineVergne constructe a
valuation that assign values to faces of polytopes, which provides a way to write Ehrhart
coefficients of a polytope as positive sums of these values. Based on empirical results, we
conjecture BerlineVergne's valuation is always positive on regular permutohedra, which
implies our first conjecture. This article proves that our conjecture on BerlineVergne's
valuation is true for dimension up to $6$, and is true if we restrict to faces of
codimension up to $3.$ We also give two equivalent statements to this conjecture in terms
of mixed valuations and Todd class, respectively. In addition to investigating the
positivity conjectures, we study the BerlineVergne's valuation, and show that it is the
unique construction for McMullen's...
https://escholarship.org/uc/item/98w5p3f0
Tue, 20 Feb 2018 00:00:00 +0000

Stabilizing Heegaard Splittings of HighDistance Knots
https://escholarship.org/uc/item/98h321z7
Suppose $K$ is a knot in $S^3$ with bridge number $n$ and bridge distance greater
than $2n$. We show that there are at most ${2n\choose n}$ distinct minimal genus Heegaard
splittings of $S^3\setminus\eta(K)$. These splittings can be divided into two families. Two
splittings from the same family become equivalent after at most one stabilization. If $K$
has bridge distance at least $4n$, then two splittings from different families become
equivalent only after $n1$ stabilizations. Further, we construct representatives of the
isotopy classes of the minimal tunnel systems for $K$ corresponding to these Heegaard
surfaces.
https://escholarship.org/uc/item/98h321z7
Tue, 20 Feb 2018 00:00:00 +0000

Emergence of a Giant Component in Random Site Subgraphs of a dDimensional Hamming
Torus
https://escholarship.org/uc/item/9870g7tk
The ddimensional Hamming torus is the graph whose vertices are all of the integer
points inside an a_1 n X a_2 n X ... X a_d n box in R^d (for constants a_1, ..., a_d >
0), and whose edges connect all vertices within Hamming distance one. We study the size of
the largest connected component of the subgraph generated by independently removing each
vertex of the Hamming torus with probability 1p. We show that if p=\lambda / n, then there
exists \lambda_c > 0, which is the positive root of a degree d polynomial whose
coefficients depend on a_1, ..., a_d, such that for \lambda < \lambda_c the largest
component has O(log n) vertices (a.a.s. as n \to \infty), and for \lambda > \lambda_c
the largest component has (1q) \lambda (\prod_i a_i) n^{d1} + o(n^{d1}) vertices and the
second largest component has O(log n) vertices (a.a.s.). An implicit formula for q < 1
is also given....
https://escholarship.org/uc/item/9870g7tk
Tue, 20 Feb 2018 00:00:00 +0000

LiebRobinson bounds for classical anharmonic lattice systems
https://escholarship.org/uc/item/95j36227
We prove locality estimates, in the form of LiebRobinson bounds, for classical
oscillator systems defined on a lattice. Our results hold for the harmonic system and a
variety of anharmonic perturbations with long range interactions. The anharmonic estimates
are applicable to a special class of observables, the Weyl functions, and the bounds which
follow are not only independent of the volume but also the initial condition.
https://escholarship.org/uc/item/95j36227
Tue, 20 Feb 2018 00:00:00 +0000

Equivalence of History and Generator EpsilonMachines
https://escholarship.org/uc/item/9592981w
Epsilonmachines are minimal, unifilar presentations of stationary stochastic
processes. They were originally defined in the history machine sense, as hidden Markov
models whose states are the equivalence classes of infinite pasts with the same probability
distribution over futures. In analyzing synchronization, though, an alternative generator
definition was given: unifilar, edgeemitting hidden Markov models with probabilistically
distinct states. The key difference is that history epsilonmachines are defined by a
process, whereas generator epsilonmachines define a process. We show here that these two
definitions are equivalent in the finitestate case.
https://escholarship.org/uc/item/9592981w
Tue, 20 Feb 2018 00:00:00 +0000

Mismatch and resolution in compressive imaging
https://escholarship.org/uc/item/92g3m5q3
Highly coherent sensing matrices arise in discretization of continuum problems such
as radar and medical imaging when the grid spacing is below the Rayleigh threshold as well
as in using highly coherent, redundant dictionaries as sparsifying operators. Algorithms
(BOMP, BLOOMP) based on techniques of band exclusion and local optimization are proposed to
enhance Orthogonal Matching Pursuit (OMP) and deal with such coherent sensing matrices.
BOMP and BLOOMP have provably performance guarantee of reconstructing sparse, widely
separated objects {\em independent} of the redundancy and have a sparsity constraint and
computational cost similar to OMP's. Numerical study demonstrates the effectiveness of
BLOOMP for compressed sensing with highly coherent, redundant sensing matrices.
https://escholarship.org/uc/item/92g3m5q3
Tue, 20 Feb 2018 00:00:00 +0000

Spaces of invariant circular orders of groups
https://escholarship.org/uc/item/9083t020
Motivated by well known results in lowdimensional topology, we introduce and study
a topology on the set CO(G) of all leftinvariant circular orders on a fixed countable and
discrete group G. CO(G) contains as a closed subspace LO(G), the space of all
leftinvariant linear orders of G, as first topologized by Sikora. We use the compactness
of these spaces to show the sets of nonlinearly and noncircularly orderable finitely
presented groups are recursively enumerable. We describe the action of Aut(G) on CO(G) and
relate it to results of Koberda regarding the action on LO(G). We then study two families
of circularly orderable groups: finitely generated abelian groups, and free products of
circularly orderable groups. For finitely generated abelian groups A, we use a
classification of elements of CO(A) to describe the homeomorphism type of the space CO(A),
and to show that Aut(A) acts faithfully...
https://escholarship.org/uc/item/9083t020
Tue, 20 Feb 2018 00:00:00 +0000

Vertices of GelfandTsetlin Polytopes
https://escholarship.org/uc/item/8zw344px
This paper is a study of the polyhedral geometry of GelfandTsetlin patterns
arising in the representation theory $\mathfrak{gl}_n \C$ and algebraic combinatorics. We
present a combinatorial characterization of the vertices and a method to calculate the
dimension of the lowestdimensional face containing a given GelfandTsetlin pattern. As an
application, we disprove a conjecture of Berenstein and Kirillov about the integrality of
all vertices of the GelfandTsetlin polytopes. We can construct for each $n\geq5$ a
counterexample, with arbitrarily increasing denominators as $n$ grows, of a nonintegral
vertex. This is the first infinite family of nonintegral polyhedra for which the Ehrhart
counting function is still a polynomial. We also derive a bound on the denominators for the
nonintegral vertices when $n$ is fixed.
https://escholarship.org/uc/item/8zw344px
Tue, 20 Feb 2018 00:00:00 +0000

Multistage Portfolio Optimization: A Duality Result in Conic Market Models
https://escholarship.org/uc/item/8sw162gd
We prove a general duality result for multistage portfolio optimization problems
in markets with proportional transaction costs. The financial market is described by
Kabanov's model of foreign exchange markets over a finite probability space and
finitehorizon discrete time steps. This framework allows us to compare vectorvalued
portfolios under a partial ordering, so that our model does not require liquidation into
some numeraire at terminal time. We embed the vectorvalued portfolio problem into the
setoptimization framework, and generate a problem dual to portfolio optimization. Using
recent results in the development of set optimization, we then show that a strong duality
relationship holds between the problems.
https://escholarship.org/uc/item/8sw162gd
Tue, 20 Feb 2018 00:00:00 +0000

Learning in A Changing World: Restless MultiArmed Bandit with Unknown Dynamics
https://escholarship.org/uc/item/8sp185jn
We consider the restless multiarmed bandit (RMAB) problem with unknown dynamics in
which a player chooses M out of N arms to play at each time. The reward state of each arm
transits according to an unknown Markovian rule when it is played and evolves according to
an arbitrary unknown random process when it is passive. The performance of an arm selection
policy is measured by regret, defined as the reward loss with respect to the case where the
player knows which M arms are the most rewarding and always plays the M best arms. We
construct a policy with an interleaving exploration and exploitation epoch structure that
achieves a regret with logarithmic order when arbitrary (but nontrivial) bounds on certain
system parameters are known. When no knowledge about the system is available, we show that
the proposed policy achieves a regret arbitrarily close to the logarithmic order. We
further extend...
https://escholarship.org/uc/item/8sp185jn
Tue, 20 Feb 2018 00:00:00 +0000

Stochastic spatial models of plant diseases
https://escholarship.org/uc/item/8sm5g95m
I present three models of plantpathogen interactions. The models are stochastic
and spatially explicit at the scale of individual plants. For each model, I use a version
of pair approximation or moment closure along with a separation of timescales argument to
determine the effects of spatial clustering on threshold structure. By computing the
spatial structure early in an invasion, I find explicit corrections to mean field theory.
In the first chapter, I present a lattice model of a disease that is not directly lethal to
its host, but affects its ability to compete with neighbors. I use a type of pair
approximation to determine conditions for invasions and coexistence. In the second chapter,
I study a basic SIR epidemic point process in continuous space. I implement a
multiplicative moment closure scheme to compute the threshold transmission rate as a
function of spatial parameters. In...
https://escholarship.org/uc/item/8sm5g95m
Tue, 20 Feb 2018 00:00:00 +0000

Exact Synchronization for FiniteState Sources
https://escholarship.org/uc/item/8s29m87k
We analyze how an observer synchronizes to the internal state of a finitestate
information source, using the epsilonmachine causal representation. Here, we treat the
case of exact synchronization, when it is possible for the observer to synchronize
completely after a finite number of observations. The more difficult case of strictly
asymptotic synchronization is treated in a sequel. In both cases, we find that an observer,
on average, will synchronize to the source state exponentially fast and that, as a result,
the average accuracy in an observer's predictions of the source output approaches its
optimal level exponentially fast as well. Additionally, we show here how to analytically
calculate the synchronization rate for exact epsilonmachines and provide an efficient
polynomialtime algorithm to test epsilonmachines for exactness.
https://escholarship.org/uc/item/8s29m87k
Tue, 20 Feb 2018 00:00:00 +0000

Relaxation Time of Quantized Toral Maps
https://escholarship.org/uc/item/8mq972rn
We introduce the notion of the relaxation time for noisy quantum maps on the
2ddimensional torus  a generalization of previously studied dissipation time. We show
that relaxation time is sensitive to the chaotic behavior of the corresponding classical
system if one simultaneously considers the semiclassical limit ($\hbar$ > 0) together
with the limit of small noise strength ($\ep$ > 0). Focusing on quantized smooth Anosov
maps, we exhibit a semiclassical regime $\hbar<\ep^{E}$ << 1 (where E>1) in
which classical and quantum relaxation times share the same asymptotics: in this regime, a
quantized Anosov map relaxes to equilibrium fast, as the classical map does. As an
intermediate result, we obtain rigorous estimates of the quantumclassical correspondence
for noisy maps on the torus, up to times logarithmic in $\hbar^{1}$. On the other hand, we
show that in the ``quantum...
https://escholarship.org/uc/item/8mq972rn
Tue, 20 Feb 2018 00:00:00 +0000

Spherical metrics with conical singularities on 2spheres
https://escholarship.org/uc/item/8jf4153p
Suppose that θ1,θ2,…,θn are positive numbers and n≥3. Does there exist a sphere with a spherical metric with n conical singularities of angles 2πθ1,2πθ2,…,2πθn? A sufficient condition was obtained by Gabriele Mondello and Dmitri Panov (arXiv:1505.01994 https://arxiv.org/abs/1505.01994). We show that it is also necessary when we assume that θ1,θ2,…,θn∉N.
https://escholarship.org/uc/item/8jf4153p
Tue, 20 Feb 2018 00:00:00 +0000

A Sampling KaczmarzMotzkin Algorithm for Linear Feasibility
https://escholarship.org/uc/item/8j88k9xw
We combine two iterative algorithms for solving largescale systems of linear
inequalities, the relaxation method of Agmon, Motzkin et al. and the randomized Kaczmarz
method. In doing so, we obtain a family of algorithms that generalize and extend both
techniques. We prove several convergence results, and our computational experiments show
our algorithms often outperform the original methods.
https://escholarship.org/uc/item/8j88k9xw
Tue, 20 Feb 2018 00:00:00 +0000

New fermionic formula for unrestricted Kostka polynomials
https://escholarship.org/uc/item/8hs2z21x
A new fermionic formula for the unrestricted Kostka polynomials of type
$A_{n1}^{(1)}$ is presented. This formula is different from the one given by Hatayama et
al. and is valid for all crystal paths based on KirillovReshetihkin modules, not just for
the symmetric and antisymmetric case. The fermionic formula can be interpreted in terms of
a new set of unrestricted rigged configurations. For the proof a statistics preserving
bijection from this new set of unrestricted rigged configurations to the set of
unrestricted crystal paths is given which generalizes a bijection of Kirillov and
Reshetikhin.
https://escholarship.org/uc/item/8hs2z21x
Tue, 20 Feb 2018 00:00:00 +0000

Dissipation time and decay of correlations
https://escholarship.org/uc/item/8hk3v3f3
We consider the effect of noise on the dynamics generated by volumepreserving maps
on a ddimensional torus. The quantity we use to measure the irreversibility of the
dynamics is the dissipation time. We focus on the asymptotic behaviour of this time in the
limit of small noise. We derive universal lower and upper bounds for the dissipation time
in terms of various properties of the map and its associated propagators: spectral
properties, local expansivity, and global mixing properties. We show that the dissipation
is slow for a general class of nonweaklymixing maps; on the opposite, it is fast for a
large class of exponentially mixing systems which include uniformly expanding maps and
Anosov diffeomorphisms.
https://escholarship.org/uc/item/8hk3v3f3
Tue, 20 Feb 2018 00:00:00 +0000

Localization of Matrix Factorizations
https://escholarship.org/uc/item/8dr1j931
Matrices with offdiagonal decay appear in a variety of fields in mathematics and
in numerous applications, such as signal processing, statistics, communications
engineering, condensed matter physics, and quantum chemistry. Numerical algorithms dealing
with such matrices often take advantage (implicitly or explicitly) of the empirical
observation that this offdiagonal decay property seems to be preserved when computing
various useful matrix factorizations, such as the Cholesky factorization or the
QRfactorization. There is a fairly extensive theory describing when the inverse of a
matrix inherits the localization properties of the original matrix. Yet, except for the
special case of band matrices, surprisingly very little theory exists that would establish
similar results for matrix factorizations. We will derive a comprehensive framework to
rigorously answer the question when and under...
https://escholarship.org/uc/item/8dr1j931
Tue, 20 Feb 2018 00:00:00 +0000

Fluctuations of Matrix Entries of Regular Functions of Sample Covariance Random
Matrices
https://escholarship.org/uc/item/8cn7b3w4
We extend the results about the fluctuations of the matrix entries of regular
functions of Wigner matrices to the case of sample covariance random matrices.
https://escholarship.org/uc/item/8cn7b3w4
Tue, 20 Feb 2018 00:00:00 +0000

Topological KTheory of Complex Projective Spaces
https://escholarship.org/uc/item/8cc4g5nb
We compute the Ktheory of complex projective spaces. There are three major
ingredients: the exact sequence of Kgroups, the theory of Chern character and the Bott
Periodicity Theorem.
https://escholarship.org/uc/item/8cc4g5nb
Tue, 20 Feb 2018 00:00:00 +0000

Crystal structure on rigged configurations and the filling map
https://escholarship.org/uc/item/89r7g1mk
In this paper, we extend work of the first author on a crystal structure on rigged
configurations of simplylaced type to all nonexceptional affine types using the
technology of virtual rigged configurations and crystals. Under the bijection between
rigged configurations and tensor products of KirillovReshetikhin crystals specialized to a
single tensor factor, we obtain a new tableaux model for KirillovReshetikhin crystals.
This is related to the model in terms of KashiwaraNakashima tableaux via a filling map,
generalizing the recently discovered filling map in type $D_n^{(1)}$.
https://escholarship.org/uc/item/89r7g1mk
Tue, 20 Feb 2018 00:00:00 +0000

ESD of singular values of random band matrices; MarchenkoPastur law and more
https://escholarship.org/uc/item/88k8x1fd
We consider the limiting spectral distribution of matrices of the form
$\frac{1}{2b_{n}+1} (R + X)(R + X)^{*}$, where $X$ is an $n\times n$ band matrix of
bandwidth $b_{n}$ and $R$ is a non random band matrix of bandwidth $b_{n}$. We show that
the Stieltjes transform of spectrum of such matrices converges to the Stieltjes transform
of a nonrandom measure. And the limiting Stieltjes transform satisfies an integral
equation. For $R=0$, the integral equation yields the Stieltjes transform of the
MarchenkoPastur law
https://escholarship.org/uc/item/88k8x1fd
Tue, 20 Feb 2018 00:00:00 +0000

Embeddings of rightangled Artin groups
https://escholarship.org/uc/item/86b969hb
We explicitly construct an embedding of a rightangled Artin group into a classical
pure braid group. Using this we obtain a number of corollaries describing embeddings of
arbitrary Artin groups into rightangled Artin groups and linearly independent subgroups of
a rightangled Artin group.
https://escholarship.org/uc/item/86b969hb
Tue, 20 Feb 2018 00:00:00 +0000

Heegaard splittings and the pants complex
https://escholarship.org/uc/item/85h6g948
We define integral measures of complexity for Heegaard splittings based on the
graph dual to the curve complex and on the pants complex defined by Hatcher and Thurston.
As the Heegaard splitting is stabilized, the sequence of complexities turns out to converge
to a nontrivial limit depending only on the manifold. We then use a similar method to
compare different manifolds, defining a distance which converges under stabilization to an
integer related to Dehn surgeries between the two manifolds.
https://escholarship.org/uc/item/85h6g948
Tue, 20 Feb 2018 00:00:00 +0000

Greedy Signal Recovery Review
https://escholarship.org/uc/item/84p917vx
The two major approaches to sparse recovery are L1minimization and greedy methods.
Recently, Needell and Vershynin developed Regularized Orthogonal Matching Pursuit (ROMP)
that has bridged the gap between these two approaches. ROMP is the first stable greedy
algorithm providing uniform guarantees. Even more recently, Needell and Tropp developed the
stable greedy algorithm Compressive Sampling Matching Pursuit (CoSaMP). CoSaMP provides
uniform guarantees and improves upon the stability bounds and RIC requirements of ROMP.
CoSaMP offers rigorous bounds on computational cost and storage. In many cases, the running
time is just O(NlogN), where N is the ambient dimension of the signal. This review
summarizes these major advances.
https://escholarship.org/uc/item/84p917vx
Tue, 20 Feb 2018 00:00:00 +0000

Higher Spin Gravitational Couplings and the YangMills Detour Complex
https://escholarship.org/uc/item/80x8j43k
Gravitational interactions of higher spin fields are generically plagued by
inconsistencies. We present a simple framework that couples higher spins to a broad class
of gravitational backgrounds (including Ricci flat and Einstein) consistently at the
classical level. The model is the simplest example of a YangMills detour complex, which
recently has been applied in the mathematical setting of conformal geometry. An analysis of
asymptotic scattering states about the trivial field theory vacuum in the simplest version
of the theory yields a rich spectrum marred by negative norm excitations. The result is a
theory of a physical massless graviton, scalar field, and massive vector along with a
degenerate pair of zero norm photon excitations. Coherent states of the unstable sector of
the model do have positive norms, but their evolution is no longer unitary and their
amplitudes grow with time....
https://escholarship.org/uc/item/80x8j43k
Tue, 20 Feb 2018 00:00:00 +0000

Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching
Pursuit
https://escholarship.org/uc/item/80v451k6
This paper seeks to bridge the two major algorithmic approaches to sparse signal
recovery from an incomplete set of linear measurements  L_1minimization methods and
iterative methods (Matching Pursuits). We find a simple regularized version of the
Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and
transparency of OMP and the strong uniform guarantees of the L_1minimization. Our
algorithm ROMP reconstructs a sparse signal in a number of iterations linear in the
sparsity (in practice even logarithmic), and the reconstruction is exact provided the
linear measurements satisfy the Uniform Uncertainty Principle.
https://escholarship.org/uc/item/80v451k6
Tue, 20 Feb 2018 00:00:00 +0000

Promotion and evacuation on standard Young tableaux of rectangle and staircase
shape
https://escholarship.org/uc/item/80s1c0zm
(Dual)promotion and (dual)evacuation are bijections on SYT(\lambda) for any
partition \lambda. Let c^r denote the rectangular partition (c,...,c) of height r, and let
sc_k (k > 2) denote the staircase partition (k,k1,...,1). B. Rhoades showed
representationtheoretically that promotion on SYT(c^r) exhibits the cyclic sieving
phenomenon (CSP). In this paper, we demonstrate a promotion and evacuationpreserving
embedding of SYT(sc_k) into SYT(k^{k+1}). This arose from an attempt to demonstrate the CSP
of promotion action on SYT(sc_k).
https://escholarship.org/uc/item/80s1c0zm
Tue, 20 Feb 2018 00:00:00 +0000

A continuum approximation for the excitations of the (1,1,...,1) interface in the
quantum Heisenberg model
https://escholarship.org/uc/item/7z16q91t
It is shown that, with an appropriate scaling, the energy of lowlying excitations
of the (1,1,...,1) interface in the $d$dimensional quantum Heisenberg model are given by
the spectrum of the $d1$dimensional Laplacian on an suitable domain.
https://escholarship.org/uc/item/7z16q91t
Tue, 20 Feb 2018 00:00:00 +0000

A (k+1)Slope Theorem for the kDimensional Infinite Group Relaxation
https://escholarship.org/uc/item/7w32w7j6
We prove that any minimal valid function for the kdimensional infinite group
relaxation that is piecewise linear with at most k+1 slopes and does not factor through a
linear map with nontrivial kernel is extreme. This generalizes a theorem of Gomory and
Johnson for k=1, and Cornuejols and Molinaro for k=2.
https://escholarship.org/uc/item/7w32w7j6
Tue, 20 Feb 2018 00:00:00 +0000

A Generalization of Lifting Nonproper Tropical Intersections
https://escholarship.org/uc/item/7vf2d3mh
Let X and X' be closed subschemes of an algebraic torus T over a nonarchimedean
field. We prove the rational equivalence as tropical cycles, in the sense of Henning
Meyer's graduate thesis, between the tropicalization of the intersection product of X and
X' and the stable intersection of trop(X) and trop(X'), when restricted to (the inverse
image under the tropicalization map of) a connected component C of the intersection of
trop(X) and trop(X'). This requires possibly passing to a (partial) compactification of T
with respect to a suitable fan. We define the compactified stable intersection in a toric
tropical variety, and check that this definition is compatible with the intersection
product in loc.cit.. As a result we get a numerical equivalence (after a compactification
and restricting to C) between the intersection product of X and X' and the stable
intersection of trop(X) and trop(X')...
https://escholarship.org/uc/item/7vf2d3mh
Tue, 20 Feb 2018 00:00:00 +0000

Kstable equivalence for knots in Heegaard surfaces
https://escholarship.org/uc/item/7sv2m7xn
Let K be a knot embedded in a Heegaard surface S for a closed orientable 3manifold
M. We define Kstable equivalence between pairs (S, K) and (S', K) in M, and we prove that
any two pairs are Kstably equivalent in M if they have the same surface slope.
https://escholarship.org/uc/item/7sv2m7xn
Tue, 20 Feb 2018 00:00:00 +0000

Droplet States in the XXZ Heisenberg Chain
https://escholarship.org/uc/item/7sp7178d
We consider the ground states of the ferromagnetic XXZ chain with spin up boundary
conditions in sectors with a fixed number of down spins. This forces the existence of a
droplet of down spins in the system. We find the exact energy and the states that describe
these droplets in the limit of an infinite number of down spins. We prove that there is a
gap in the spectrum above the droplet states. As the XXZ Hamiltonian has a gap above the
fully magnetized ground states as well, this means that the droplet states (for
sufficiently large droplets) form an isolated band. The width of this band tends to zero in
the limit of infinitely large droplets. We also prove the analogous results for finite
chains with periodic boundary conditions and for the infinite chain.
https://escholarship.org/uc/item/7sp7178d
Tue, 20 Feb 2018 00:00:00 +0000

Isolated Eigenvalues of the Ferromagnetic SpinJ XXZ Chain with Kink Boundary
Conditions
https://escholarship.org/uc/item/7qj0v04m
We investigate the lowlying excited states of the spin J ferromagnetic XXZ chain
with Ising anisotropy Delta and kink boundary conditions. Since the third component of the
total magnetization, M, is conserved, it is meaningful to study the spectrum for each fixed
value of M. We prove that for J>= 3/2 the lowest excited eigenvalues are separated by a
gap from the rest of the spectrum, uniformly in the length of the chain. In the
thermodynamic limit, this means that there are a positive number of excitations above the
ground state and below the essential spectrum.
https://escholarship.org/uc/item/7qj0v04m
Tue, 20 Feb 2018 00:00:00 +0000

Finitevolume excitations of the 111 interface in the quantum XXZ model
https://escholarship.org/uc/item/7kv7q58k
We show that the ground states of the threedimensional XXZ Heisenberg ferromagnet
with a 111 interface have excitations localized in a subvolume of linear size R with
energies bounded by O(1/R^2). As part of the proof we show the equivalence of ensembles for
the 111 interface states in the following sense: In the thermodynamic limit the states with
fixed magnetization yield the same expectation values for gauge invariant local observables
as a suitable grand canonical state with fluctuating magnetization. Here, gauge invariant
means commuting with the total third component of the spin, which is a conserved quantity
of the Hamiltonian. As a corollary of equivalence of ensembles we also prove the
convergence of the thermodynamic limit of sequences of canonical states (i.e., with fixed
magnetization).
https://escholarship.org/uc/item/7kv7q58k
Tue, 20 Feb 2018 00:00:00 +0000

Circular thin position for knots in the 3sphere
https://escholarship.org/uc/item/7k47w185
A regular circlevalued Morse function on the knot complement C(K) = S^3\K is a
function f from C(K) to S^1 which separates critical points and which behaves nicely in a
neighborhood of the knot. Such a function induces a handle decomposition on the knot
exterior E(K) = S^3\N (K), with the property that every regular level surface contains a
Seifert surface for the knot. We rearrange the handles in such a way that the regular
surfaces are as simple as possible. To make this precise the concept of circular width for
E(K) is introduced. When E(K) is endowed with a handle decomposition which realizes the
circular width we will say that the knot K is in circular thin position. We use this to
show that many knots have more than one nonisotopic incompressible Seifert surface. We
also analyze the behavior of the circular width under some knot operations.
https://escholarship.org/uc/item/7k47w185
Tue, 20 Feb 2018 00:00:00 +0000

Fluctuations of Linear Eigenvalue Statistics of Random Band Matrices
https://escholarship.org/uc/item/7hm671sk
In this paper, we study the fluctuation of linear eigenvalue statistics of Random
Band Matrices defined by $M_{n}=\frac{1}{\sqrt{b_{n}}}W_{n}$, where $W_{n}$ is a $n\times
n$ band Hermitian random matrix of bandwidth $b_{n}$, i.e., the diagonal elements and only
first $b_{n}$ off diagonal elements are nonzero. Also variances of the matrix elmements are
upto a order of constant. We study the linear eigenvalue statistics
$\mathcal{N}(\phi)=\sum_{i=1}^{n}\phi(\lambda_{i})$ of such matrices, where $\lambda_{i}$
are the eigenvalues of $M_{n}$ and $\phi$ is a sufficiently smooth function. We prove that
$\sqrt{\frac{b_{n}}{n}}[\mathcal{N}(\phi)\mathbb{E} \mathcal{N}(\phi)]\stackrel{d}{\to}
N(0,V(\phi))$ for $b_{n}>>\sqrt{n}$, where $V(\phi)$ is given in the Theorem 1.
https://escholarship.org/uc/item/7hm671sk
Tue, 20 Feb 2018 00:00:00 +0000

$A_\infty$ Algebras and the Cohomology of Moduli Spaces
https://escholarship.org/uc/item/7h8832gw
We introduce the notion of cyclic cohomology of an Ainfinity algebra and show that
the deformations of an Ainfinity algebra which preserve an invariant inner product are
classified by this cohomology. We use this result to construct some cycles on the moduli
space of algebraic curves. The paper also contains a review of some well known notions and
results about Hochschild and cyclic cohomology of associative algebras, Ainfinity
algebras, and deformation theory of algebras, and includes a discussion of the homology of
the graph complex of metric ribbon graphs which is associated to the moduli space of
Riemann surfaces with marked points.
https://escholarship.org/uc/item/7h8832gw
Tue, 20 Feb 2018 00:00:00 +0000

Lens space surgeries & primitive/Seifert type constructions
https://escholarship.org/uc/item/7gh33913
We show that lens space surgeries on knots in $S^3$ which arise from the
primitive/Seifert type construction also arise from the primitive/primitive construction.
This is the first step of a three step program to prove the Berge conjecture for tunnel
number one knots.
https://escholarship.org/uc/item/7gh33913
Tue, 20 Feb 2018 00:00:00 +0000

The ladder crystal
https://escholarship.org/uc/item/7g54c677
n this paper I introduce a new description of the crystal $B(\Lambda_0)$ of
$\hat{\mathfrak{sl}_\ell}$. As in the MisraMiwa model of $B(\Lambda_0)$, the nodes of this
crystal are indexed by partitions and the $i$arrows correspond to adding a box of residue
$i$. I then show that the two models are equivalent by interpreting the operation of
regularization introduced by James as a crystal isomorphism.
https://escholarship.org/uc/item/7g54c677
Tue, 20 Feb 2018 00:00:00 +0000

Regularity Conditions for Convergence of Linear Statistics of GUE
https://escholarship.org/uc/item/7d37h0xm
We establish a central limit theorem for the unnormalized linear statistic of the
Gaussian Unitary Ensemble under optimal conditions: the linear statistics converges if and
only if the expression for the limiting variance is finite.
https://escholarship.org/uc/item/7d37h0xm
Tue, 20 Feb 2018 00:00:00 +0000

Characterization of ${\cal B}(\infty)$ using marginally large tableaux and rigged
configurations in the $A_n$ case via integer sequences
https://escholarship.org/uc/item/7cz3c19b
Rigged configurations are combinatorial objects prominent in the study of solvable
lattice models. Marginally large tableaux are semistandard Young tableaux of special form
that give a realization of the crystals ${\cal B}(\infty)$. We introduce cascading
sequences to characterize marginally large tableaux. Then we use cascading sequences and a
nonexplicit crystal isomorphism between marginally large tableaux and rigged
configurations to give a characterization of the latter set, and to give an explicit
bijection between the two sets.
https://escholarship.org/uc/item/7cz3c19b
Tue, 20 Feb 2018 00:00:00 +0000

Representable Chow classes of a product of projective spaces
https://escholarship.org/uc/item/7cj2b2hj
Inside a product of projective spaces, we try to understand which Chow classes come
from irreducible subvarieties. The answer is closely related to the theory of integer
polymatroids. The support of a representable class can be (partially) characterized as some
integer point inside a particular polymatroid. If the class is multiplicityfree, we obtain
a complete characterization in terms of representable polymatroids. We also generalize some
of the results to the case of products of Grassmannians.
https://escholarship.org/uc/item/7cj2b2hj
Tue, 20 Feb 2018 00:00:00 +0000

Double bubbles in the 3torus
https://escholarship.org/uc/item/78g0s843
We present a conjecture, based on computational results, on the area minimizing way
to enclose and separate two arbitrary volumes in the flat cubic 3torus. For comparable
small volumes, we prove that an area minimizing double bubble in the 3torus is the
standard double bubble from R^3.
https://escholarship.org/uc/item/78g0s843
Fri, 16 Feb 2018 00:00:00 +0000

Graphical Calculus on Representations of Quantum Lie Algebras
https://escholarship.org/uc/item/7823v4md
We develop graphical calculation methods. JonesWenzl projectors for U_q(sl(2,C))
are very powerful tools to find not only invariants of links but also invariants of
3manifolds. We find single clasp expansions of generalized JonesWenzl projectors for
simple Lie algebras of rank 2. Trihedron coefficients of the representation theory for
U_q(sl(2,C)) has significant meaning and it is called 3j symbols. Using single clasp
expansions for U_q(sl(3,C)), we find some trihedron coefficients of the representation
theory of U_q(sl(3,C)). We study representation theory for U_q(sl(4,C)). We conjecture a
complete set of relations for U_q(sl(4,C)).
https://escholarship.org/uc/item/7823v4md
Fri, 16 Feb 2018 00:00:00 +0000

Gaussian Fluctuations of Eigenvalues in Wigner Random Matrices
https://escholarship.org/uc/item/7817r45t
We study the fluctuations of eigenvalues from a class of Wigner random matrices
that generalize the Gaussian orthogonal ensemble. We begin by considering an $n \times n$
matrix from the Gaussian orthogonal ensemble (GOE) or Gaussian symplectic ensemble (GSE)
and let $x_k$ denote eigenvalue number $k$. Under the condition that both $k$ and $nk$
tend to infinity with $n$, we show that $x_k$ is normally distributed in the limit. We also
consider the joint limit distribution of $m$ eigenvalues from the GOE or GSE with similar
conditions on the indices. The result is an $m$dimensional normal distribution. Using a
recent universality result by Tao and Vu, we extend our results to a class of Wigner real
symmetric matrices with nonGaussian entries that have an exponentially decaying
distribution and whose first four moments match the Gaussian moments.
https://escholarship.org/uc/item/7817r45t
Fri, 16 Feb 2018 00:00:00 +0000

On Fluctuations of Matrix Entries of Regular Functions of Wigner Matrices with
NonIdentically Distributed Entries
https://escholarship.org/uc/item/73r6j9g6
In this note, we extend the results about the fluctuations of the matrix entries of
regular functions of Wigner random matrices obtained in arXiv:1103.3731 [math.PR] to Wigner
matrices with noni.i.d. entries provided certain Lindeberg type conditions for the fourth
moments of the offdiagonal entries and the second moments of the diagonal entries are
satisfied. In addition, we relax our conditions on the test functions and require that for
some $s>3 \ \int (1+k)^{2s}\*\hat{f}(k)^2 \* dk <\infty.$
https://escholarship.org/uc/item/73r6j9g6
Fri, 16 Feb 2018 00:00:00 +0000

Laplacian spectrum for the nilpotent KacMoody Lie algebras
https://escholarship.org/uc/item/72t666dq
We prove that the maximal nilpotent subalgebra of a KacMoody Lie algebra has an
(essentially unique) Euclidean metric with respect to which the Laplace operator in the
chain complex is scalar on each component of a given degree. Moreover, both the Lie algebra
structure and the metric are uniquely determined by this property.
https://escholarship.org/uc/item/72t666dq
Fri, 16 Feb 2018 00:00:00 +0000

A Combinatorial Formula for Orthogonal Idempotents in the $0$Hecke Algebra of the
Symmetric Group
https://escholarship.org/uc/item/71v0t7v4
Building on the work of P.N. Norton, we give combinatorial formulae for two maximal
decompositions of the identity into orthogonal idempotents in the $0$Hecke algebra of the
symmetric group, $\mathbb{C}H_0(S_N)$. This construction is compatible with the branching
from $S_{N1}$ to $S_{N}$.
https://escholarship.org/uc/item/71v0t7v4
Fri, 16 Feb 2018 00:00:00 +0000

On the local structure of doubly laced crystals
https://escholarship.org/uc/item/7097n816
Let $\mathfrak{g}$ be a Lie algebra all of whose regular subalgebras of rank 2 are
type $A_{1}\times A_{1}$, $A_{2}$, or $C_{2}$, and let $B$ be a crystal graph corresponding
to a representation of $\mathfrak{g}$. We explicitly describe the local structure of $B$,
confirming a conjecture of Stembridge.
https://escholarship.org/uc/item/7097n816
Fri, 16 Feb 2018 00:00:00 +0000

Abrams's stable equivalence for graph braid groups
https://escholarship.org/uc/item/6zk7v19t
In his PhD thesis, Abrams proved that, for a natural number n and a graph G with at
least n vertices, the nstrand configuration space of G deformation retracts to a compact
subspace, the discretized nstrand configuration space, provided G satisfies two
conditions: each path between distinct essential vertices (vertices of degree not equal to
2) is of length at least n+1 edges, and each path from a vertex to itself which is not
nullhomotopic is of length at least n+1 edges. Using Forman's discrete Morse theory for
CWcomplexes, we show the first condition can be relaxed to require only that each path
between distinct essential vertices is of length at least n1.
https://escholarship.org/uc/item/6zk7v19t
Fri, 16 Feb 2018 00:00:00 +0000

Bridge Number and the Curve Complex
https://escholarship.org/uc/item/6zc2v86b
We show that there are hyperbolic tunnelnumber one knots with arbitrarily high
bridge number and that "most" tunnelnumber one knots are not onebridge with respect to an
unknotted torus. The proof relies on a connection between bridge number and a certain
distance in the curve complex of a genustwo surface.
https://escholarship.org/uc/item/6zc2v86b
Fri, 16 Feb 2018 00:00:00 +0000

Distribution of a particle's position in the ASEP with the {alternating} initial
condition
https://escholarship.org/uc/item/6z67490w
In this paper we give the distribution of the position of the particle in the
asymmetric simple exclusion process (ASEP) with the alternating initial condition. That is,
we find $\mathbb{P}(X_m(t) \leq x)$ where $X_m(t)$ is the position of the particle at time
$t$ which was at $m =2k1, k \in \mathbb{Z}$ at $t=0.$ As in the ASEP with the step initial
condition, there arises a new combinatorial identity for the alternating initial condition,
and this identity relates the integrand to a determinantal form together with an extra
product.
https://escholarship.org/uc/item/6z67490w
Fri, 16 Feb 2018 00:00:00 +0000

Beyond ChanceConstrained Convex MixedInteger Optimization: A Generalized
CalafioreCampi Algorithm and the notion of $S$optimization
https://escholarship.org/uc/item/6d04k7qj
The scenario approach developed by Calafiore and Campi to attack chanceconstrained
convex programs utilizes random sampling on the uncertainty parameter to substitute the
original problem with a representative continuous convex optimization with $N$ convex
constraints which is a relaxation of the original. Calafiore and Campi provided an explicit
estimate on the size $N$ of the sampling relaxation to yield highlikelihood feasible
solutions of the chanceconstrained problem. They measured the probability of the original
constraints to be violated by the random optimal solution from the relaxation of size $N$.
This paper has two main contributions. First, we present a generalization of the
CalafioreCampi results to both integer and mixedinteger variables. In fact, we
demonstrate that their sampling estimates work naturally for variables restricted to some
subset $S$ of $\mathbb R^d$. The...
https://escholarship.org/uc/item/6d04k7qj
Fri, 16 Feb 2018 00:00:00 +0000

A new Lenstratype Algorithm for Quasiconvex Polynomial Integer Minimization with
Complexity 2^O(n log n)
https://escholarship.org/uc/item/6wc538rm
We study the integer minimization of a quasiconvex polynomial with quasiconvex
polynomial constraints. We propose a new algorithm that is an improvement upon the best
known algorithm due to Heinz (Journal of Complexity, 2005). This improvement is achieved by
applying a new modern Lenstratype algorithm, finding optimal ellipsoid roundings, and
considering sparse encodings of polynomials. For the bounded case, our algorithm attains a
timecomplexity of s (r l M d)^{O(1)} 2^{2n log_2(n) + O(n)} when M is a bound on the
number of monomials in each polynomial and r is the binary encoding length of a bound on
the feasible region. In the general case, s l^{O(1)} d^{O(n)} 2^{2n log_2(n) +O(n)}. In
each we assume d>= 2 is a bound on the total degree of the polynomials and l bounds the
maximum binary encoding size of the input.
https://escholarship.org/uc/item/6wc538rm
Thu, 15 Feb 2018 00:00:00 +0000

On the Computation of ClebschGordan Coefficients and the Dilation Effect
https://escholarship.org/uc/item/6w08r6g7
We investigate the problem of computing tensor product multiplicities for complex
semisimple Lie algebras. Even though computing these numbers is #Phard in general, we show
that if the rank of the Lie algebra is assumed fixed, then there is a polynomial time
algorithm, based on counting the lattice points in polytopes. In fact, for Lie algebras of
type A_r, there is an algorithm, based on the ellipsoid algorithm, to decide when the
coefficients are nonzero in polynomial time for arbitrary rank. Our experiments show that
the lattice point algorithm is superior in practice to the standard techniques for
computing multiplicities when the weights have large entries but small rank. Using an
implementation of this algorithm, we provide experimental evidence for conjectured
generalizations of the saturation property of LittlewoodRichardson coefficients. One of
these conjectures seems to be valid...
https://escholarship.org/uc/item/6w08r6g7
Thu, 15 Feb 2018 00:00:00 +0000

Asymptotics for the Covariance of the Airy_2 process
https://escholarship.org/uc/item/6vm1v3z8
In this paper we compute some of the higher order terms in the larget asymptotic
expansion of the Airy process twopoint function, extending the previous work of Adler and
van Moerbeke and Widom. We prove that it is possible to represent any order asymptotic
approximation as a polynomial and integrals of the HastingsMcLeod Painlev\'e II function
and its first derivative. Further, for up to tenth order we give this asymptotic
approximation as a linear combination of the TracyWidom GUE density function f_2 and its
derivatives. As a corollary to this, the asymptotic covariance is expressed up to tenth
order in terms of the moments of the TracyWidom GUE distribution.
https://escholarship.org/uc/item/6vm1v3z8
Thu, 15 Feb 2018 00:00:00 +0000

Normal Surface Theory in Link Diagrams
https://escholarship.org/uc/item/6p81x03m
This paper has been withdrawn by the author, due to a significant error in section
4.3.1.
https://escholarship.org/uc/item/6p81x03m
Thu, 15 Feb 2018 00:00:00 +0000

A quantum algorithm for the quantum SchurWeyl transform
https://escholarship.org/uc/item/6mz4640v
We construct an efficient quantum algorithm to compute the quantum SchurWeyl
transform for any value of the quantum parameter $q \in [0,\infty]$. Our algorithm is a
$q$deformation of the BaconChuangHarrow algorithm, in the sense that it has the same
structure and is identically equal when $q=1$. When $q=0$, our algorithm is the unitary
realization of the RobinsonSchenstedKnuth (or RSK) algorithm, while when $q=\infty$ it is
the dual RSK algorithm together with phase signs. Thus, we interpret a wellmotivated
quantum algorithm as a generalization of a wellknown classical algorithm.
https://escholarship.org/uc/item/6mz4640v
Thu, 15 Feb 2018 00:00:00 +0000

Universal Structure and Universal PDE for Unitary Ensembles
https://escholarship.org/uc/item/6kj9n2d5
An attempt is made to describe random matrix ensembles with unitary invariance of
measure (UE) in a unified way, using a combination of TracyWidom (TW) and AdlerShiotaVan
Moerbeke (ASvM) approaches to derivation of partial differential equations (PDE) for
spectral gap probabilities. First, general 3term recurrence relations for UE restricted to
subsets of real line, or, in other words, for functions in the resolvent kernel, are
obtained. Using them, simple universal relations between all TW dependent variables and
onedimensional Toda lattice $\tau$functions are found. A universal system of PDE for UE
is derived from previous relations, which leads also to a {\it single independent PDE} for
spectral gap probability of various UE. Thus, orthogonal function bases and Toda lattice
are seen at the core of correspondence of different approaches. Moreover, TodaAKNS system
provides a common...
https://escholarship.org/uc/item/6kj9n2d5
Thu, 15 Feb 2018 00:00:00 +0000

High distance knots in closed 3manifolds
https://escholarship.org/uc/item/6jk256qh
Let M be a closed 3manifold with a given Heegaard splitting. We show that after a
single stabilization, some core of the stabilized splitting has arbitrarily high distance
with respect to the splitting surface. This generalizes a result of Minsky, Moriah, and
Schleimer for knots in S^3. We also show that in the complex of curves, handlebody sets are
either coarsely distinct or identical. We define the coarse mapping class group of a
Heeegaard splitting, and show that if (S, V, W) is a Heegaard splitting of genus greater
than or equal to 2, then the coarse mapping class group of (S,V,W) is isomorphic to the
mapping class group of (S, V,W).
https://escholarship.org/uc/item/6jk256qh
Thu, 15 Feb 2018 00:00:00 +0000

Great circle links in the threesphere
https://escholarship.org/uc/item/6g68z37m
We investigate great circle links in the threesphere, the class of links where
each component is a great circle. Using the geometry of their complements, we classify such
links up to five components. For any twobridge knot complement, there is a finite cover
that is the complement of a link of great circles in $S^3$. We show that for many
twobridge knots, this cover contains a closed incompressible surface. Infinitely many
fillings of the twobridge knot lift to fillings of great circle link where the
incompressibility of this surface is preserved. Using this, we show that infinitely many
fillings of an infinite class of twobridge knot complements are virtually Haken.
https://escholarship.org/uc/item/6g68z37m
Thu, 15 Feb 2018 00:00:00 +0000

A method for computing quadratic Brunovsky forms
https://escholarship.org/uc/item/6bn318vq
In this paper, for continuous, linearlycontrollable quadratic control systems with
a single input, an explicit, constructive method is proposed for studying their Brunovsky
forms, initially studied in [W. Kang and A. J. Krener, Extended quadratic controller normal
form and dynamic state feedback linearization of nonlinear systems, SIAM Journal on Control
and Optimization, 30:13191337, 1992]. In this approach, the computation of Brunovsky forms
and transformation matrices and the proof of their existence and uniqueness are carried out
simultaneously. In addition, it is shown that quadratic transformations in the
aforementioned paper can be simplified to prevent multiplicity in Brunovsky forms. This
method is extended for studying discrete quadratic systems. Finally, computation algorithms
for both continuous and discrete systems are summarized, and examples demonstrated.
https://escholarship.org/uc/item/6bn318vq
Thu, 15 Feb 2018 00:00:00 +0000

An Electronic Compendium of Extreme Functions for the GomoryJohnson Infinite Group
Problem
https://escholarship.org/uc/item/6bh555qm
In this note we announce the availability of an electronic compendium of extreme
functions for GomoryJohnson's infinite group problem. These functions serve as the
strongest cutgenerating functions for integer linear optimization problems. We also close
several gaps in the literature.
https://escholarship.org/uc/item/6bh555qm
Thu, 15 Feb 2018 00:00:00 +0000

No Quantum Brooks' Theorem
https://escholarship.org/uc/item/69p5g5pb
First, I introduce quantum graph theory. I also discuss a known lower bound on the
independence numbers and derive from it an upper bound on the chromatic numbers of quantum
graphs. Then, I construct a family of quantum graphs that can be described as tropical,
cyclical, and commutative. I also define a step logarithm function and express with it the
bounds on quantum graph invariants in closed form. Finally, I obtain an upper bound on the
independence numbers and a lower bound on the chromatic numbers of the constructed quantum
graphs that are similar in form to the existing bounds. I also show that the constructed
family contains graphs of any valence with arbitrarily high chromatic numbers and conclude
by it that quantum graph colorings are quite different from classical graph colorings.
https://escholarship.org/uc/item/69p5g5pb
Thu, 15 Feb 2018 00:00:00 +0000

Low Temperature Results for the Heisenberg XXZ and XY Models
https://escholarship.org/uc/item/67s5d430
This thesis contains two results for the low temperature behavior of quantum spin
systems. First, we present a lower bound for the spin1 XXZ chain in finite volumes in
terms of the gap of the twosite Hamiltonian. The estimate is derived by a method developed
by Nachtergaele in (condmat/9410110) called the Martingale Method. Our bound relies on an
assumption which we have, as yet, been unable to verify analytically in all cases. We
present numerical evidence that strongly indicates our assumption is valid. The second
result is a proof that the spin1/2, ddimensional XY model in the presence of an external
magnetic field does not undergo a phase transition at low temperature, provided that the
strength of the field is great enough. Using a contour expansion inspired by Kennedy, we
show that the weights of contours satisfy a condition of Kotecky and Preiss which allows us
to express the...
https://escholarship.org/uc/item/67s5d430
Thu, 15 Feb 2018 00:00:00 +0000

Product Vacua and Boundary State Models in d Dimensions
https://escholarship.org/uc/item/61d929p0
We introduce and analyze a class of quantum spin models defined on ddimensional
lattices Lambda subset of Z^d, which we call `Product Vacua with Boundary States' (PVBS).
We characterize their ground state spaces on arbitrary finite volumes and study the
thermodynamic limit. Using the martingale method, we prove that the models have a gapped
excitation spectrum on Z^d except for critical values of the parameters. For special values
of the parameters we show that the excitation spectrum is gapless. We demonstrate the
sensitivity of the spectrum to the existence and orientation of boundaries. This
sensitivity can be explained by the presence or absence of edge excitations. In particular,
we study a PVBS models on a slanted halfplane and show that it has gapless edge states but
a gapped excitation spectrum in the bulk.
https://escholarship.org/uc/item/61d929p0
Thu, 15 Feb 2018 00:00:00 +0000

Infinity Algebras and the Homology of Graph Complexes
https://escholarship.org/uc/item/60r9g6kw
An Ainfinity algebra is a generalization of a associative algebra, and an
Linfinity algebra is a generalization of a Lie algebra. In this paper, we show that an
Linfinity algebra with an invariant inner product determines a cycle in the homology of
the complex of metric ordinary graphs. Since the cyclic cohomology of a Lie algebra with an
invariant inner product determines infinitesimal deformations of the Lie algebra into an
Linfinity algebra with an invariant inner product, this construction shows that a cyclic
cocycle of a Lie algebra determines a cycle in the homology of the graph complex. In this
paper a simple proof of the corresponding result for Ainfinity algebras, which was proved
in a different manner in an earlier paper, is given.
https://escholarship.org/uc/item/60r9g6kw
Thu, 15 Feb 2018 00:00:00 +0000

New computerbased search strategies for extreme functions of the GomoryJohnson
infinite group problem
https://escholarship.org/uc/item/60f1k5c1
We describe new computerbased search strategies for extreme functions for the
GomoryJohnson infinite group problem. They lead to the discovery of new extreme
functions, whose existence settles several open questions.
https://escholarship.org/uc/item/60f1k5c1
Thu, 15 Feb 2018 00:00:00 +0000

A LittlewoodRichardson Type Rule for RowStrict Quasisymmetric Schur Functions
https://escholarship.org/uc/item/5zd6p2hv
We give a LittlewoodRichardson type rule for expanding the product of a rowstrict
quasisymmetric Schur function and a symmetric Schur function in terms of rowstrict
quasisymmetric Schur functions. This expansion follows from several new properties of an
insertion algorithm defined by Mason and Remmel (2010) which inserts a positive integer
into a rowstrict composition tableau.
https://escholarship.org/uc/item/5zd6p2hv
Thu, 15 Feb 2018 00:00:00 +0000

Toward computerassisted discovery and automated proofs of cutting plane
theorems
https://escholarship.org/uc/item/5xk4r71z
Using a metaprogramming technique and semialgebraic computations, we provide
computerbased proofs for old and new cuttingplane theorems in GomoryJohnson's model of
cut generating functions.
https://escholarship.org/uc/item/5xk4r71z
Thu, 15 Feb 2018 00:00:00 +0000

Locally unknotted spines of Heegaard splittings
https://escholarship.org/uc/item/5x88p2cs
We show that under reasonable conditions, the spines of the handlebodies of a
strongly irreducible Heegaard splitting will intersect a closed ball in a graph which is
isotopic into the boundary of the ball. This is in some sense a generalization of the
results by Scharlemann on how a strongly irreducible Heegaard splitting surface can
intersect a ball.
https://escholarship.org/uc/item/5x88p2cs
Thu, 15 Feb 2018 00:00:00 +0000

Software for cutgenerating functions in the GomoryJohnson model and beyond
https://escholarship.org/uc/item/5w08g4mg
We present software for investigations with cut generating functions in the
GomoryJohnson model and extensions, implemented in the computer algebra system SageMath.
https://escholarship.org/uc/item/5w08g4mg
Thu, 15 Feb 2018 00:00:00 +0000