The universal partition theorem for oriented matroids

We consider realization spaces of a family of oriented matroids of rank three as point configurations in the affine plane. The fundamental problem arises as to which way these realization spaces partition their embedding space. The Universal Partition Theorem roughly states that such a partition can be as complicated as any partition of ℝ ⁿ into elementary semialgebraic sets induced by an arbitrary finite set of polynomials in ℤ[X]. We present the first proof of the Universal Partition Theorem. In particular, it includes the first complete proof of the so-called Universality Theorem. This work was supported by the Deutsche Forschungsgemeinschaft, Graduiertenkolleg “Analyse und Konstruktion in der Mathematik”.     

Characterization of Stochastic Viability of Any Nonsmooth Set Involving Its Generalized Contingent Curvature

Abstract

Thanks to the Stroock and Varadhan “Support Theorem” and under convenient regularity assumptions, stochastic viability problems are equivalent to invariance problems for control systems (also called tychastic viability), as it has been singled out by Doss in 1977 for instance. By the way, it is in this framework of invariance under control systems that problems of stochastic viability in mathematical finance are studied. The Invariance Theorem for control systems characterizes invariance through first‐order tangential and/or normal conditions whereas the stochastic invariance theorem characterizes invariance under second‐order tangential conditions. Doss's Theorem states that these first‐order normal conditions are equivalent to second‐order normal conditions that we expect for invariance under stochastic differential equations for smooth subsets. We extend this result to any subset by defining in an adequate way the concept of contingent curvature of a set and contingent epi‐Hessian of a function, related to the contingent curvature of its epigraph. This allows us to go one step further by characterizing functions the epigraphs of which are invariant under systems of stochastic differential equations. We shall show that they are (generalized) solutions to either a system of first‐order Hamilton‐Jacobi equations or to an equivalent system of second‐order Hamilton‐Jacobi equations.     

On N0-quasi-continuous exchange rings

An associative ring R with identity is said to have stable range one if for any a,b? R with aR + bR = R, there exists y ? R such that a + by is left (equivalently, right) invertible. The main results of this note are Theorem 2: A left or right continuous ring R has stable range one if and only if R is directly finite (i.e xy = 1 implies yx = 1 for all x,y ? R), Theorem 6: A left or right N ₀o-quasi-continuous exchange ring has stable range one if and only if it is directly finite, and Theorem 12: left or right N ₀-quasi-continuous strongly π-regular rings have stable range one. Theorem 6 generalizes a well-known result of Goodearl [10], which says that a directly finite, right N _o-continuous von Neumann regular ring is unit-regular     

A generalization of Rado's Theorem for almost graphical boundaries

In this paper, we prove a generalization of Rado's Theorem, a fundamental result of minimal surface theory, which says that minimal surfaces over a convex domain with graphical boundaries must be disks which are themselves graphical. We will show that, for a minimal surface of any genus, whose boundary is ``almost graphical' in some sense, that the surface must be graphical once we move sufficiently far from the boundary.     

On t-covers in finite projective spaces

A t-cover of the finite projective space PG(d,q) is a setS of t-dimensional subspaces such that any point of PG(d,q) is contained in at least one element ofS. In Theorem 1 a lower bound for the cardinality of a t-coverS in PG(d,q) is obtained and in Theorem 2 it is shown that this bound is best possible for all positive integers t,d and for any prime-power q.     

More proofs of menger's theorem

Four ways of proving Menger's Theorem by induction are described. Two of them involve showing that the theorem holds for a finite undirected graph G if it holds for the graphs obtained from G by deleting and contracting the same edge. The other two prove the directed version of Menger's Theorem to be true for a finite digraph D if it is true for a digraph obtained by deleting an edge from D.     

On Rado's Boundedness Conjecture

We prove that Rado's Boundedness Conjecture from Richard Rado's 1933 famous dissertation Studien zur Kombinatorik is true if it is true for homogeneous equations. We then prove the first nontrivial case of Rado's Boundedness Conjecture: if a₁,a₂, and a₃ are integers, and if for every 24-coloring of the positive integers (or even the nonzero rational numbers) there is a monochromatic solution to the equation a₁x₁+a₂x₂+a₃x₃=0, then for every finite coloring of the positive integers there is a monochromatic solution to a₁x₁+a₂x₂+a₃x₃=0.     

