A fully benzenoid system has a unique maximum cardinality resonant set

A benzenoid system is a 2-connected plane graph such that its each inner face is a regular hexagon of side length 1. A benzenoid system is Kekuléan if it has a perfect matching. Let P be a set of hexagons of a Kekuléan benzenoid system B. The set P is called a resonant set of B if the hexagons in P are pair-wise disjoint and the subgraph B−P (obtained by deleting from B the vertices of the hexagons in P) is either empty or has a perfect matching. It was shown (Gutman in Wiss. Z. Thechn. Hochsch. Ilmenau 29:57–65, 1983; Zheng and Chen in Graphs Comb. 1:295–298, 1985) that for every maximum cardinality resonant set P of a Kekuléan benzenoid system B, the subgraph B−P is either empty or has a unique perfect matching. A Kekuléan benzenoid system B is said to be fully benzenoid if there exists a maximum cardinality resonant set P of B, such that the subgraph B−P is empty. It is shown that a fully benzenoid system has a unique maximum cardinality resonant set, a well-known statement that, so far, has remained without a rigorous proof.     

On the<Emphasis Type="Italic">k</Emphasis>-systems of a simple polytope

Ak-system of the graphG _P of a simple polytopeP is a set of induced subgraphs ofG _P that shares certain properties with the set of subgraphs induced by thek-faces ofP. This new concept leads to polynomial-size certificates in terms ofG _P for both the set of vertex sets of facets and for abstract objective functions (AOF) in the sense of Kalai. Moreover, it is proved that an acyclic orientation yields an AOF if and only if it induces a unique sink on every 2-face.     

On the number of k-realizations of an ordered set

A k-realization of an ordered set P is a sequence of k linear orderings of the underlying set of P, whose intersection is (the order relation of) P. We determine the status of the number of k-realizations with respect to comparability invariance, and we show that among all orders on the set {1, 2, ..., n}, the antichain has the most k-realizations, for any k>1. The latter intuitively reasonable result rests ultimately on an observation related to comparability invariance for numbers of linear extensions.Research supported by ONR Contract N00014 85-K-0769.     

Analytic Hypoellipticity at Non-Symplectic Poisson-Treves Strata for Certain Sums of Squares of Vector Fields

We consider an operator P which is a sum of squares of vector fields with analytic coefficients. The operator has a non-symplectic characteristic manifold, but the rank of the symplectic form σ is not constant on Char P. Moreover the Hamilton foliation of the non-symplectic stratum of the Poisson-Treves stratification for P consists of closed curves in a ring-shaped open set around the origin. We prove that then P is analytic hypoelliptic on that open set. And we note explicitly that the local Gevrey hypoellipticity for P is G ^k+1 and that this is sharp.      

On Poset Boolean Algebras

Let (P,≤) be a partially ordered set. The poset Boolean algebra of P, denoted F(P), is defined as follows: The set of generators of F(P) is {x _p  : p∈P}, and the set of relations is {x _p ⋅x _q =x _p  : p≤q}. We say that a Boolean algebra B is well-generated, if B has a sublattice G such that G generates B and (G,≤ ^B |G) is well-founded. A well-generated algebra is superatomic. THEOREM 1. Let (P,≤) be a partially ordered set. The following are equivalent. (i) P does not contain an infinite set of pairwise incomparable elements, and P does not contain a subset isomorphic to the chain of rational numbers, (ii) F(P) is superatomic, (iii) F(P) is well-generated. The equivalence (i) ⇔ (ii) is due to M. Pouzet. A partially ordered set W is well-ordered, if W does not contain a strictly decreasing infinite sequence, and W does not contain an infinite set of pairwise incomparable elements. THEOREM 2. Let F(P) be a superatomic poset algebra. Then there are a well-ordered set W and a subalgebra B of F(W), such that F(P) is a homomorphic image of B. This is similar but weaker than the fact that every interval algebra of a scattered chain is embeddable in an ordinal algebra. Remember that an interval algebra is a special case of a poset algebra. This revised version was published online in June 2006 with corrections to the Cover Date.     

Extending a Partially Ordered Set: Links with its Lattice of Ideals

A well-known result of Bonnet and Pouzet bijectively links the set of linear extensions of a partial order P with the set of maximal chains of its lattice of ideals I(P). We extend this result by showing that there is a one-to-one correspondence between the set of all extensions of P and the set of all sublattices of I(P) which are chain-maximal in the sense that every chain which is maximal (for inclusion) in the sublattice is also maximal in the lattice.We prove that the absence of order S as a convex suborder of P is equivalent to the absence of I(S) as a convex suborder of I(P). Let S be a set of partial orders and let us call S-convex-free any order that does not contain any order of S as a convex suborder. We deduce from the previous results that there is a one-to-one correspondence between the set of S-convex-free extensions of P and the set of I(S)-convex-free chain-maximal sublattices of I(P). This can be applied to some classical classes of orders (total orders and in the finite case, weak orders, interval orders, N-free orders). In the particular case of total orders this gives as a corollary the result of Bonnet and Pouzet.     

A Sufficient Condition for the Existence of Large Empty Convex Polygons

   Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R ^d for each odd d≥ 3 .     

A Sufficient Condition for the Existence of Large Empty Convex Polygons

Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R ^d for each odd d≥ 3 .     

Compactness and subsets of ordered sets that meet all maximal chains

