Global Rank Axioms for Poset Matroids

An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “global” version and a “pseudo-global” version. Some corresponding properties of combinatorial schemes are also obtained.     

Cyclic orders: Equivalence and duality

Cyclic orders of graphs and their equivalence have been promoted by Bessy and Thomassé’s recent proof of Gallai’s conjecture. We explore this notion further: we prove that two cyclic orders are equivalent if and only if the winding number of every circuit is the same in the two. The proof is short and provides a good characterization and a polynomial algorithm for deciding whether two orders are equivalent. We then derive short proofs of Gallai’s conjecture and a theorem “polar to” the main result of Bessy and Thomassé, using the duality theorem of linear programming, total unimodularity, and the new result on the equivalence of cyclic orders.     

Computability in structures representing a Scott set

Continuing work begun in [10], we utilize a notion of forcing for which the generic objects are structures and which allows us to determine whether these “generic” structures compute certain sets and enumerations. The forcing conditions are bounded complexity types which are consistent with a given theory and are elements of a given Scott set. These generic structures will “represent” this given Scott set, in the sense that the structure has a certain weak saturation property with respect to bounded complexity types in the Scott set. For example, if ? is a nonstandard model of PA, then ? represents the Scott set ? = n∈ω | ?⊧“the nth prime divides a” | a∈?. The notion of forcing yields two main results. The first characterizes the sets of natural numbers computable in all models of a given theory representing a given Scott set. We show that the characteristic function of such a set must be enumeration reducible to a complete existential type which is consistent with the given theory and is an element of the given Scott set. The second provides a sufficient condition for the existence of a structure ? such that ? represents a countable jump ideal and ? does not compute an enumeration of a given family of sets ?. This second result is of particular interest when the family of sets which cannot be enumerated is ? = Rep[Th(?)]. Under this additional assumption, the second result generalizes a result on TA [6] and on certain other completions of PA [10]. For example, we show that there also exist models of completions of ZF from which one cannot enumerate the family of sets represented by the theory. Received: 8 October 1997 / Published online: 25 January 2001     

Robinson forcing is not absolute

Robinson (or infinite model theoretic) forcing is studied in the context of set theory. The major result is that infinite forcing, genericity, and related notions are not absolute relative to ZFC. This answers a question of G. Sacks and provides a non-trivial example of a non-absolute notion of model theory. This non-absoluteness phenomenon is shown to be intrinsic to the concept of infinite forcing in the sense that any ZFC-definable set theory, relative to which forcing is absolute, has the flavor of asserting self-inconsistency. More precisely: IfT is a ZFC-definable set theory such that the existence of a standard model ofT is consistent withT, then forcing is not absolute relative toT. For example, if it is consistent that ZFC+ “there is a measureable cardinal” has a standard model then forcing is not absolute relative to ZFC+ “there is a measureable cardinal.” Some consequences: 1) The resultants for infinite forcing may not be chosen “effectively” in general. This answers a question of A. Robinson. 2) If ZFC is consistent then it is consistent that the class of constructible division rings is disjoint from the class of generic division rings. 3) If ZFC is consistent then the generics may not be axiomatized by a single sentence ofL _w/w. In Memoriam: Abraham Robinson     

Isomorphism of random walks

We show that any two aperiodic, recurrent random walks on the integers whose jump distributions have finite seventh moment, are isomorphic as infinite measure preserving transformations. The method of proof involved uses a notion of equivalence of renewal sequences, and the “relative” isomorphism of Bernoulli shifts respecting a common state lumping with the same conditional entropy. We also prove an analogous result for random walks on the two dimensional integer lattice.     

Hypothetical knowledge and counterfactual reasoning

Samet introduced a notion of hypothetical knowledge and showed how it could be used to capture the type of counterfactual reasoning necessary to force the backwards induction solution in a game of perfect information. He argued that while hypothetical knowledge and the extended information structures used to model it bear some resemblance to the way philosophers have used conditional logic to model counterfactuals, hypothetical knowledge cannot be reduced to conditional logic together with epistemic logic. Here it is shown that in fact hypothetical knowledge can be captured using the standard counterfactual operator “>” and the knowledge operator “K”, provided that some assumptions are made regarding the interaction between the two. It is argued, however, that these assumptions are unreasonable in general, as are the axioms that follow from them. Some implications for game theory are discussed.     

Free limits of forcing and more on Aronszajn trees

We prove that the Souslin Hypothesis does not imply “every Aron. (=Aronszajn) tree is special”. For this end we introduce variants of the notion “special Aron. tree”. We also introduce a limit of forcings bigger than the inverse limit, and prove it preserves properness and related notions not less than inverse limit, and the proof is easier in some respects. The result was announced in [9]. The author thanks Uri Avraham for detecting many errors.     

On growth and covering theorems of quasi-convex mappings in the unit ball of a complex banach space

A class of biholomorphic mappings named “quasi-convex mapping” is introduced in the unit ball of a complex Banach space. It is proved that this class of mappings is a proper subset of the class of starlike mappings and contains the class of convex mappings properly, and it has the same growth and covering theorems as the convex mappings. Furthermore, when the Banach space is confined to ℂⁿ, the “quasi-convex mapping” is exactly the “quasi-convex mapping of type A” introduced by K. A. Roper and T. J. Suffridge.     

Construction of pseudorandom binary lattices by using the multiplicative inverse

In an earlier work Hubert and the authors of this paper introduced and studied the notion of pseudorandomness of binary lattices. Later in another paper the authors gave a construction for a large family of “good” binary lattices by using the quadratic characters of finite fields. Here, a further large family of “good” binary lattices is constructed by using finite fields and the notion of multiplicative inverse.     

