Congruence lattices ofp-algebras

T. Kartriák proved the following theorem:Every finite distributive lattice is the congruence lattice of a finite p-algebra. We provide a short proof, and a generalization, of this result.Presented by J. Berman.The research of the first author was supported by the NSERC of Canada.The research of the second author was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1903.     

Maximal Local Time of a <Emphasis Type="Italic">d</Emphasis>-dimensional Simple Random Walk on Subsets

Strong theorems are given for the maximal local time on balls and subspaces for the d-dimensional simple symmetric random walk.Endre Csáki - Research supported by the Hungarian National Foundation for Scientific Research, Grant No. T 037886 and T 043037.Pál Révész - Research supported by a PSC CUNY Grant, No. 65685-0034.     

On additive functionals of Markov chains

Let{S _n } _n=0 ^∞ be a Harris-recurrent Markov chain on a measurable state space. We prove strong approximation results for the additive functionals . Research supported by the Hungarian National Foundation for Scientific Research, Grant No. 1905. Mathematical Institute of the Hungarian Academy of Sciences, Budapest, P.O.B. 127, H-1364, Hungary. Research supported by an NSERC Canada Grant, Carleton University. Department of Mathematics and Statistics, Carleton University, Ottawa, Canada K1S 5B6.     

An upper bound on the number of planarK-sets

Given a setS ofn points, a subsetX of sizek is called ak-set if there is a hyperplane that separatesX fromS–X. We prove thatO(nk/log*k) is an upper bound for the number ofk-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log*k.The research of J. Pach was supported in part by NSF Grant CCR-8901484 and by Grant OTKA-1418 from the Hungarian Foundation for Scientific Research. The research of W. Steiger and E. Szemerédi was supported in part by NSF Grant CCR-8902522. All authors express gratitude to the NSF DIMACS Center at Rutgers.     

Sufficient Optimality Criterion for Linearly Constrained,Separable Concave Minimization Problems

