A tropical view on Bruhat-Tits buildings and their compactifications

We relate some features of Bruhat-Tits buildings and their compactifications to tropical geometry. If G is a semisimple group over a suitable non-Archimedean field, the stabilizers of points in the Bruhat-Tits building of G and in some of its compactifications are described by tropical linear algebra. The compactifications we consider arise from algebraic representations of G. We show that the fan which is used to compactify an apartment in this theory is given by the weight polytope of the representation and that it is related to the tropicalization of the hypersurface given by the character of the representation.     

A Lower Bound on the Greedy Weights of Product Codes

A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r - 1)-subcode. The r-th greedy weight e _r is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes.     

Recurrence formulas for Macdonald polynomials of type <Emphasis Type="Italic">A</Emphasis>

We consider products of two Macdonald polynomials of type A, indexed by dominant weights which are respectively a multiple of the first fundamental weight and a weight having zero component on the kth fundamental weight. We give the explicit decomposition of any Macdonald polynomial of type A in terms of this basis.     

The Six-Vertex Model at Roots of Unity and some Highest Weight Representations of the sl 2 Loop Algebra

We discuss irreducible highest weight representations of the sl₂ loop algebra and reducible indecomposable ones in association with the sl₂ loop algebra symmetry of the six-vertex model at roots of unity. We formulate an elementary proof that every highest weight representation with distinct evaluation parameters is irreducible. We present a general criteria for a highest weight representation to be irreducible. We also give an example of a reducible indecomposable highest weight representation and discuss its dimensionality. Communicated by Vincent Rivasseau Dedicated to Daniel Arnaudon Submitted: March 3, 2006; Accepted: March 13, 2006     

Bounds on Codes Derived by Counting Components in Varshamov Graphs

We are interested in improving the Varshamov bound for finite values of length n and minimum distance d. We employ a counting lemma to this end which we find particularly useful in relation to Varshamov graphs. Since a Varshamov graph consists of components corresponding to low weight vectors in the cosets of a code it is a useful tool when trying to improve the estimates involved in the Varshamov bound. We consider how the graph can be iteratively constructed and using our observations are able to achieve a reduction in the over-counting which occurs. This tightens the lower bound for any choice of parameters n, k, d or q and is not dependent on information such as the weight distribution of a code. This work is taken from the author’s thesis [10]     

Admission control with advance reservations in simple networks

In the admission control problem we are given a network and a set of connection requests, each of which is associated with a path, a time interval, a bandwidth requirement, and a weight. A feasible schedule is a set of connection requests such that at any given time, the total bandwidth requirement on every link in the network is at most 1. Our goal is to find a feasible schedule with maximum total weight.We consider the admission control problem in two simple topologies: the line and the tree. We present a 12c-approximation algorithm for the line topology, where c is the maximum number of requests on a link at some time instance. This result implies a 12c-approximation algorithm for the rectangle packing problem, where c is the maximum number of rectangles that cover simultaneously a point in the plane. We also present an O(logt)-approximation algorithm for the tree topology, where t is the size of the tree. We consider the loss minimization version of the admission control problem in which the goal is to minimize the weight of unscheduled requests. We present a c-approximation algorithm for loss minimization problem in the tree topology. This result is based on an approximation algorithm for a generalization of set cover, in which each element has a covering requirement, and each set has a covering potential. The approximation ratio of this algorithm is Δ, where Δ is the maximum number of sets that contain the same element.     

Sharp estimates and saturation phenomena for a nonlocal eigenvalue problem

We determine the shape which minimizes, among domains with given measure, the first eigenvalue of a nonlocal operator consisting of a perturbation of the standard Dirichlet Laplacian by an integral of the unknown function. We show that this problem displays a saturation behaviour in that the corresponding value of the minimal eigenvalue increases with the weight affecting the average up to a (finite) critical value of this weight, and then remains constant. This critical point corresponds to a transition between optimal shapes, from one ball as in the Faber–Krahn inequality to two equal balls.     

Half twists and the cohomology of hypersurfaces

A Hodge structure V of weight k on which a CM field acts defines, under certain conditions, a Hodge structure of weight , its half twist. In this paper we consider hypersurfaces in projective space with a cyclic automorphism which defines an action of a cyclotomic field on a Hodge substructure in the cohomology. We determine when the half twist exists and relate it to the geometry and moduli of the hypersurfaces. We use our results to prove the existence of a Kuga-Satake correspondence for certain cubic 4-folds. Received: 25 August 2000; in final form: 8 January 2001 / Published online: 18 January 2002     

An asymptotically exact algorithm for the high-multiplicity bin packing problem

The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C−2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly( log D)), where poly(·) is a polynomial function not depending on C.     

Sobolev spaces on an arbitrary metric space

We define Sobolev space W ^1,p for 1<p on an arbitrary metric space with finite diameter and equipped with finite, positive Borel measure. In the Euclidean case it coincides with standard Sobolev space. Several classical imbedding theorems are special cases of general results which hold in the metric case. We apply our results to weighted Sobolev space with Muckenhoupt weight.This work is supported by KBN grant no. 2 1057 91 01     

Zak Transforms on Binary Fields

We introduce analogues of the Zak Transform on binary fields, and show that they are bounded linear operators on L^p for p=1 and 2. We also show that positivity of Zak transforms can be used to decide whether orthonormal systems generated by multiplying characters of F by a weight function are complete or not.     

Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Given a directed graph G and an edge weight function w : A(G)→ R^ , the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S| -- k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.     

An exact formula for the move-to-front rule for self-organizing lists