LetP be a chain complete ordered set. By considering subsets which meet all maximal chains, we describe conditions which imply that the space of maximal chains ofP is compact. The symbolsP ₁ andP ₂ refer to two particular ordered sets considered below. It is shown that the space of maximal chains (P) is compact ifP satisfies any of the following conditions: (i)P contains no copy ofP ₁ or its dual and all antichains inP are finite. (ii)P contains no properN and every element ofP belongs to a finite maximal antichain ofP. (iii)P contains no copy ofP ₁ orP ₂ and for everyx inP there is a finite subset ofP which is coinitial abovex. We also describe an example of an ordered set which is complete and densely ordered and in which no antichain meets every maximal chain.     

A GAME-THEORETIC PROOF OF ANALYTIC RAMSEY THEOREM

We give a simple game-theoretic proof of Silver's theorem that every analytic set is Ramsey. A set P of subsets of ω is called Ramsey if there exists an infinite set H such that either all infinite subsets of H are in P or all out of P. Our proof clarifies a strong connection between the Ramsey property of partitions and the determinacy of infinite games.     

Prime Orders All of Whose Prime Suborders Are Selfdual

Let P be an order on a set V. A subset A of V is autonomous in P if every element of V not in A is either less than or greater than or incomparable to all elements of A. The empty set, the singletons from V and the set V are autonomous sets and are called trivial. Call an order prime if all its autonomous sets are trivial. We give the complete list of all finite prime orders all of whose prime suborders are selfdual.     

There Are Not Too Many Magic Configurations

A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all points of P on l equals 1. We prove a conjecture of Murty from 1971 and show that if a set of n points P is a magic configuration, then P is in general position, or P contains n−1 collinear points, or P is a special configuration of 7 points. The research by Rom Pinchasi was supported by a Grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

The realizability of local loop spaces as manifolds

As an extension of earlier work, we show that every P-local loop space, where P is a set of primes, is homotopy equivalent to the P-localization of a compact, smooth, parallelizable manifold. A similar result is also proved for P-complete loop spaces. Received: February 2006     

Index sets for ω‐languages

An ω‐language is a set of infinite sequences (words) on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the languages, may enumerated as P₀, P₁, … and then an index set associated to a given property R (such as finiteness) of languages is just the set of e such that P_e has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language.     

Automorphisms and isotone self-maps of ordered sets with top and bottom

For an ordered setP letP ^P denote the set of all isotone self-maps on P, that is, all mapsf fromP toP such thatxy impliesf(x)f(y), and let Aut (P) the set of all automorphisms onP, that is, all bijective isotone self-maps inP ^P . We establish an inequality relating ¦P ^P ¦ and ¦Aut(P)¦ in terms of the irreducibles ofP. As a straightforward corollary, we show that Rival and Rutkowski's automorphism conjecture is true for lattices. It is also true for ordered sets with top and bottom whose covering graphs are planar.Supported in part by NSERC (Grant no. A2507).Supported under an NSERC International Research Fellowship.     

Optimization of multiple covering of a bounded set with circles

Numerical algorithms for the optimization of multiple covering of a bounded set G in the plane P with equal circles are proposed. The variants in which G is a connected bounded set in P or a finite set in P are considered. The circles may be centered at arbitrary points of G or at points belonging to a given set. Minimization of the radius of the given number of circles and minimization of the number of circles of a given radius are considered. Models and solution algorithms are described, and estimates of the solutions provided by most variants are given. Numerical results are presented.     

The Menger property for infinite ordered sets

It is shown that, if an ordered set P contains at most k pairwise disjoint maximal chains, where k is finite, then every finite family of maximal chains in P has a cutset of size at most k. As a corollary of this, we obtain the following Menger-type result that, if in addition, P contains k pairwise disjoint complete maximal chains, then the whole family, M (P), of maximal chains in P has a cutset of size k. We also give a direct proof of this result. We give an example of an ordered set P in which every maximal chain is complete, P does not contain infinitely many pairwise disjoint maximal chains (but arbitrarily large finite families of pairwise disjoint maximal chains), and yet M (P) does not have a cutset of size <x, where x is any given (infinite) cardinal. This shows that the finiteness of k in the above corollary is essential and disproves a conjecture of Zaguia.     

The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

Pseudozero Set of Real Multivariate Polynomials

The pseudozero set of a system P of polynomials in n variables is the subset of C ⁿ consisting of the union of the zeros of all polynomial systems Q that are near to P in a suitable sense. This concept arises naturally in Scientific Computing where data often have a limited accuracy. When the polynomials of the system are polynomials with complex coefficients, the pseudozero set has already been studied. In this paper, we focus on the case where the polynomials of the system have real coefficients and such that all the polynomials in all the perturbed polynomial systems have real coefficients as well. We provide an explicit definition to compute this pseudozero set. At last, we analyze different methods to visualize this set.      

On the Jump Number of Lexicographic Sums of Ordered Sets

Let Q be the lexicographic sum of finite ordered sets Q _x over a finite ordered set P. For some P we can give a formula for the jump number of Q in terms of the jump numbers of Q _x and P, that is, , where s(X) denotes the jump number of an ordered set X. We first show that where w(X) denotes the width of an ordered set X. Consequently, if P is a Dilworth ordered set, that is, s(P) = w(P)–1, then the formula holds. We also show that it holds again if P is bipartite. Finally, we prove that the lexicographic sum of certain jump-critical ordered sets is also jump-critical.