Edge-Directions of Standard Polyhedra with Applications to Network Flows

Recent results show that edge-directions of polyhedra play an important role in (combinatorial) optimization; in particular, a d-dimensional polyhedron with |D| distinct edge-directions has at most O(|D|^d-1) vertices. Here, we obtain a characterization of the directions of edges that are adjacent to a given vertex of a standard polyhedron of the form P = {x : Ax = b, l⩽ x⩽ u, tightening a standard necessary condition which asserts that such directions must be minimal support solutions of the homogenous equation Ax = 0 which are feasible at the given vertex. We specialize the characterization for polyhedra that correspond to network flows, obtaining a graph characterization of circuits which correspond to edge-directions. Applications to partitioning polyhedra are discussed. Research of these authors was supported by a grant from ISF – the Israel Science Foundation, by a VPR grant at the Technion, and by the Fund for the Promotion of Research at the Technion.     

Spectral Statistics of the Rectangular Billiard with a Flux Line

The density of states of a rectangular billiard with an Aharonov–Bohm flux line in its center was calculated in the semiclassical approximation and was used for the calculation of the form factor in the diagonal approximation. The distribution of nearest level spacings and the form factor were calculated also numerically. For some values of the flux these were found to be close to the ones of the semi-Poisson statistics. The difference between the numerical results and the semiclassical ones were found to be much larger than for chaotic and for integrable systems within similar approximations. Possible reasons for these discrepancies are discussed.     

Auslander-Reiten Numbers Games

Let \(\mathfrak {g}\) be a simple complex Lie algebra of types A _n , D _n , E _n , and Q a quiver obtained by orienting its Dynkin diagram. Let λ be a dominant weight, and E(λ) the corresponding simple highest weight representation. We show that the weight multiplicities of E(λ) may be recovered by playing a numbers game Λ _Q (λ), generalizing the well known Mozes game, constructing the orbit of λ under the action of the Weyl group W. The game board is provided by the Auslander-Reiten quiver Γ _Q of Q. The game moves are obtained by constructing Nakajima’s monomial crystal M(λ) directly out of Γ _Q . As an application, we consider Kashiwara’s parameterizations of the canonical basis. Let w ₀ be a reduced expression of the longest element w ₀ of W, adapted to a quiver Q of type A _n . We show that a set of inequalities defining the string (Kashiwara) cone with respect to w ₀, may be obtained by playing subgames of the numbers games Λ _Q (ω _i ) associated to fundamental representations.     

From Exact Systems to Riesz Bases in the Balian�CLow Theorem

We look at the time–frequency localization of generators of lattice Gabor systems. For a generator of a Riesz basis, this localization is described by the classical Balian–Low theorem. We establish Balian–Low type theorems for complete and minimal Gabor systems with a frame-type approximation property. These results describe how the best possible localization of a generator is limited by the degree of control over the coefficients in approximations given by the system, and provide a continuous transition between the classical Balian–Low conditions and the corresponding conditions for generators of complete and minimal systems. Moreover, this holds for the non-symmetric generalizations of these theorems as well.     

On the optimality of a simple strategy for searching graphs

Consider a search game with an immobile hider in a graph. A Chinese postman tour is a closed trajectory which visits all the points of the graph and has minimal length. We show that encircling the Chinese postman tour in a random direction is an optimal search strategy if and only if the graph is weakly Eulerian (i.e it consists of several Eulerian curves connected in a tree-like structure). Received: December 1999/Revised version: September 2000     

Generalized interval exchanges and the 2–3 conjecture

We introduce the notion of a generalized interval exchange induced by a measurable k-partition of [0,1). can be viewed as the corresponding restriction of a nondecreasing function on ℝ with . A is called λ-dense if λ(A _i ∩(a, b))>0 for each i and any 0≤ a< b≤1. We show that the 2–3 Furstenberg conjecture is invalid if and only if there are 2 and 3 λ-dense partitions A and B of [0,1), such that . We give necessary and sufficient conditions for this equality to hold. We show that for each integer m≥2, such that 3∤2m+1, there exist 2 and 3 non λ-dense partitions A and B of [0,1), corresponding to the interval exchanges on 2m intervals, for which and commute.     

A Planar 3-Convex Set is Indeed a Union of Six Convex Sets

Suppose S is a planar set. Two points $a,b$ in S  see each other via S if $[a,b]$ is included in S . F. Valentine proved in 1957 that if S is closed, and if for every three points of S, at least two see each other via S, then S is a union of three convex sets. The pentagonal star shows that the number three is the best possible. We drop the condition that S is closed and show that S is a union of (at most) six convex sets. The number six is best possible.     

A metric minimal flow whose enveloping semigroup contains finitely many minimal ideals is PI

We show that a minimal metric flowX whose enveloping semigroupE(X), contains finitely many minimal ideals, is a PI-flow; i.e.X has a proximal extensionX' which can be built by iterating proximal and isometric extensions (starting with the trivial one point flow). An example is given which shows that the converse theorem does not hold. Finally, we show that ifX is a minimal, non-trivial, metric, weakly mixing flow and the group action is nilpotent thenE(X) contains infinitely many minimal ideals.     

On the coupling between vibrational relaxation and molecular electronic transitions

Vibrational relaxation of a harmonic molecule in contact with its surrounding medium is studied, and its effect on the electronic relaxation rate in such molecules is examined. Results of earlier works which considered harmonic phonon models for the medium are extended to the case of a general thermal bath. The formal expression for the vibrational relaxation rate is modified but the general form of the final results for the electronic and vibrational time evolution is shown to remain intact.