On a certain type of commutators of operators

LetH be a separable infinite-dimensional Hilbert space and letC be a normal operator andG a compact operator onH. It is proved that the following four conditions are equivalent.

1. C +G is a commutatorAB-BA with self-adjointA.
2. There exists an infinite orthonormal sequencee _j inH such that |Σ _j ⁿ =1 (Ce _j, e_j)| is bounded.
3. C is not of the formC ₁ ⊕C ₂ whereC ₁ has finite dimensional domain andC ₂ satisfies inf {|(C ₂ x, x)|: ‖x‖=1}>0.
4. 0 is in the convex hull of the set of limit points of spC.

     

On an Ulam's problem

The existence and the uniqueness (with respect to a filtration-equivalence) of a vector flowX on ? ⁿ ,n≥3, such that:

1. X has not any stationary points on ? ⁿ ;
2. all orbits ofX are bounded;
3. there exists a filtration forX are proved in the present note.

     

k-convexn-person games and their cores

For any natural numbersk andn, the subclass ofk-convexn-person games is introduced. In casek=n, the subclass consists of the convexn-person games. Ak-convexn-person game is characterized in several ways in terms of the core and certain marginal worth vectors. The marginal worth vectors of a game are described in terms of an upper bound for the core and the corresponding gap function. It is shown that thek-convexity of ann-person gamev is equivalent to

1. all marginal worth vectors ofv belong to the core ofv; or
2. the core ofv is the convex hull of the set consisting of all marginal worth vectors ofv; or
3. the extreme points of the core ofv are exactly the marginal worth vectors ofv.

Examples ofk-convexn-person games are also treated.     

Convergence of representation averages and of convolution powers

LetS be a locally compact (σ-compact) group or semi-group, and letT(t) be a continuous representation ofS by contractions in a Banach spaceX. For a regular probability μ onS, we study the convergence of the powers of the μ-averageUx=∫T(t)xdμ(t). Our main results for random walks on a groupG are:

1. if μ is adapted and strictly aperiodic, and generates a recurrent random walk, thenU ⁿ (U-I) converges strongly to 0. In particular, the random walk is completely mixing.
2. If μ×μ is ergodic onG×G, then for every unitary representationT(.) in a Hilbert space,U ⁿ converges strongly to the orthogonal projection on the space of common fixed points. These results are proved for semigroup representations, along with some other results (previously known only for groups) which do not assume ergodicity.
3. If μ is spread-out with supportS, then $\left\| {\mu ^{n + K} - \mu ^n } \right\| \to 0$ if and only if e $ \in \overline { \cup _{j = 0}^\infty S^{ - j} S^{j + K} } .$ .

     

Graph bisection algorithms with good average case behavior

In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n ^{1?1/[(d+1)/2]}), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n ^2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:

1. the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,
2. whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),
3. the algorithm works well both theoretically and experimentally,
4. the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and
5. the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).

     

Compactness and the axiom of choice

In the absence of the axiom of choice four versions of compactness (A-, B-, C-, and D-compactness) are investigated. Typical results:

1. C-compact spaces form the epireflective hull in Haus of A-compact completely regular spaces.
2. Equivalent are:
3. the axiom of choice,
4. A-compactness = D-compactness,
5. B-compactness = D-compactness,
6. C-compactness = D-compactness and complete regularity,
7. products of spaces with finite topologies are A-compact,
8. products of A-compact spaces are A-compact,
9. products of D-compact spaces are D-compact,
10. powers X ^k of 2-point discrete spaces are D-compact,
11. finite products of D-compact spaces are D-compact,
12. finite coproducts of D-compact spaces are D-compact,
13. D-compact Hausdorff spaces form an epireflective subcategory of Haus,
14. spaces with finite topologies are D-compact.

1. Equivalent are:
2. the Boolean prime ideal theorem,
3. A-compactness = B-compactness,
4. A-compactness and complete regularity = C-compactness,
5. products of spaces with finite underlying sets are A-compact,
6. products of A-compact Hausdorff spaces are A-compact,
7. powers X ^k of 2-point discrete spaces are A-compact,
8. A-compact Hausdorff spaces form an epireflective subcategory of Haus.

1. Equivalent are:
2. either the axiom of choice holds or every ultrafilter is fixed,
3. products of B-compact spaces are B-compact.

1. Equivalent are:
2. Dedekind-finite sets are finite,
3. every set carries some D-compact Hausdorff topology,
4. every T ₁-space has a T ₁-D-compactification,
5. Alexandroff-compactifications of discrete spaces and D-compact.

     

Properties of vertex packing and independence system polyhedra

