J-selfadjointness of a class of high-order differential operators with transmission conditions

This paper is to investigate the J-selfadjointness of a class of high-order complex coefficients differential operators with transmission conditions. Using the Lagrange bilinear form of J-symmetric differential equations, the definition of J-selfadjoint differential operators and the method of matrix representation, we prove that the operator is J-selfadjoint operator, and the eigenvectors and eigen-subspaces corresponding to different eigenvalues are C-orthogonal.     

On the section of a convex polyhedron

Let P be a convex polyhedron in R³, and E be a plane cutting P. Then the section P_E=P∩E is a convex polygon. We show a sharp inequality , where L(P) denotes the sum of the edge-lengths of P.     

On the minimal reducible bound for outerplanar and planar graphs

Let L be the set of all additive and hereditary properties of graphs. For P₁, P₂ L we define the reducible property R = P₁ P₂ as follows: G P₁P₂ if there is a bipartition (V₁, V₂) of V(G) such that V₁ P₁ and V₂ P₂. For a property P L, a reducible property R is called a minimal reducible bound for P if P R and for each reducible property R′, R′ R → P R′. It is proved that the class of all outerplanar graphs has exactly two minimal reducible bounds in L. Some related problems for planar graphs are discussed.     

The deviation, density, and depth of partially ordered sets

Let P be a poset, and let γ be a linear order type with |γ| ≥ 3. The γ-deviation of P, denoted by γ-dev P, is defined inductively as follows: (1) γ-dev P=0, if P contains no chain of order type γ; (2) γ-dev P = , if γ-dev P and each chain C of type γ in P contains elements a and b such that a<b and [a, b] as an interval of P has γ-deviation <. There may be no ordinal such that γ-dev P = ; i.e., γ-dev P does not exist. A chain is γ-dense if each of its intervals contains a chain of order type γ. If P contains a γ-dense chain, then γ-dev P fails to exist. If either (1) P is linearly ordered or (2) a chain of order type γ does not contain a dense interval, then the converse holds. For an ordinal ξ, a special set S(ξ) is used to study ω_ξ-deviation. The depth of P, denoted by δ(P) is the least ordinal β that does not embed in P^*. Then the following statements are equivalent: (1) ω_ξ-dev P does not exist; (2) S(ξ) embeds in P; and (3) P has a subset Q of cardinality _ξ such that δ(Q^*) = ω_{ξ + 1}. Also ω_ξ-dev P = <ω_{ξ + 1} if and only if |δ(P^*)|_ξ; if these equivalent conditions hold, then ω^β_ξ < δ(P^*) ≤ ω ^{+ 1}_ξ for all β < . Applications are made to the study of chains of submodules of a module over an associative ring.     

Ranks of zero patterns and sign patterns

Let F be a field with at least three elements. Zero patterns P such that all matrices over F with pattern P have the same rank are characterized. Similar results are proven for sign patterns. These results are applied to answering two open questions on conditions for formal nonsingularity of a pattern P, as well as to proving a sufficient condition on P such that all matrices over F with pattern P have the same height characteristic.     

Balanced partitions of two sets of points in the plane

We prove the following theorem. Let m≥2 and q≥1 be integers and let S and T be two disjoint sets of points in the plane such that no three points of ST are on the same line, |S|=2q and |T|=mq. Then ST can be partitioned into q disjoint subsets P₁,P₂,…,P_q satisfying the following two conditions: (i) conv(P_i)∩conv(P_j)=φ for all 1≤i<j≤q, where conv(P_i) denotes the convex hull of P_i; and (ii) |P_i∩S|=2 and |P_i∩T|=m for all 1≤i≤q.     

On the P4-components of graphs

Two edges are called P₄-adjacent if they belong to the same P₄ (chordless path on four vertices). P₄-components, in our terminology, are the equivalence classes of the transitive closure of the P₄-adjacency relation. In this paper, new results on the structure of P₄-components are obtained. On the one hand, these results allow us to improve the complexity of orienting P₄-comparability graphs and of recognizing P₄-indifference graphs from O(n⁵) and O(n⁶) to O(m²). On the other hand, by combining the modular decomposition with the substitution of P₄-components, a new unique tree representation for arbitrary graphs is derived which generalizes the homogeneous decomposition introduced by Jamison and Olariu (SIAM J. Discrete Math. 8 (1995) 448–463).     

Homeomorphs and amallamorphs of the Petersen graph

Let P be the Petersen graph. The main results of this paper are the discovery of infinite families of chromatically equivalent pairs of P homeomorphs and the discovery of infinite families of flow equivalent pairs of P amallamorphs. In particular, three families of P homeomorphs with 8 parameters, five families with 7 parameters and many families with fewer parameters are obtained. Also one family of P amallamorphs with 9 parameters, three families with 7 parameters, seven families with 6 parameters and many families with fewer parameters are obtained.     

Generalized P(N)-graded Lie superalgebras

We generalize the P(N)-graded Lie superalgebras of Martinez-Zelmanov. This generalization is not so restrictive but suffcient enough so that we are able to have a classification for this generalized P(N)-graded Lie superalgebras. Our result is that the generalized P(N)-graded Lie super-algebra L is centrally isogenous to a matrix Lie superalgebra coordinated by an associative superalgebra with a super-involution. Moreover, L is P(N)-graded if and only if the coordinate algebra R is commutative and the super-involution is trivial. This recovers Martinez-Zelmanov's theorem for type P(N). We also obtain a generalization of Kac's coordinatization via Tits-Kantor-Koecher construction. Actually, the motivation of this generalization comes from the Fermionic-Bosonic module construction.     

