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, ...).

     

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.     

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.

     

Treewidth computation and extremal combinatorics

For a given graph G and integers b,f ≥0, let S be a subset of vertices of G of size b+1 such that the subgraph of G induced by S is connected and S can be separated from other vertices of G by removing f vertices. We prove that every graph on n vertices contains at most $n\left( {_b^{b + f} } \right)$ such vertex subsets. This result from extremal combinatorics appears to be very useful in the design of several enumeration and exact algorithms. In particular, we use it to provide algorithms that for a given n-vertex graph G

1. compute the treewidth of G in time O(1.7549 ⁿ ) by making use of exponential space and in time O(2.6151 ⁿ ) and polynomial space
2. decide in time O(n ⁵· $_{k + 2}^{\left\lceil {(2n + k + 8)/3} \right\rceil } $ ) if the treewidth of G is at most k
3. list all minimal separators of G in time O(1.6181 ⁿ ) and all potential maximal cliques of G in time O(1.7549 ⁿ ).

This significantly improves previous algorithms for these problems.     

E-free objects inE-varieties of inverse rings

We show that for any regular ring (R, +, -), the following conditions are equivalent:

1. (R, -) is inverse.
2. (R, -) isE-solid.
3. (R, -) is locally inverse.
4. (R, -) is locallyE-solid.

We also show that there is ane-free object in eache-variety of inverse rings.     

Positive Lyapunov exponent for generic one-parameter families of unimodal maps

Letf _{a a∈A} be a C² one-parameter family of non-flat unimodal maps of an interval into itself anda* a parameter value such that

1. f_a* satisfies the Misiurewicz Condition,
2. f_a* satisfies a backward Collet-Eckmann-like condition,
3. the partial derivatives with respect tox anda of f _a ⁿ (x), respectively at the critical value and ata*, are comparable for largen.

Thena* is a Lebesgue density point of the set of parameter valuesa such that the Lyapunov exponent of f_a at the critical value is positive, and f_a admits an invariant probability measure absolutely continuous with respect to the Lebesgue measure. We also show that given f_a* satisfying (a) and (b), condition (c) is satisfied for an open dense set of one-parameter families passing through f_a*.     

Complex Banach spaces whose duals areL 1-spaces

We prove that for a complex Banach spaceA the following properties are equivalent:

1. A ^* is isometric to anL ₁(μ)-space;
2. every family of 4 balls inA with the weak intersection property has a non-empty intersection;
3. every family of 4 balls inA such that any 3 of them have a non-empty intersection, has a non-empty intersection.

     

Exklusive Graphen und Hamiltonche Graphenn-ten Grades II

The graphs considered are finite and undirected, loops do not occur. An induced subgraphI of a graphX is called animitation ofX, if

1. the degreesd _I(v)≡d _X(v) (mod 2) for allv∈V(I)
2. eachu∈V(X)?V(I) is connected with the setv(I) by an even number of edges. If the set of imitations ofX consists only ofX itself, thenX is anexclusive graph. AHamiltonian graph of degree n (abbr.:HG ⁿ) in the sense ofA. Kotzig is ann-regular graph (n>1) with a linear decomposition and with the property, that any two of the linear components together form a Hamiltonian circuit of the graph.

In the first chapter some theorems concerning exclusive graphs and Euler graphs are stated. Chapters 2 deals withHG ^n′ s and bipartite graphs. In chapters 3 a useful concept—theX-graph of anHG ⁿ—is defined; in this paper it is the conceptual connection between exclusive graphs andHG ^n′ s, since a graphG is anHG ⁿ, if all itsX-graphs are exlusive. Furthermore, some theorems onX-graphs are proved. Chapter 4 contains the quintessence of the paper: If we want to construct a newHG ⁿ F from anotherHG ⁿ G, we can consider certain properties of theX-graphs ofG to decide whetherF is also anHG ⁿ.     

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.     

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.     

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.

     

Analytische Fortsetzbarkeit von zufälligen Potenzreihen bezüglich abhängiger Zufallsvariabler

Рассматриваются слу чайная величина \(\mathfrak{X} = (X_n (\omega ))\) , удовлетворяющая усл овиюE(X _n ⁴ )≦M, и соответствующ ий случайный степенн ой ряд \(f_x (z;\omega ) = \mathop \sum \limits_{n = 0}^\infty a_n X_n (\omega )z^n\) . Устанавливаются тео ремы непродолжимост и почти наверное:

