On Gittins’ index theorem in continuous time

We give a new and comparably short proof of Gittins’ index theorem for dynamic allocation problems of the multi-armed bandit type in continuous time under minimal assumptions. This proof gives a complete characterization of optimal allocation strategies as those policies which follow the current leader among the Gittins indices while ensuring that a Gittins index is at an all-time low whenever the associated project is not worked on exclusively. The main tool is a representation property of Gittins index processes which allows us to show that these processes can be chosen to be pathwise lower semi-continuous from the right and quasi-lower semi-continuous from the left. Both regularity properties turn out to be crucial for our characterization and the construction of optimal allocation policies.     

Chromatic polynomial, q-binomial counting and colored Jones function

We define a q-chromatic function and q-dichromate on graphs and compare it with existing graph functions. Then we study in more detail the class of general chordal graphs. This is partly motivated by the graph isomorphism problem. Finally we relate the q-chromatic function to the colored Jones function of knots. This leads to a curious expression of the colored Jones function of a knot diagram K as a chromatic operator applied to a power series whose coefficients are linear combinations of long chord diagrams. Chromatic operators are directly related to weight systems by the work of Chmutov, Duzhin, Lando and Noble, Welsh.     

The problem of Dirichlet for anisotropic quasilinear degenerate elliptic equations

We consider the Dirichlet problem for a class of anisotropic degenerate elliptic equations. New a priori estimates for solutions and for the gradient of solutions are established. Based on these estimates sufficient conditions guaranteeing the solvability of the problem are formulated. The results are new even in the semilinear case when the principal part is the Laplace operator.     

Measures on minimally generated Boolean algebras

We investigate properties of minimally generated Boolean algebras. It is shown that all measures defined on such algebras are separable but not necessarily weakly uniformly regular. On the other hand, there exist Boolean algebras small in terms of measures which are not minimally generated. We prove that under CH a measure on a retractive Boolean algebra can be nonseparable. Some relevant examples are indicated. Also, we give two examples of spaces satisfying some kind of Efimov property.     

Complex magnetism in ultra-thin films: atomic-scale spin structures and resolution by the spin-polarized scanning tunneling microscope

In this paper we present a density functional theory investigation of complex magnetic structures in ultra-thin films. The focus is on magnetically frustrated antiferromagnetic Cr and Mn monolayers deposited on a triangular lattice provided by a Ag (111) substrate. This involves non-collinear magnetic structures, which we treat by first-principles calculations on the basis of the vector spin-density formulation of the density functional theory. We find for Cr/Ag (111) a coplanar non-collinear periodic 120° Néel structure, for Mn/Ag (111) a row-wise antiferromagnetic structure, and for Fe/Ag (111) a ferromagnetic structure as magnetic ground states. The spin-polarized scanning tunneling microscope (SP–STM) operated in the constant-current mode is proposed as a powerful tool to investigate complex atomic-scale magnetic structures of otherwise chemically equivalent atoms. We discuss a recent application of this operation mode of the SP–STM on Mn/W (110), which led to the first observation of a two-dimensional antiferromagnet on a non-magnetic metal. The future potential of this approach is demonstrated by calculating SP–STM images for different magnetic structures of Cr/Ag (111). The results show that the predicted non-collinear magnetic ground state structure can clearly be discriminated from competing magnetic structures. A general discussion of the application of different operation modes of the SP–STM is presented on the basis of the model of Tersoff and Hamann. Received: 07 May 2001 / Accepted: 23 July 2001 / Published online: 3 April 2002     

The treatment of nonhomogeneous Dirichlet boundary conditions by thep-version of the finite element method

Summary The paper addresses the problem of the implementation of nonhomogeneous essential Dirichlet type boundary conditions in thep-version of the finite element method.Partially supported by the Office of Naval Research under Grant N-00014-85-K-0169Research partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 85-0322     

Über die abstandsverträglichen Abbildungen auf dem Kreis und auf der reellen Geraden

Zusammenfassung. Eine Abbildung zwischen metrischen R?umen hei?t abstandsvertr?glich, wenn der Abstand der Bilder zweier Punkte nur vom Abstand der Punkte selbst abh?ngt. Wir zeigen, dass eine Abbildung genau dann abstandsvertr?glich ist, wenn der Cauchyschen Funktionalgleichung genügt, also ein Endomorphismus der Gruppe ist. Ein entsprechendes Resultat gilt auch für die abstandsvertr?glichen Abbildungen des Kreises (mit der Multiplikation komplexer Zahlen als Gruppenverknüpfung). Damit kann man sowohl alle messbaren abstandsvertr?glichen Abbildungen von bzw. in sich angeben, als auch einen Nachweis für die Existenz nichtmessbarer abstandsvertr?glicher Abbildungen auf und erbringen. Eingegangen am 20. Juni 2001 / Angenommen am 13. September 2001     

A nondifferentiable extension of a theorem of Pucci and Serrin and applications

We study the multiplicity of critical points for functionals which are only differentiable along some directions. We extend to this class of functionals the three critical point theorem of Pucci and Serrin and we apply it to a one-parameter family of functionals Jλ, λ∈I⊂R. Under suitable assumptions, we locate an open subinterval of values λ in I for which Jλ possesses at least three critical points. Applications to quasilinear boundary value problems are also given.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.