Tight embedding of modular lattices into partition lattices: progress and program

A famous Theorem of Pudlak and T?ma states that each finite lattice L occurs as sublattice of a finite partition lattice. Here we derive, for modular lattices L, necessary and sufficient conditions for cover-preserving embeddability. Aspects of our work relate to Bjarni Jónsson.     

A unified approach to known and unknown cases of Berge's conjecture

Berge's elegant dipath partition conjecture from 1982 states that in a dipath partition P of the vertex set of a digraph minimizing , there exists a collection C^k of k disjoint independent sets, where each dipath P∈P meets exactly min{|P|, k} of the independent sets in C. This conjecture extends Linial's conjecture, the Greene–Kleitman Theorem and Dilworth's Theorem for all digraphs. The conjecture is known to be true for acyclic digraphs. For general digraphs, it is known for k=1 by the Gallai–Milgram Theorem, for k?λ (where λis the number of vertices in the longest dipath in the graph), by the Gallai–Roy Theorem, and when the optimal path partition P contains only dipaths P with |P|?k. Recently, it was proved (Eur J Combin (2007)) for k=2. There was no proof that covers all the known cases of Berge's conjecture. In this article, we give an algorithmic proof of a stronger version of the conjecture for acyclic digraphs, using network flows, which covers all the known cases, except the case k=2, and the new, unknown case, of k=λ?1 for all digraphs. So far, there has been no proof that unified all these cases. This proof gives hope for finding a proof for all k.     

Matrices with prescribed row,column and block sums

The main result of the paper is Theorem 1. It concerns the sets of integral symmetric matrices with given block partition and prescribed row, column and block sums. It is shown that by interchanges preserving these sums we can pass from any two matrices, one from each set, to the other two ones falling close together as much as possible. One of the direct corollaries of Theorem 1 is substantiating the fact that any realization ofr-graphical integer-pair sequence can be obtained from any other one byr-switchings preserving edge degrees. This result is also of interest in connection with the problem of determinings-complete properties. In the special cases Theorem 1 includes a number of well-known results, some of which are presented.     

On maximal abelian subgroups in finite 2-groups

We determine here up to isomorphism the structure of any finite nonabelian 2-group G in which every two distinct maximal abelian subgroups have cyclic intersection. We obtain five infinite classes of such 2-groups (Theorem 1.1). This solves for p = 2 the problem Nr. 521 stated by Berkovich (in preparation). The more general problem Nr. 258 stated by Berkovich (in preparation) about the structure of finite nonabelian p-groups G such that A ∩ B = Z(G) for every two distinct maximal abelian subgroups A and B is treated in Theorems 3.1 and 3.2. In Corollary 3.3 we get a new result for an arbitrary finite 2-group. As an application of Theorems 3.1 and 3.2, we solve for p = 2 a problem of Heineken-Mann (Problem Nr. 169 stated in Berkovich, in preparation), classifying finite 2-groups G such that A/Z(G) is cyclic for each maximal abelian subgroup A (Theorem 4.1).      

FINITE REPLACEMENT AND FINITE HILBERT-STYLE AXIOMATIZABILITY

We define a property for varieties V, the f.r.p. (finite replacement property). If it applies to a finitely based V then V is strongly finitely based in the sense of [14], see Theorem 2. Moreover, we obtain finite axiomatizability results for certain propositional logics associated with V, in its generality comparable to well-known finite base results from equational logic. Theorem 3 states that each variety generated by a 2-element algebra has the f.r.p. Essentially this implies finite axiomatizability of a 2-valued logic in any finite language.     

有限域上n元n次方程只有零解的充要条件

本文研究了有限域上只有零解的n元n次方程的结构问题.利用对有限域上不可约多元多项式在其扩域中的分解特征的刻画,结合Chevalley定理,得到了有限域上n元n次方程只有零解的一个充要条件,并给出这类方程的一些新的具体构造.     