1. дляf _x при условиях с лабой мультипликати вности на \(\mathfrak{X}\) ,
2. для \(f_{\tilde x}\) , где \(\mathop \mathfrak{X}\limits^ \sim = (\mathop X\limits^ \sim _n )\) есть подп оследовательность в \(\mathfrak{X}\) ,
3. для по крайней мере од ного из рядовf _x′ илиf _x″ , где \(\mathfrak{X}'\) и \(\mathfrak{X}''\) — некоторые п ерестановки \(\mathfrak{X}\) , выбираемые универс ально, т. е. независимо от коэффициентовa _n .

     

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.

     

Uppers to zero in R[x] and almost principal ideals

Let R be an integral domain with quotient field K and f(x) a polynomial of positive degree in K[x]. In this paper we develop a method for studying almost principal uppers to zero ideals. More precisely, we prove that uppers to zero divisorial ideals of the form I = f(x)K[x] ∩ R[x] are almost principal in the following two cases:

• J, the ideal generated by the leading coefficients of I, satisfies J ^?1 = R.
• I ^?1 as the R[x]-submodule of K(x) is of finite type.

Furthermore we prove that for I = f(x)K[x] ∩ R[x] we have:

• I ^?1 ∩ K[x] = (I: K(x) I).
• If there exists p/q ∈ I ^?1 ? K[x], then (q, f) ≠ 1 in K[x]. If in addition q is irreducible and I is almost principal, then I′ = q(x)K[x] ∩ R[x] is an almost principal upper to zero.

Finally we show that a Schreier domain R is a greatest common divisor domain if and only if every upper to zero in R[x] contains a primitive polynomial.     

Lifting measures to Markov extensions

Generalizing a theorem ofHofbauer (1979), we give conditions under which invariant measures for piecewise invertible dynamical systems can be lifted to Markov extensions. Using these results we prove:

1. IfT is anS-unimodal map with an attracting invariant Cantor set, then ∫log|T′|dμ=0 for the unique invariant measure μ on the Cantor set.
2. IfT is piecewise invertible, iff is the Radon-Nikodym derivative ofT with respect to a σ-finite measurem, if logf has bounded distortion underT, and if μ is an ergodicT-invariant measure satisfying a certain lower estimate for its entropy, then μ?m iffh _μ (T)=Σlogf dμ.

     

ДИФФЕРЕНцИАльНыЕ сВ ОИстВА ИжВИВАУЩИхсь ФУНкцИИ

A continuous real valued function defined on an intervalD is called crinkly iff the setf ^?1(У) ∩I is uncountable for each interval \(I \subseteqq D\) and number \(y \in (\mathop {\inf }\limits_I f,\mathop {\sup }\limits_I f)\) . The main result of the paper consists in the following assertion. Let the closed segment [0, 1] be represented as a union of four measurable, mutually nonintersecting setsE ₁,Е ₂,E ₃,E ₄. Then, for each functionH(δ) such thatH(δ)→ + ∞ andδH(δ)→0 asδ→0, there exists a crinkly functionf possessing the following five properties:

1. a.e. onE ₁:D ⁺ f(x)=D-f(x)=+∞,D ₊ f(x)=D?f(x)=?∞;
2. a.e. onE ₂:D ⁺ f(x)=+∞,D?f(x)=?∞,D ₊f(x)=D-f(x)=0;
3. a.e. onE ₃:D ₊ f(x)=?∞,D ^? f(x)=+∞,D ⁺ f(x)=D?f(x)=0;
4. a.e. onE ₄:Df(x)=0;
5. the modulus of continuityΩ off on [0, 1] satisfies $$\omega (\delta ,f,[0,1]) \leqq \delta H(\delta ).$$

     

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.

     

On the deque conjecture for the splay algorithm

Splay is a simple, efficient algorithm for searching binary search trees, devised by Sleator and Tarjan, that reorganizes the tree after each search by means of rotations. An open conjecture of Sleator and Tarjan states that Splay is, in essence, the fastest algorithm for processing any sequence of search operations on a binary search tree, using only rotations to reorganize the tree. Tarjan proved a basic special case of this conjecture, called theScanning Theorem, and conjectured a more general special case, called theDeque Conjecture. The Deque Conjecture states that Splay requires linear time to process sequences of deque operations on a binary tree. We prove the following results:

1. Almost tight lower and upper bounds on the maximum numbers of occurrences of various types of right rotations in a sequence of right rotations performed on a binary tree. In particular, the lower bound for right 2-turns refutes Sleator's Right Turn Conjecture.
2. A linear times inverse Ackerman upper bound for the Deque Conjecture. This bound is derived using the above upper bounds.
3. Two new proofs of the Scanning Theorem, one, a simple potential-based proof that solves Tarjan's problem of finding a potential-based proof for the theorem, the other, an inductive proof that generalizes the theorem.

     

Fixed point theory and product,sub-, super-spaces

In this paper, we definen-segmentwise metric spaces and then we prove the following results:

1. (i)|Let (X, d) be ann-segmentwise metric space. ThenX ⁿ has the fixed point property with respect to uniformly continuous bounded functions if and only if, for any continuous functionF: C ^*(X) → C^*(X) and for anyn-tuple of distinct points x₁, x₂, ?, x_n ∈X, there exists anh ∈C ^*(X) such that $$F(h)(x_1 ) = h(x_1 ),i = 1,2,...,n;$$ whereC ^*(X) has either the uniform topology or the subspace product (Tychonoff) topology \((C^ * (X) \subseteq X^X )\) .
2. LetX _i (i = 1, 2, ?) be countably compact Hausdorff spaces such thatX ₁ × ? × X_n has the fixed point property for alln ∈N Then the product spaceX ₁ × X₂ × ? has the fixed point property. We shall also discuss several problems in the Fixed Point Theory and give examples if necessary. Among these examples, we have:
3. There exists a connected metric spaceX which can be decomposed as a disjoint union of a closed setA and an open setB such thatA andB have the fixed point property andX does not have.
4. There exists a locally compact metrizable spaceX which has the fixed point property but its one-point compactificationX ⁺ does not have the fixed point property.

Other relevant results and examples will be presented in this paper.     

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.