A collection of items (e.g., books), each with an associated weight (or popularity), is arranged in a row. At each unit of time an item is removed with probability proportional to its weight and replaced at the left end of the row. Thismove-to-front rule gives a Markov chain on permutations often known as theTsetlin library. We derive an exact and tractable formula for the probability of any permutation after any number of moves. From the formula we read off previously studied quantities of interest associated with the chain, such as the stationary distribution and eigenvalues. Measuring discrepancy from stationarity by separation, we use the formula to find the initial arrangement giving the slowest convergence to stationarity. The time to stationarity in this case is a convolution of geometric random variables which we analyze for three natural choices of weights. We also assess the time required for an important functional, namely, expected search cost, to approach its stationary value.     

Eigenvalues and Spectra of Composition Operators Acting on Weighted Bergman Spaces of Infinite Order on the Unit Polydisk

We give the spectra of bounded composition operators acting on the weighted Bergman spaces of infinite order on the unit polydisk defined for a weight v which is radial in each component, when the symbol of the operator has a fixed point in the unit polydisk.     

Values of <Emphasis Type="Italic">L</Emphasis>-functions at integers outside the critical strip

We incorporate the non-critical values of L-functions of cusp forms into a cohomological set-up analogous to the one of Eichler, Manin and Shimura. We use the 1-cocycles we associate in this way to non-critical values to prove an expression for such values which is similar in structure to Manin’s formula for the critical value of the L-function of a weight 2 cusp form. YoungJu Choie is partially supported by KOSEF R01-2003-00011596-0 and by ITRC Research Fund. N. Diamantis is partially supported by EPSRC grant EP/D032350/1.     

Weights in the cohomology of toric varieties

We describe the weight filtration in the cohomology of toric varieties. We present a role of the Frobenius automorphism in an elementary way. We prove that equivariant intersection homology of an arbitrary toric variety is pure. We obtain results concerning Koszul duality: nonequivariant intersection cohomology is equal to the cohomology of the Koszul complexIH _T ^* (X)⊗H*(T). We also describe the weight filtration inIH ^*(X). Supported by KBN 2P03A 00218 grant. I thank, Institute of Mathematics, Polish Academy of Science for hospitality.     

Degree bounds for type-A weight rings and Gelfand–Tsetlin semigroups

A weight ring in type A is the coordinate ring of the GIT quotient of the variety of flags in ℂ ⁿ modulo a twisted action of the maximal torus in SL(n,ℂ). We show that any weight ring in type A is generated by elements of degree strictly less than the Krull dimension, which is at worst O(n ²). On the other hand, we show that the associated semigroup of Gelfand–Tsetlin patterns can have an essential generator of degree exponential in n.     

Painlevé transcendents and the Hankel determinants generated by a discontinuous Gaussian weight

This paper studies the Hankel determinants generated by a discontinuous Gaussian weight with one and two jumps. It is an extension in a previous study, in which they studied the discontinuous Gaussian weight with a single jump. By using the ladder operator approach, we obtain a series of difference and differential equations to describe the Hankel determinant for the single jump case. These equations include the Chazy II equation, continuous and discrete Painlevé IV. In addition, we consider the large n behavior of the corresponding orthogonal polynomials and prove that they satisfy the biconfluent Heun equation. We also consider the jump at the edge under a double scaling, from which a Painlevé XXXIV appeared. Furthermore, we study the Gaussian weight with two jumps and show that a quantity related to the Hankel determinant satisfies a two variables' generalization of the Jimbo‐Miwa‐Okamoto σ‐form of the Painlevé IV.     

Extremal Bases for the Adjoint Representations of the Simple Lie Algebras

We construct n distinct weight bases, which we call extremal bases, for the adjoint representation of each simple Lie algebra 𝔤 of rank n: One construction for each simple root. We explicitly describe actions of the Chevalley generators on the basis elements. We show that these extremal bases are distinguished by their “supporting graphs” in three ways. (In general, the supporting graph of a weight basis for a representation of a semisimple Lie algebra is a directed graph with colored edges that describe the supports of the actions of the Chevalley generators on the elements of the basis.) We show that each extremal basis constructed is essentially the only basis with its supporting graph (i.e., each extremal basis is solitary), and that each supporting graph is a modular lattice. Each extremal basis is shown to be edge-minimizing: Its supporting graph has the minimum number of edges. The extremal bases are shown to be the only edge-minimizing as well as the only modular lattice weight bases (up to scalar multiples) for the adjoint representation of 𝔤. The supporting graph for an extremal basis is shown to be a distributive lattice if and only if the associated simple root corresponds to an end node for a “branchless” simple Lie algebra, i.e., type A, B, C, F, or G. For each extremal basis, basis elements for the Cartan subalgebra are explicitly expressed in terms of the h _i Chevalley generators.     

Minimum-weight two-connected spanning networks

We consider the problem of constructing a minimum-weight, two-connected network spanning all the points in a setV. We assume a symmetric, nonnegative distance functiond(·) defined onV × V which satisfies the triangle inequality. We obtain a structural characterization of optimal solutions. Specifically, there exists an optimal two-connected solution whose vertices all have degree 2 or 3, and such that the removal of any edge or pair of edges leaves a bridge in the resulting connected components. These are the strongest possible conditions on the structure of an optimal solution since we also show thatany two-connected graph satisfying these conditions is theunique optimal solution for a particular choice of canonical distances satisfying the triangle inequality. We use these properties to show that the weight of an optimal traveling salesman cycle is at most 4/3 times the weight of an optimal two-connected solution; examples are provided which approach this bound arbitrarily closely. In addition, we obtain similar results for the variation of this problem where the network need only span a prespecified subset of the points.