Strictly ordered minimal subsets of a class of convex monotone skew-product semiflows

We study the topological and ergodic structure of a class of convex and monotone skew-product semiflows. We assume the existence of two strongly ordered minimal subsets and we obtain an ergodic representation of their upper Lyapunov exponents. In the case of null upper Lyapunov exponents, we obtain a lamination into minimal subsets of an intermediate region where the restriction of the semiflow is affine. In the hyperbolic case, we deduce the long-time behaviour of every trajectory ordered with K₂. Some examples of skew-product semiflows generated by non-autonomous differential equations and satisfying the assumptions of monotonicity and convexity are also presented.     

Minimal nil-transformations of class two

On a metric minimal flow (X, a) which is a torus (K) extension of its largest almost periodic factorZ=X/K, the following conditions are equivalent.

1. (X, a) is a nil-transformation of the form (N/Γ,a) whereK is central inN and [N, N]?K.
2. E(X), the enveloping group of (X, a) is a nilpotent group of class 2.
3. Any minimal subset Ω ofX×X is invariant under the diagonal action ofK and the quotient Ω/K=Z ₁, is the largest almost periodic factor of Ω.

The enveloping groups of such flows are described and a corollary on cocycles of the circle into itself is deduced. Finally general minimal niltransformations of class two are shown to be of the form considered in condition (i) above (possibly with a different nilpotent group) and consequently we deduce that the class of minimal flows which are group factors of nil-transformations of class 2 is closed under factors.     

Optimal partitions

Consider a set of numbersZ={z ₁≥z ₂≥...≥z _n} and a functionf defined on subsets ofZ. LetP be a partition ofZ into disjoint subsetsS _i, say,g of them. The cost ofP is defined as $$C(P) = \sum\limits_{i = 1}^g {f(S_i )} .$$ By definition, in anordered partition, every pair of subsets has the property that the numbers in one subset are all greater than or equal to every number in the other subset. The problem of minimizingC(P) over all ordered partitions is called the optimal ordered partition problem. While no efficient method is known for solving the general optimal partition problem, the optimal ordered partition problem can be solved in quadratic time by dynamic programming. In this paper, we study the conditions onf under which an optimal ordered partition is indeed an optimal partition. In particular, we present an additive model and a multiplicative model for the functionf and give conditions such that the optimal partition problem can be reduced to the optimal ordered partition problem. We illustrate our results by applying them on problems which have been investigated previously in the literature.     

Marriage in denumerable societies

A society is an ordered triple (M, W, K) of sets such that M, W are disjoint and K ? M × W. An espousal of (M, W, K) is a subset of K of the form {(a, e(a)) : a ∈ M} where e(a₁) ≠ e(a₂) whenever a₁ ≠ a₂. If M is countable, we associate with (M, W, K) and each ordinal α a function m_α from the set of subsets of W into the union of the set of integers and {? ∞, ∞}. Three different definitions of m_α (all fairly elaborate) are presented and their equivalence under suitable conditions is proved. Assuming M to be countable, we prove that (i) (M, W, K) has an espousal if and only if $\text{m}{}_{\mathrm{\Omega }}\text{(X) ? 0}$ for every subset X of W, where Ω is the first uncountable ordinal, and (ii) if X ? W and α ? β and m_α(X) < ∞ and m_α(Z) ? 0 for every subset Z of X then m_α(Z) = m_β(Z) for every subset Z of X. The result (i) is a theorem of Damerell and Milner, but the proof here presented differs somewhat in formulation and structure from theirs.     

Wedderburn polynomials over division rings, I

A Wedderburn polynomial over a division ring K is a minimal polynomial of an algebraic subset of K. Such a polynomial is always a product of linear factors over K, although not every product of linear polynomials is a Wedderburn polynomial. In this paper, we establish various properties and characterizations of Wedderburn polynomials over K, and show that these polynomials form a complete modular lattice that is dual to the lattice of full algebraic subsets of K. Throughout the paper, we work in the general setting of an Ore skew polynomial ring K[t,S,D], where S is an endomorphism of K and D is an S-derivation on K.     

On stable set polyhedra for K1,3-free graphs

