Interval Analysis on Directed Acyclic Graphs for Global Optimization

A directed acyclic graph (DAG) representation of optimization problems represents each variable, each operation, and each constraint in the problem formulation by a node of the DAG, with edges representing the flow of the computation. Using bounds on ranges of intermediate results, represented as weights on the nodes and a suitable mix of forward and backward evaluation, it is possible to give efficient implementations of interval evaluation and automatic differentiation. It is shown how to combine this with constraint propagation techniques to produce narrower interval derivatives and slopes than those provided by using only interval automatic differentiation preceded by constraint propagation. The implementation is based on earlier work by L.V. Kolev, (1997), Reliable Comput., 3, 83–93 on optimal slopes and by C. Bliek, (1992), Computer Methods for Design Automation, PhD Thesis, Department of Ocean Engineering, Massachusetts Institute of Technology on backward slope evaluation. Care is taken to ensure that rounding errors are treated correctly. Interval techniques are presented for computing from the DAG useful redundant constraints, in particular linear underestimators for the objective function, a constraint, or a Lagrangian. The linear underestimators can be found either by slope computations, or by recursive backward underestimation. For sufficiently sparse problems the work is proportional to the number of operations in the calculation of the objective function (resp. the Lagrangian). Mathematics Subject Classification (2000). primary 65G40, secondary 90C26     

Band limited functions on quantum graphs

The notion of band limited functions is introduced on a quantum graph. The main results of the paper are a uniqueness theorem and a reconstruction algorithm of such functions from discrete sets of values. It turns out that some of our band limited functions can have compact supports and their frequencies can be localized on the ``time" side. It opens an opportunity to consider signals of a variable band width and to develop a sampling theory with variable rate of sampling.

     

A property of subgroups of infinite index in a free group

We prove that if is a finitely generated subgroup of infinite index in a free group , then, in a certain statistical meaning, the normal subgroup generated by ``randomly' chosen elements of has trivial intersection with .

     

Structural covariance of graphs

Algebraic structures including multiple rank tensors, linear and non-linear operators are related to and represented with various types of graphs. Special emphasis is placed on linear operators e.g. on the Hibert space. A different graph represents the same operator depending on the basis frame used, in general non-orthonormal. All such graphs are shown to belong in one equivalence class and are termed structurally covariant. Crucial indices related to eigenvalues but invariant under any basis frame changes including non-orthonormal ones provide one way to characterize each class. A set of rules are given that allow one to find the graphs structurally covarinat with a given one and/or to deduce the class indices directly by simple pictorial manipulations on a graph. Applications in various fields including the quantum theory of molecules and reactions are indicated.     

Deformational covariance of graphs

Graphs on n vertices are classified into equivalence classes under the linear group L(n). All graphs representing the same operator on a vector space V _n belong to the same class. Graphs of different operators may or may not belong to the same class as ascertained by rules that were given by the author. Graphs in the same class are structurally covariant. If, in addition, two graphs can be continuously deformed into each other in the sense of varying line strengths while remaining structurally covariant throughout, then the two graphs are termed deformationally covariant along such paths. Applications in the quantum theory of chemistry and to the dynamic stability theory of coupled reaction systems which occur in various fields are indicated.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

Spectral Sequences on Combinatorial Simplicial Complexes

The goal of this paper is twofold. First, we give an elementary introduction to the usage of spectral sequences in the combinatorial setting. Second we list a number of applications.In the first group of applications the simplicial complex is the nerve of a poset; we consider general posets and lattices, as well as partition-type posets. Our last application is of a different nature: the -quotient of the complex of directed forests is a simplicial complex whose cell structure is defined combinatorially.     

On the distributions of the form ∑i (δpi−δni)

We present some properties of the distributions T of the form ∑_i (δ_pi−δ_ni), with ∑_i d(p_i,n_i)<∞, which arise in the study of the 3-d Ginzburg–Landau problem; see Bourgain et al. (C. R. Acad. Sci. Paris, Ser. I 331 (2000) 119–124). We show that there always exists an irreducible representation of T. We also extend a result of Smets (C. R. Acad. Sci. Paris, Ser. I 334 (2002) 371–374) which says that T is a measure iff T can be written as a finite sum of dipoles.     

From a Floyd-Auslander minimal system to an odd triangular map

In 1989 A.N. Sharkovsky asked the question which of the properties characterizing continuous maps of the interval with zero topological entropy remain equivalent for triangular maps of the square. The problem is difficult and only partial results are known. However, in the case of triangular maps with nondecreasing fibres there are only few gaps in a classification (given by Z. Ko?an) of a set of 24 of these conditions. In the present paper we remove these gaps by giving an example of a triangular map in the square with the following properties:

(1)

all fibre maps are nondecreasing,

(2)

all recurrent points of the map are uniformly recurrent, and

(3)

the restriction of the map to the set of recurrent points has an uncountable scrambled set (and so is Li-Yorke chaotic).

The example is obtained by taking an appropriate Floyd-Auslander minimal system and then taking its appropriate continuous extension to a triangular map of the square.