Functional equations on finite groups of substitutions

Motivated by some investigations of Babbage, we study a class of single variable functional equations. These are functional equations involving one unknown function and a finite set of known functions that form a group under the operation of composition. It turns out that the algebraic structure of a stabilizer determines the number of initial value conditions for the functional equation. In the proof of the main result, the Implicit Function Theorem and, when the stabilizer is nontrivial, the Global Existence and Uniqueness Theorem play a key role.     

VIP systems in partial semigroups

A VIP system is a polynomial-type generalization of the notion of an IP system, i.e., a set of finite sums. We extend the notion of VIP system to commutative partial semigroups and obtain an analogue of Furstenberg's central sets theorem for these systems which extends the polynomial Hales–Jewett Theorem of Bergelson and Leibman. Several Ramsey theoretic consequences, including the central sets theorem itself, are then derived from these results.     

Multiple Nontrivial Solutions for a Class of p-Laplacian Equations

In this paper a class of p-Laplacian equations are considered. The existence of five nontrivial solutions is stated. By the standard supersolution and subsolution method, we prove the existence of minimal positive solution and maximal negative solution in L ^∞(Ω). Furthermore, in virtue of the well-known Mountain-Pass Theorem and Second Deformation Theorem, we can give additional three nontrivial solutions, i.e., one positive solution, one negative solution and one sign-changing solution.     

Asymptotics of random partitions of a set

This paper contains two results on the asymptotic behavior of uniform probability measure on partitions of a finite set as its cardinality tends to infinity. The first one states that there exists a normalization of the corresponding Young diagrams such that the induced measure has a weak limit. This limit is shown to be a δ-measure supported by the unit square (Theorem 1). It implies that the majority of partition blocks have approximately the same length. Theorem 2 clarifies the limit distribution of these blocks. The techniques used can also be useful for deriving a range of analogous results. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 223, 1995, pp. 227–250. The paper is supported by International Science Foundation, grant MQV-100. Translated by Yu. Yakubovich     

Constructing pairs of dual bandlimited framelets with desired time localization

For sufficiently small translation parameters, we prove that any bandlimited function ψ, for which the dilations of its Fourier transform form a partition of unity, generates a wavelet frame with a dual frame also having the wavelet structure. This dual frame is generated by a finite linear combination of dilations of ψ with explicitly given coefficients. The result allows a simple construction procedure for pairs of dual wavelet frames whose generators have compact support in the Fourier domain and desired time localization. The construction is based on characterizing equations for dual wavelet frames and relies on a technical condition. We exhibit a general class of function satisfying this condition; in particular, we construct piecewise polynomial functions satisfying the condition.      

Isomorphism Classes of A-Hypergeometric Systems

Given a finite set A of integral vectors and a parameter vector, Gel'fand, Kapranov, and Zelevinskii defined a system of differential equations, called an A-hypergeometric (or a GKZ hypergeometric) system. Classifying the parameters according to the D-isomorphism classes of their corresponding A-hypergeometric systems is one of the most fundamental problems in the theory. In this paper we give a combinatorial answer for the problem under the assumption that the finite set A lies in a hyperplane off the origin, and illustrate it in two particularly simple cases: the normal case and the monomial curve case.     

Markov Chains with Positive Transitions Are Not Determined by Any p-Marginals

 We prove that if is a finite valued stationary Markov Chain with strictly positive probability transitions, then for any natural number p, there exists a continuum of finite valued non Markovian processes which have the p-marginal distributions of X and with positive entropy, whereas for an irrational rotation and essentially bounded real measurable function f with no zero Fourier coefficient on the unit circle with normalized Lebesgue measure, the process is uniquely determined by its three-dimensional distributions in the class of ergodic processes. We give also a family of Gaussian non-Markovian dynamical systems for which the symbolic dynamic associated to the time zero partition has the two-dimensional distributions of a reversible mixing Markov Chain. (Received 22 July 1999; in revised form 24 February 2000)