We give several classes of facets for the convex hull of incidence vectors of stable sets in a K_1,3-free graph, including facets with (a, a + 1)-valued coefficients, where a = 1, 2, 3,…. These provide counterexamples to three recent conjectures concerning such facets. We also give a necessary and sufficient condition for a minimal imperfect graph to be an odd hole or an odd antihole and indicate that minimal imperfect K_1,3-free graphs satisfy the condition.     

Are two given elements neighbouring?

Let |H|=n be a finite ordered set (say, different real numbers. However, their ordering is unknown to us. In this paper we solve the following problem: What is the minimal number of comparisons needed to decide wether z₁ and z₂ are neighbouring in H or not. The answer is 2(n?2).     

A novel approach towards fuzzy Γ-ideals in ordered Γ-semigroups

In many applied disciplines like computer science, coding theory and formal languages, the use of fuzzified algebraic structures especially ordered semigroups play a remarkable role. In this paper, we introduce a new concept of fuzzy Γ-ideal of an ordered Γ-semigroup G called an (∈, ∈ ?q _k )-fuzzy Γ-ideal of G. Fuzzy Γ-ideal of type (∈, ∈ ∨q _k ) are the generalization of ordinary fuzzy Γ-ideals of an ordered Γ-semigroup G. A new characterization of ordered Γ-semigroups in terms of an (∈, ∈ ∨q _k )-fuzzy Γ-ideal is given. We show that a fuzzy subset λ of an ordered Γ-semigroup G is an (∈, ∈ ∨q _k )-fuzzy Γ-ideal of G if and only if U (λ; t) is a Γ-ideal of G for all \(t \in \left( {0,\frac{{1 - k}} {2}} \right]\) . We also investigate some important characterization theorems in terms of this notion. Finally, regular ordered Γ-semigroups are characterized by the properties of their (∈, ∈ ∨q _k )-fuzzy Γ-ideals.     

On pancyclic digraphs

We show that a strongly connected digraph with n vertices and minimum degree ? n is pancyclic unless it is one of the graphs K_p,p. This generalizes a result of A. Ghouila-Houri. We disprove a conjecture of J. A. Bondy by showing that there exist hamiltonian digraphs with n vertices and $\text{1}\text{2}\text{n(n + 1) – 3}$ edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least $\text{1}\text{2}\text{n(n + 1) – 1}$ edges is pancyclic and we give some generalizations of this result. As applications of these results we determine the minimal number of edges required in a digraph to guarantee the existence of a cycle of length k, k ? 2, and we consider the corresponding problem where the digraphs under consideration are assumed to be strongly connected.     

A fixed point theorem for eventually nonexpansive semigroups of mappings

Let K be a subset of a Banach space X. A semigroup $\text{F}$ = {?_α ∥ α ∞ A} of Lipschitz mappings of K into itself is called eventually nonexpansive if the family of corresponding Lipschitz constants $\text{{k}{}_{\mathrm{\alpha }}\text{¦ α ? A}}$ satisfies the following condition: for every ? > 0, there is a γ?A such that k_β < 1 + ? whenever ?_β ? ?_γ$\text{F}$ = {?_gg?_α ¦ ?_α ? $\text{F}$}. It is shown that if K is a nonempty, closed, convex, and bounded subset of a uniformly convex Banach space, and if $\text{F}$:K → K is an eventually nonexpansive, commutative, linearly ordered semigroup of mappings, then $\text{F}$ has a common fixed point. This result generalizes a fixed point theorem by Goebel and Kirk.     

Definable functions in the ℵ<Subscript>0</Subscript>-categorical weakly circularly minimal structures

We continue studying the analogs of o-minimality and weak o-minimality for circularly ordered sets. We present a complete characterization of the behavior of unary definable functions in an ?₀-categorical 1-transitive weakly circularly minimal structure. Using it, we describe the ?₀-categorical 1-transitive nonprimitive weakly circularly minimal structures of convexity rank greater than 1 up to binarity.     

On indecomposable subcones

Let K₁,K₂ be cones. We say that K₁ is a subcone of K₂ if ExtK₁?ExtK₂. Furthermore, if K₁≠K₂, K₁ is called a proper subcone; if dimK₁=dimK₂, K₁ is called a non-degenerate subcone. We first prove that every n-dimensional indecomposable cone, n?3, contains a non-degenerate indecomposable subcone which has no more than 2n-2 extremals. Then we construct for each n?3 an n-dimensional indecomposable cone with exactly 2n-2 extremals such that each of its proper non-degenerate subcones is decomposable.     

Similarity invariants of operators on a class of Gowers-Maurey spaces

This paper studies the similarity invariants of operators on a class of Gowers-Maurey spaces, Σ _dc spaces, where an infinite dimensional Banach space X is called a Σ _dc space if for every bounded linear operator on X the spectrum is disconnected unless it is a singleton. It shows that two strongly irreducible operators T ₁ and T ₂ on a Σ _dc space are similar if and only if the K ₀-group of the commutant algebra of the direct sum T ₁⊕T ₂ is isomorphic to the group of integers ?. On a Σ _dc space X, it uses the semigroups of the commutant algebras of operators to give a condition that an operator is similar to some operator in (ΣSI)(X), it further gives a necessary and sufficient condition that two operators in (ΣSI)(X) are similar by using the ordered K ₀-groups. It also proves that every operator in (ΣSI)(X) has a unique (SI) decomposition up to similarity on a Σ _dc space X, where (ΣSI)(X) denotes the class of operators which can be written as a direct sum of finitely many strongly irreducible operators.     

Linearly ordered compacta and Banach spaces with a projectional resolution of the identity

We construct a compact linearly ordered space Kω₁ of weight ℵ₁, such that the space C(Kω₁) is not isomorphic to a Banach space with a projectional resolution of the identity, while on the other hand, Kω₁ is a continuous image of a Valdivia compact and every separable subspace of C(Kω₁) is contained in a 1-complemented separable subspace. This answers two questions due to O. Kalenda and V. Montesinos.     

Asymptotics of the heat exchange

Let K be a compact subset in Euclidean space , and let E_K(t) denote the total amount of heat in at time t, if K is kept at fixed temperature 1 for all t?0, and if has initial temperature 0. For two disjoint compact subsets K₁ and K₂ we define the heat exchange H_K1,K2(t)=E_K1(t)+E_K2(t)−E_K1∪K2(t). We obtain the leading asymptotic behaviour of H_K1,K2(t) as t→0 under mild regularity conditions on K₁ and K₂.     

On Connected 2-K n -Residual Graphs

A graph G is said to be K _n -residual if for every point u in G, the graph obtained by removing the closed neighborhood of u from G is isomorphic to K _n . We inductively define a multiply-K _n -residual graph by saying that G is m-K _n -residual if the removal of the closed neighborhood of any vertex of G results in an (m – 1)-K _n -residual graphs. Erdös, Harary and Klawe [2] determined the minimum order of the m?K _n -residual graphs for all m and n, which are not necessarily connected, the minimum order of connected; K _n -residual graphs, all K _n -residual extremal graphs. They also stated some conjectures regarding the connected case. In this paper, we determine the minimum order of a connected 2-K _n -residual graph and specify the extremal graphs, expect for n = 3. In particular, we determining only one connected 2-K ₄-residual graph of minimal order, and show that there is a connected 2-K ₆-residual graph non isomorphic to K ₈ × K ₃ with minimum order. Finally we present and a revised version of the conjecture in [2].     

On the semiring of cone preserving maps

If K is a proper cone in Rⁿ, then the cone of all linear operators that preserve K, denoted by π(K), forms a semiring under usual operator addition and multiplication. Recently J.G. Horne examined the ideals of this semiring. He proved that if K₁, K₂ are polyhedral cones such that π(K₁) and π(K₂) are isomorphic as semirings, then K₁ and K₂ are linearly isomorphic. The study of this semiring is continued in this paper. In Sec. 3 ideals of π(K) which are also faces are characterized. In Sec. 4 it is shown that π(K) has a unique minimal two-sided ideal, namely, the dual cone of π(K¹), where K¹ is the dual cone of K. Extending Horne's result, it is also proved that the cone K is characterized by this unique minimal two-sided ideal of π(K). The set of all faces of π(K) inherits a quotient semiring structure from π(K). Properties of this face-semiring are given in Sec. 5. In particular, it is proved that this face-semiring admits no nontrivial congruence relation iff the duality operator of π(K) is injective. In Sec. 6 the maximal one-sided and two-sided ideals of π(K) are identified. In Sec. 8 it is shown that π(K) never satisfies the ascending-chain condition on principal one-sided ideals. Some partial results on the question of topological closedness of principal one-sided ideals of π(K) are also given.     

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.