Multiparameter spectral theory of a separating operator system

We define the spatial numerical range V[P] of the multiparameter system P(λ), and establish a connection between V[P] and the joint spatial numerical range of a separating operator system.     

On a straight-line embedding problem of graphs

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane in general position. A straight-line embedding of G onto P is an embedding of G onto whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.     

More examples on ordered set reconstruction

We show that there are nonisomorphic ordered sets P and Q that have the same maximal and minimal decks and a rank k such that there is a map B from the elements of rank k in P to the elements of rank k in Q such that P{x} is isomorphic to Q{B(x)} for all x of rank k in P. The examples are preceded by a criterion as to when two nonisomorphic ordered sets will have a rank k and a map B as above.     

Three problems about simple polygons

We give three related algorithmic results concerning a simple polygon P:

1. Improving a series of previous work, we show how to find a largest pair of disjoint congruent disks inside P in linear expected time.

2. As a subroutine for the above result, we show how to find the convex hull of any given subset of the vertices of P in linear worst-case time.

3. More generally, we show how to compute a triangulation of any given subset of the vertices or edges of P in almost linear time.

Finite p-groups All of Whose Minimal Nonabelian Subgroups are Nonmetacyclic of Order p3

Assume p is an odd prime. We investigate finite p-groups all of whose minimal nonabelian subgroups are of order p³. Let P₁-groups denote the p-groups all of whose minimal nonabelian subgroups are nonmetacyclic of order p³. In this paper, the P₁-groups are classified, and as a by-product, we prove the Hughes' conjecture is true for the P₁-groups.     

Rotational polygon overlap minimization and compaction

An effective and fast algorithm is given for rotational overlap minimization: given an overlapping layout of polygons P₁, P₂, P₃, …, P_k in a container polygon Q, translate and rotate the polygons to diminish their overlap to a local minimum. A (local) overlap minimum has the property that any perturbation of the polygons increases the overlap. Overlap minimization is modified to create a practical algorithm for compaction: starting with a non-overlapping layout in a rectangular container, plan a non-overlapping motion that diminishes the length or area of the container to a local minimum. Experiments show that both overlap minimization and compaction work well in practice and are likely to be useful in industrial applications.     

Language-theoretic complexity of disjunctive sequences

A sequence over an alphabet ∑ is called disjunctive if it contains all possible finite strings over ∑ as its substrings. Disjunctive sequences have been recently studied in various contexts. They abound in both category and measure senses. In this paper we measure the complexity of a sequence x by the complexity of the language P(x) consisting of all prefixes of x. The languages P(x) associated to disjunctive sequences can be arbitrarily complex. We show that for some disjunctive numbers x the language P(x) is context-sensitive, but no language P(x) associated to a disjunctive number can be context-free. We also show that computing a disjunctive number x by rationals corresponding to an infinite subset of P(x) does not decrease the complexity of the procedure, i.e. if x is disjunctive, then P(x) does not have an infinite context-free subset. This result reinforces, in a way, Chaitin's thesis (1969) according to which perfect sets, i.e. sets for which there is no way to compute infinitely many of its members essentially better (simpler/quicker) than computing the whole set, do exist. Finally we prove the existence of the following language-theoretic complexity gap: There is no x ε ∑^w such that P(x) is context-free but not regular. If S(x), the set of all finite substrings of a sequence x ε ∑^w, is slender, then the set of all prefixes of x is regular, that is P(x) is regular if and only if S(x) is slender.     

Siegmund Duality for Continuous Time Markov Chains on ℤ<Stack><Subscript>+</Subscript><Superscript>d</Superscript></Stack>

For the continuous time Markov chain with transition function P(t) on Z₊^d, we give the necessary and sufficient conditions for the existence of its Siegmund dual with transition function P(t). If Q, the q-matrix of P(t), is uniformly bounded, we show that the Siegmund dual relation can be expressed directly in terms of q-matrices, and a sufficient condition under which the Q-function is the Siegmund dual of some Q-function is also given.     

On Some Properties of Convex Matrix Sets Characterized by P -Matrices and Block P -Matrices

In this paper, we consider convex sets of real matrices and establish criteria characterizing these sets with respect to certain matrix properties of their elements. In particular, we deal with convex sets of P-matrices, block P-matrices and M-matrices, nonsingular and full rank matrices, as well as stable and Schur stable matrices. Our results are essentially based on the notion of a block P-matrix and extend and generalize some recently published results on this topic.     

On guarding the vertices of rectilinear domains

We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is NP-hard. For the first two proofs (i.e., vertex guards and boundary guards), we construct a reduction from minimum piercing of 2-intervals. The third proof is somewhat simpler; it is obtained by adapting a known reduction from minimum line cover.

We also consider the problem of guarding the vertices of a 1.5D rectilinear terrain. We establish an interesting connection between this problem and the problem of computing a minimum clique cover in chordal graphs. This connection yields a 2-approximation algorithm for the guarding problem.     

Some closed form formulae for the intersection of two special matrices under the star order

In this note we present closed form formulae for the intersection A ∧ B under the star order, for certain pairs of special matrices. In particular, it is shown that for two m×n partial isometries P and QP∧Q=P[I-(I-P^*Q)^†(I-P^*Q)]. Some further possible representations for P∧Q are considered.