A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimality criterion is based on the sensitivity analysis of the relaxed linear programming problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive.In the Phillips and Rosen paper (Ref. 1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimality of the current basic solution.The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithms developed for linearly-constrained concave minimization problems.This research was supported by a Bolyai János Research Fellowship BO/00334/00 of the Hungarian Academy of Science and by the Hungarian Scientific Research Foundation, Grant OTKA T038027.     

On Constantive Simple and Order-Primal Algebras

A finite algebra is said to be order-primal if its clone of all term operations is the set of all operations defined on A which preserve a given partial order ≤ on A. In this paper we study algebraic properties of order-primal algebras for connected ordered sets (A; ≤). Such order-primal algebras are constantive, simple and have no non-identical automorphisms. We show that in this case cannot have only unary fundamental operations or only one at least binary fundamental operation. We prove several properties of the varieties and the quasi-varieties generated by constantive and simple algebras and apply these properties to order-primal algebras. Further, we use the properties of order-primal algebras to formulate new primality criteria for finite algebras.* Research supported by the Hungarian research grant No. TO34137 and by the János Bolyai grant.** Research supported by the Thailand Research Fund.     

Aronszajn null and Gaussian null sets coincide

We prove that in every separable Banach space the σ ideals of Aronszajn null sets, Gaussian null sets and cube null sets coincide. Research supported by the Hungarian National Foundation for Scientific Research Grant No. T019476 and FKFP Grant 0189/1997.     

A uniform refinement property for congruence lattices

The Congruence Lattice Problem asks whether every algebraic distributive lattice is isomorphic to the congruence lattice of a lattice. It was hoped that a positive solution would follow from E. T. Schmidt's construction or from the approach of P. Pudlák, M. Tischendorf, and J. Tuma. In a previous paper, we constructed a distributive algebraic lattice with compact elements that cannot be obtained by Schmidt's construction. In this paper, we show that the same lattice cannot be obtained using the Pudlák, Tischendorf, Tuma approach.

The basic idea is that every congruence lattice arising from either method satisfies the Uniform Refinement Property, that is not satisfied by our example. This yields, in turn, corresponding negative results about congruence lattices of sectionally complemented lattices and two-sided ideals of von Neumann regular rings.

     

On minimal simple lattices

The class of simple lattices, excluding the two-element lattice, is preordered by placing L₀L₁ iff L₀ belongs to the variety generated by L₁. We prove that the finite simple lattices minimal under this pre-ordering generate the variety of all lattices. We construct infinite simple lattices minimal under the ordering, and others that contain, in the sense of the ordering, no minimal simple lattices.Presented by G. McNulty.Research supported by National Science Foundation Grant DMS 89 04014.     

Global solutions of stochastic 2D Navier-Stokes equations with Lévy noise

In this paper, we prove the global existence and uniqueness of the strong and weak solutions for 2D Navier-Stokes equations on the torus perturbed by a Lévy process. The existence of invariant measure of the solutions are proved also. This work was supported by National Basic Research Program of China (Grant No. 2006CB8059000), Science Fund for Creative Research Groups (Grant No. 10721101), National Natural Science Foundation of China (Grant Nos. 10671197, 10671168), Science Foundation of Jiangsu Province (Grant Nos. BK2006032, 06-A-038, 07-333) and Key Lab of Random Complex Structures and Data Science, Chinese Academy of Sciences     

On a characterization of distributive lattices by the betweenness relation

We construct an example of a ternary structure satisfying certain conditions due to M. Kolibiar, which is not a betweenness relation of any lattice. This answers a question posed by J. Hedlíková and T. Katriák.Dedicated to the memory of Alan DayPresented by J. Sichler.Supported by GA SAV Grant 362/92.     

The local time of iterated Brownian motion

We define and study the local time process {L ^*(x,t);x¹,t0} of the iterated Brownian motion (IBM) {H(t):=W ₁(|W ₂ (t)|); t0}, whereW ₁(·) andW ₂(·) are independent Wiener processes.Research supported by Hungarian National Foundation for Scientific Research, Grant No. T 016384.Research supported by an NSERC Canada Grant at Carleton University, Ottawa.Research supported by a PSC CUNY Grant, No. 6-66364.     

Minimally k-Edge-Connected Directed Graphs of Maximal Size

Let D=(V,E) be a minimally k-edge-connected simple directed graph. We prove that there is a function f(k) such that |V|f(k) implies |E|2k(|V|–k). We also determine the extremal graphs whose size attains this upper bound.Basic Research in Computer Science, funded by the Danish National Research Foundation.Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization, and the Hungarian Scientific Research Fund grant No. F034930, T037547, and FKFP grant No. 0143/2001. Part of this research was done when the second author visited BRICS, University of Aarhus, Denmark.     

Radicals coinciding with the von Neumann regular radical on artinian rings

We study radicals which coincide on artinian rings with Jacobson semisimple rings or equivalently with von Neumann regular rings. Exact lower and upper bounds for strong coincidence are given. For weak coincidence the exact lower bound is that for strong coincidence. We determine the smallest homomorphically closed class which contains all radicals coinciding in the weak sense with the von Neumann regular radical on artinian rings, but we do not know even the existence of the upper bound for weak coincidence. If a radical coincides with the von Neumann regular radical on artinian rings in the strong sense, then (A) is a direct summand inA for every aritian ringA.Research carried out within the Austro-Hungarian Bilateral Intergovernmental Cooperation Program A-31. Research partially supported by Hungarian National Foundations for Scientific Research Grant No. T4265The second author gratefully acknowledges the support of the Carnegie Trust for Universities of Scotland     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.     

A structural characterization of non-Arguesian lattices

This is the first of a planned series of papers on the structure of non-Arguesian modular lattices. Apart from the (subspace lattices of) non-Arguesian projective planes, the best known examples of such lattices are obtained via the Hall-Dilworth construction by badly gluing together two projective planes of the same order. Our principal result shows that every non-Arguesian modular lattice L retains some of the flavor of these examples: There exist in the ideal lattice of L 20 intervals, not necessarily distinct, that form non-degenerate projective plains, and 10 points and 10 lines in these planes that constitute in a natural sense a classical non-Arguesian configuration.Research supported by NSERC Operating Grant A8190.Research supported by NSF Grant DMS-8300107.     

A new characterization of convex plates of constant width

A convex plate DR ² of diameter 1 is of constant width 1 if and only if any two perpendicular intersecting chords have total length 1.Research (partially) supported by Hungarian National Foundation for Scientific Research, Grant No. 1238.     

On isotone functions with the Substitution Property in distributive lattices

A universal algebra isaffine complete if all functions satisfying the Substitution Property are polynomials (composed of the basic operations and the elements of the algebra). In 1962, the first author proved that a bounded distributive lattice is affine complete if and only if it does not contain a proper Boolean interval. Recently, M. Ploica generalized this result to arbitrary distributive lattices.In this paper, we introduce a class of functions on a latticeL, we call themID-polynomials, that derive from polynomials on the ideal lattice (resp., dual ideal lattice) ofL; they are isotone functions and satisfy the Substitution Property. We prove that for a distributive latticeL, all unary functions with the Substitution Property are ID-polynomials if and only ifL contains no proper Boolean interval.The research of the first author was supported by the NSERC of Canada. The research of the second author was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1903.     

Equations in finite fields with restricted solution sets. II (Algebraic equations)

Generalizing earlier results, it is shown that if are “large” subsets of a finite field F _q , then the equations a + b = cd, resp. ab + 1 = cd can be solved with . Other algebraic equations with solutions restricted to “large” subsets of F _q are also studied. The proofs are based on character sum estimates proved in Part I of the paper. Research partially supported by the Hungarian National Foundation for Scientific Research, Grants No. T 043623, T 043631 and T 049693.