We consider two convex polyhedra related to the vertex packing problem for a finite, undirected, loopless graphG with no multiple edges. A characterization is given for the extreme points of the polyhedron \(\mathcal{L}_G = \{ x \in R^n :Ax \leqslant 1_m ,x \geqslant 0\} \) , whereA is them × n edge-vertex incidence matrix ofG and 1 _m is anm-vector of ones. A general class of facets of = convex hull{x∈R ⁿ :Ax≤1 _m ,x binary} is described which subsumes a class examined by Padberg [13]. Some of the results for are extended to a more general class of integer polyhedra obtained from independence systems.     

On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

On projective planes admitting elations and homologies

We consider projective planes Π of ordern with abelian collineation group Γ of ordern(n?1) which is generated by (A, m)-elations and (B, l)-homologies wherem =AB andA εl. We prove

1. Ifn is even thenn=2^e and the Sylow 2-subgroup of Γ is elementary abelian.
2. Ifn is odd then the Sylow 2-subgroup of Γ is cyclic.
3. Ifn is a prime then Π is Desarguesian.
4. Ifn is not a square thenn is a prime power.

     

A spectral approach to polyhedral dimension

Thespectrum spec( ) of a convex polytope is defined as the ordered (non-increasing) list of squared singular values of [A|1], where the rows ofA are the extreme points of . The number of non-zeros in spec( ) exceeds the dimension of by one. Hence, the dimension of a polytope can be established by determining its spectrum. Indeed, this provides a new method for establishing the dimension of a polytope, as the spectrum of a polytope can be established without appealing to a direct proof of its dimension. The spectrum is determined for the four families of polytopes defined as the convex hulls of:

1. The edge-incidence vectors of cutsets induced by balanced bipartitions of the vertices in the complete undirected graph on 2_q vertices (see Section 6).
2. The edge-incidence vectors of Hamiltonian tours in the complete undirected graph onn vertices (see Section 6).
3. The arc-incidence vectors of directed Hamiltonian tours in the complete directed graph ofn nodes (see Section 7).
4. The edge-incidence vectors of perfect matchings in the complete 3-uniform hypergraph on 3_q vertices (see Section 8).

In the cases of (ii) and (iii), the associated dimension results are well-known. The dimension results for (i) and (iv) do not seem to be well-known. General principles are discussed for ‘balanced polytopes’ arising from complete structures.     

Elementary Abelianp-extensions of algebraic function fields

LetK be a field of characteristicp>0 andF/K be an algebraic function field. We obtain several results on Galois extensionsE/F with an elementary Abelian Galois group of orderp ⁿ.

1. E can be generated overF by some elementy whose minimal polynomial has the specific formT ^pn?T?z.
2. A formula for the genus ofE is given.
3. IfK is finite, then the genus ofE grows much faster than the number of rational points (as [E∶F] → ∞).
4. We present a new example of a function fieldE/K whose gap numbers are nonclassical.

     

Algorithms for the vector maximization problem

We consider a convex setB inR ⁿ described as the intersection of halfspacesa _i ^T x ≦b _i (i ∈ I) and a set of linear objective functionsf _j =c _j ^T x (j ∈ J). The index setsI andJ are allowed to be infinite in one of the algorithms. We give the definition of theefficient points ofB (also called functionally efficient or Pareto optimal points) and present the mathematical theory which is needed in the algorithms. In the last section of the paper, we present algorithms that solve the following problems:

1. To decide if a given point inB is efficient.
2. To find an efficient point inB.
3. To decide if a given efficient point is the only one that exists, and if not, find other ones.
4. The solutions of the above problems do not depend on the absolute magnitudes of thec _j. They only describe the relative importance of the different activitiesx _i. Therefore we also consider $$\begin{gathered} \max G^T x \hfill \\ x efficient \hfill \\ \end{gathered} $$ for some vectorG.

     

Multidimensional symmetric stable processes

This paper surveys recent remarkable progress in the study of potential theory for symmetric stable processes. It also contains new results on the two-sided estimates for Green functions, Poisson kernels and Martin kernels of discontinuous symmetric α-stable process in boundedC ^1,1 open sets. The new results give explicit information on how the comparing constants depend on parameter α and consequently recover the Green function and Poisson kernel estimates for Brownian motion by passing α ↑ 2. In addition to these new estimates, this paper surveys recent progress in the study of notions of harmonicity, integral representation of harmonic functions, boundary Harnack inequality, conditional gauge and intrinsic ultracontractivity for symmetric stable processes. Here is a table of contents.

1. Introduction
2. Green function and Poisson kernel estimates