An Extension Principle for the Einstein-Vlasov System in Spherical Symmetry

We prove that “first singularities” in the non-trapped region of the maximal development of spherically symmetric asymptotically flat data for the Einstein-Vlasov system must necessarily emanate from the center. The notion of “first” depends only on the causal structure and can be described in the language of terminal indecomposable pasts (TIPs). This result suggests a local approach to proving weak cosmic censorship for this system. It can also be used to give the first proof of the formation of black holes by the collapse of collisionless matter from regular initial configurations. Communicated by Sergiu Klainerman submitted 15/11/04, accepted 17/02/05     

A homogenization approach to flashing ratchets

The paper continues the program of the authors to develop a mathematical framework to understand and characterize the notion of “asymmetric” potentials, which has been introduced to explain how molecular motors work, considering flashing ratchets, i.e., molecules diffusing in a potential with periodic switches. The mathematical model is a Fokker–Planck equation with a space–time periodic potential and diffusion of order of magnitude compatible with the period of the potential. After performing a homogenization analysis of the problem the “asymmetric” potentials are characterized by the property that the solution, which models the molecule density, concentrates on one end of the domain. Finally explicit examples are presented exhibiting that the concentration phenomena (motor effect) takes place are presented. The proof uses techniques from the theory of viscosity solutions for the Hamilton–Jacobi equation which, in the homogenization limit, defines the effective hamiltonian.     

No random reals in countable support iterations

We prove a preservation theorem for limit steps of countable support iterations of proper forcing notions whose particular cases are preservations of the following properties on limit steps: “no random reals are added”, “μ(Random(V))≠1”, “no dominating reals are added”, “Cohen(V) is not comeager”. Consequently, countable support iterations of σ-centered forcing notions do not add random reals. The work was supported by BRF of Israel Academy of Sciences and by grant GA SAV 365 of Slovak Academy of Sciences.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

PLS and dimension reduction for classification

Barker and Rayens (J Chemometrics 17:166–173, 2003) offered convincing arguments that partial least squares (PLS) is to be preferred over principal components analysis (PCA) when discrimination is the goal and dimension reduction is required, since at least with PLS as the dimension reduction tool, information involving group separation is directly involved in the structure extraction. In this paper the basic results in Barker and Rayens (J Chemometrics 17:166–173, 2003) are reviewed and some of their ideas and comparisons are illustrated on a real data set, something which Barker and Rayens did not do. More importantly, new results are introduced, including a formal proof for the superiority of PLS over PCA in the two-group case, as well as new connections between PLS for discrimination and an extended class of PLS-like techniques known as “oriented PLS” (OrPLS). In the latter case, a particularly simple subclass of OrPLS procedures, when used to achieve the dimension reduction, is shown to always produce a lower misclassification rate than when “ordinary” PLS is used for the same purpose.     

Compactifications of universal abelian threefolds with CM

We determine completions of semi-abelian degenerations of abelian threefolds with complex multiplication. This type of completion plays a crucial role in the determination of motivic decompositions of such degenerating families. To this end we generalize the notion of “relatively complete model” as introduced by Mumford, Faltings and Chai and explicitly compute it in the case at hand.     

Uniformly convex spaces,bead spaces,and equivalence conditions

The notion of a metric bead space was introduced in the preceding paper (L.Pasicki: Bead spaces and fixed point theorems, Topology Appl., vol. 156 (2009), 1811–1816) and it was proved there that every bounded set in such a space (provided the space is complete) has a unique central point. The bead spaces themselves can be considered in particular as natural extensions of convex sets in uniformly convex spaces. It appears that normed bead spaces are identical with uniformly convex spaces. On the other hand the “metric” approach leads to new elementary conditions equivalent to the uniform convexity. The initial part of the paper contains the proof that discus spaces (they seem to have a richer structure) are identical with bead spaces.     

On equivalent number fields with special Galois groups

In [12] and [13] Jack Sonn has introduced and studied a new notion of equivalence for number fields. In this note we show that “almost all” (cf. [14]) pairs of equivalent number fields are conjugate over ℚ, and we study equivalence classes of fields of prime degree.     

A Probabilistic Approach to Carne’s Bound

Carne’s bound is a sharp inequality controlling the transition probabilities for a discrete reversible Markov chain (Section 1). Its ordinary proof uses spectral techniques which look as efficient as miraculous. Here we present a new proof, comparing a “drift” for ways “out” and “back”, to get the gaussian part of the bound (Section 2), and using a conditioning technique to get the flight factor (Section 4). Moreover we show how our proof is more “supple” than Carne’s one and may generalize (Section 3.2).      

Associated families of pluriharmonic maps¶and isotropy

Like minimal surface immersions in 3-space, pluriharmonic maps into symmetric spaces allow a one-parameter family of isometric deformations rotating the differential (“associated family”); in fact, pluriharmonic maps are characterized by this property. We give a geometric proof of this fact and investigate the “isotropic” case where this family is constant. It turns out that isotropic pluriharmonic maps arise from certain holomorphic maps into flag manifolds. Further, we also consider higher dimensional generalizations of constant mean curvature surfaces which are K?hler submanifolds with parallel (1,1) part of their soecond fundamental form; under certain restrictions there are also characterized by having some kind of (“weak”) associated family. Examples where this family is constant arise from extrinsic K?hler symmetric spaces. Received: 8 July 1997     

On the Borel-Cantelli lemma

A new variant of the “divergent” part of the Borel-Cantelli lemma for events derived from a Markov chain is given. Further two applications are considered. One of the applications refers to the denumerable Markov chain and the second is a new proof of the “strong” theorem corresponding to the “arc sine law”.