Some results on entire functions of finite lower order

Letf(z) be an entire function of order λ and of finite lower order μ. If the zeros off(z) accumulate in the vicinity of a finite number of rays, then

1. λ is finite;
2. for every arbitrary numberk ₁>1, there existsk ₂>1 such thatT(k ₁ r,f)≤k ₂ T(r,f) for allr≥r ₀. Applying the above results, we prove that iff(z) is extremal for Yang's inequalityp=g/2, then
3. every deficient values off(z) is also its asymptotic value;
4. every asymptotic value off(z) is also its deficient value;
5. λ=μ;
6. $\sum\limits_{a \ne \infty } {\delta (a,f) \leqslant 1 - k(\mu ).} $

     

Les operateurs quasi Fredholm: Une generalisation des operateurs semi Fredholm

The present paper is concerned with the study of a new class of linear operators on a Hilbert space: the class of quasi-Fredholm operators, which contains many operators already studied in the litterature (in particular semi-Fredholm operators). An operatorA is said to be quasi-Fredholm of degreed, if the following conditions are satisfied:

1. For alln greater thand, R(A ⁿ )∩N(A)=R(A ^d )∩N(A);
2. N(A)∩R(A ^d ) is closed inH;
3. R(A)+N(A ^d ) is closed inH.

Two characterisations of quasi-Fredholm operators are given:

1. A is quasi-Fredholm iff there exists a direct decomposition ofH into the sum of two subspacesH ₁ andH ₂ which are invariant underA and such that the restriction ofA toH ₁ is quasi-Fredholm of degree 0 and the restriction ofA toH ₂ is nilpotent (Kato decomposition).
2. A is quasi-Fredholm iff there exists a neighborhoodD of 0 in C such that for all λ≠0 in that neighborhoodA?λI has a generalized inverse which is meromorphic inD?{0} (The generalized inverse is holomorphic inD iffA is of degree 0).

The bulk of the paper is devoted to the proofs of these characterizations and of related results, making use of the theory of operators ranges and of generalized inverses. Most of the results extend easily to the Banach case. The rest of the paper deals with the class of quasi-normal operators, which is closely related to the class of spectral operators. Some applications of the first part of the paper are given in this context.     

Boolean approach to planar embeddings of a graph

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.

1. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
2. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2 ^c(H)?1, wherec (H) is the number of the components of the graphH which is related toG.

     

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

     

States on bounded commutative residuated lattices

We define states on bounded commutative residuated lattices and consider their property. We show that, for a bounded commutative residuated lattice X,

1. If s is a state, then X/ker(s) is an MV-algebra.
2. If s is a state-morphism, then X/ker(s) is a linearly ordered locally finite MV-algebra.

Moreover we show that for a state s on X, the following statements are equivalent:

1. s is a state-morphism on X.
2. ker(s) is a maximal filter of X.
3. s is extremal on X.

     

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.     

Every 4k-edge-connected graph is Weakly 3k-linked

We prove:

1. Fork ≥ 2 andα = 0, 1, every (4k + 2α)-edge-connected graph is weakly (3k + 2α)-linked.
2. IfG is ak-edge-connected graph (k ≥ 2),s, t are vertices andf is an edge, then there exists a pathP betweens andt such thatf ? E(P) andG ? E(P) ? f is (k ? 2)-edge-connected, whereE(P) denotes the edge set ofP.

     

Ramanujan graphs

A large family of explicitk-regular Cayley graphsX is presented. These graphs satisfy a number of extremal combinatorial properties.

1. For eigenvaluesλ ofX eitherλ=±k or ¦λ¦≦2 √k?1. This property is optimal and leads to the best known explicit expander graphs.
2. The girth ofX is asymptotically ≧4/3 log _k?1 ¦X¦ which gives larger girth than was previously known by explicit or non-explicit constructions.

     

Constructing a perfect matching is in random NC

We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. We also show that several related problems lie in Random NC. These include:

1. Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation;
2. Constructing a maximum-cardinality matching;
3. Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary;
4. Constructing a maximums-t flow in a directed graph whose edge weights are given in unary.

     

Homogeneity in infinite permutation groups

It is shown that ifG is a permutation group on an infinite setX, andG is (k?1)-transitive but notk-transitive (wherek ≥ 5), then the following hold:

1. G is not (k + 3)-homogeneous.
2. IfG is (k + 2)-homogeneous, then the group induced byG on ak-subset ofX is the alternating groupA _k .

     

Sur les Suites Presque Echangeables DansL q , 1≦q<2

Let 1≦q<p<2. We construct a bounded sequence (X _n ) _n∈N inL _q which defines a typeσ onL _q , such that:

1. (X _n ) _n∈N is equivalent to the unit vector basis ofl _p .
2. The l-conic classK ₁(σ) generated byσ is not relatively compact for the topology of uniform convergence on bounded sets ofL _q .
3. (X _n ) _n∈N has no almost exchangeable subsequence after any change of density.

This sequence does not verify the two natural conditions inL _q -spaces that ensure the existence of an almost symmetric subsequence.     

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.

     

Thinning of point processes,revisited

ＴＨＩＮＮＩＮＧＯＦＰＯＩＮＴＰＲＯＣＥＳＳＥＳ,ＲＥＶＩＳＩＴＥＤＨＥＳＨＥＮＧＷＵ（何声武）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃａｌＳｔａｔｉｓｔｉｃｓ,ＥａｓｔＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙＳｈａｎｇｈａｉ２０００６２,Ｃ...     

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

     

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.     

Topologies on products of partially ordered sets III: Order convergence and order topology

This paper deals with the question under which circumstances filter-theoretical order convergence in a product of posets may be computed componentwise, and the same problem is treated for convergence in the order topology (which may differ from order convergence). The main results are:

1. Order convergence in a product of posets is obtained componentwise if and only if the number of non-bounded posets occurring in this product is finite (1.5).
2. For any product of posets, the projections are open and continuous with respect to the order topologies (2.1).
3. A productL of chainsL _i has topological order convergence iff all but a finite number of the chains are bounded. In this case, the order topology onL agrees with the product topology (2.7).
4. If (L _i :j ∈J) is a countable family of lattices with topological order convergence and first countable order topologies then order topology of the product lattice and product topology coincide (2.8).
5. LetP ₁ be a poset with topological order convergence and locally compact order topology. Then for any posetP ₂, the order topology ofP ₁?P ₂ coincides with the product topology (2.10).
6. A latticeL which is a topological lattice in its order topology is join- and meet-continuous. The converse holds whenever the order topology ofL?L is the product topology (2.15).

Many examples are presented in order to illustrate how far the obtained results are as sharp as possible.     

Packing seagulls

A seagull in a graph is an induced three-vertex path. When does a graph G have k pairwise vertex-disjoint seagulls? This is NP-complete in general, but for graphs with no stable set of size three we give a complete solution. This case is of special interest because of a connection with Hadwiger’s conjecture which was the motivation for this research; and we deduce a unification and strengthening of two theorems of Blasiak [2] concerned with Hadwiger’s conjecture. Our main result is that a graph G (different from the five-wheel) with no three-vertex stable set contains k disjoint seagulls if and only if

1. |V (G)|≥3k
2. G is k-connected
3. for every clique C of G, if D denotes the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C then |D|+|V (G)\C|≥2k, and
4. the complement graph of G has a matching with k edges.

We also address the analogous fractional and half-integral packing questions, and give a polynomial time algorithm to test whether there are k disjoint seagulls.     

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.