1. Estimates on balls
2. Estimates on boundedC ^1,1 domains
3. Estimates on boundedC ^1,1 open sets

1. Harmonic functions and integral representation
2. Two notions of harmonicity
3. Martin kernel and Martin boundary
4. Integral representation and uniqueness
5. Boundary Harnack principle
6. Conditional process and its limiting behavior
7. Conditional gauge and intrinsic ultracontractivity

     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

The problem of differentiating an asymptotic expansion in real powers. Part II: Factorizational theory

In Part II of our work we approach the problem discussed in Part I from the new viewpoint of canonical factorizations of a certain nth order differential operator L. The main results include:

1. characterizations of the set of relations $$ f^{(k)} (x) = P^{(k)} (x) + o^{(k)} (x^{\alpha _n - k} ),x \to + \infty ,0 \leqslant k \leqslant n - 1, $$ where $$ P(x) = a_1 x^{\alpha _1 } + \cdots + a_n x^{\alpha _n } and \alpha _1 > \alpha _2 > \cdots > \alpha _n , $$ by means of suitable integral conditions
2. formal differentiation of a real-power asymptotic expansion under a Tauberian condition involving the order of growth of L
3. remarkable properties of asymptotic expansions of generalized convex functions.

     

Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (J. Comput. System Sci. 51 (3), 390–399, 1995) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once, in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present:

1. an O(n ²) algorithm performing O(logn·log e(P)) comparisons
2. an O(n ^2:5) algorithm performing at most (1+?) log e(P)+O _? (n) comparisons
3. an O(n ^2:5) algorithm performing O(log e(P)) comparisons.

All our algorithms can be implemented in such a way that their computational bottleneck is confined in a preprocessing phase, while the sorting phase is completed in O(q)+O(n) time, where q denotes the number of comparisons performed.     

Computing Hereditary Convex Structures

Color red and blue the n vertices of a convex polytope \(\mathcal{P}\) in ?³. Can we compute the convex hull of each color class in o(nlog?n) time? What if we have more than two colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of \(\mathcal{P}\) inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.     

Separation of two convex sets in convexity structures

A convexity structure satisfies the separation propertyS ₄ if any two disjoint convex sets extend to complementary half-spaces. This property is investigated for alignment spaces,n-ary convexities, and graphs. In particular, it is proven that

1. ann-ary convexity isS ₄ iff every pair of disjoint polytopes with at mostn vertices can be separated by complementary half spaces, and
2. an interval convexity isS ₄ iff it satisfies the analogue of the Pasch axiom of plane geometry.

A characterization of bipartite and weakly modular spaces withS ₄ convexity is given in terms of forbidden subgraphs.     

Parametric nonlinear discrete optimization over well-described sets and matroid intersections

We address optimization of parametric nonlinear functions of the form f(Wx), where ${f : \mathbb {R}^d \rightarrow \mathbb {R}}$ is a nonlinear function, W is a d × n matrix, and feasible x are in some large finite set ${\mathcal {F}}$ of integer points in ${\mathbb {R}^n}$ . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f, W and ${\mathcal {F}}$ . One of our main motivations is multi-objective discrete optimization, where f trades off the linear functions given by the rows of W. Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures. We assume that ${\mathcal {F}}$ is well described (i.e., we can efficiently optimize a linear objective function on ${\mathcal {F}}$ ; equivalently, we have an efficient separation oracle for the convex hull of ${\mathcal {F}}$ ). For example, the sets of characteristic vectors of (i) matchings of a graph, and (ii) common bases of a pair of matroids on a common ground set satisfy this property. In this setting, the problem is already known to be intractable (even for a single matroid), for general f (given by a comparison oracle), for (i) d = 1 and binary-encoded W, and for (ii) d = n and W = I. Our main results (a few technicalities and some generality suppressed):

1. When ${\mathcal {F}}$ is well described, f is convex (or even quasi-convex), and W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic algorithm for maximization.

1. When ${\mathcal {F}}$ is well described, f is a norm, and W is binary-encoded, we give an efficient deterministic constant-approximation algorithm for maximization (Note that the approximation factor depends on the norm, and hence implicitly on the number of rows of W, while the running time increases only linearly in the number of rows of W).

1. When non-negative ${\mathcal {F}}$ is well described, f is “ray concave” and non-decreasing, and non-negative W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic constant-approximation algorithm for minimization.

1. When ${\mathcal {F}}$ is the set of characteristic vectors of common independent sets or bases of a pair of rational vectorial matroids on a common ground set, f is arbitrary, and W has a fixed number of rows and is unary encoded, we give an efficient randomized algorithm for optimization.