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.     

On the pivot structure for the weighing matrix W(12,11)

In the present article we concentrate our study on the growth problem for the weighing matrix W(12,11) and show that the unique W(12,11) has three pivot structures. An improved algorithm for extending a k × k (0,+,-) matrix to a W(n,n-1), if possible, has been developed to simplify the proof. For the implementation of the algorithm special emphasis is given to the notions of data structures and parallel processing.     

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.     

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     

Packing Non-Zero A-Paths In Group-Labelled Graphs

Let G=(V,E) be an oriented graph whose edges are labelled by the elements of a group Γ and let A⊂V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Γ is not abelian, we sum the labels in their order along the path.) We are interested in the maximum number of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. The general case also includes Mader's S-paths problem. We prove that for any positive integer k, either there are k vertex-disjoint A-paths each of non-zero weight, or there is a set of at most 2k −2 vertices that meets each of the non-zero A-paths. This result is obtained as a consequence of an exact min-max theorem. These results were obtained at a workshop on Structural Graph Theory at the PIMS Institute in Vancouver, Canada. This research was partially conducted during the period the first author served as a Clay Mathematics Institute Long-Term Prize Fellow.     

Ü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.     

Large Discrepancy In Homogenous Quasi-Arithmetic Progressions

We prove that the class of homogeneous quasi-arithmetic progressions has unbounded discrepancy. That is, we show that given any 2-coloring of the natural numbers and any positive integer D, one can find a real number α≥1 and a set of natural numbers of the form {0, [α], [2α], [3α], . . . , [kα]} so that one color appears at least D times more than the other color. This was already proved by Beck in 1983, but the proof given here is somewhat simpler and gives a better bound on the discrepancy.