Some varieties and convexities generated by fractal lattices

We introduce definitions of semifractal, 0–1-fractal, quasifractal and fractal lattices. A variety generated by a fractal lattice is called fractal generated, with analogous terminology for the other variants. We show that a semifractal generated nondistributive lattice variety cannot be of residually finite length. This easily implies that there are exactly continuously many lattice varieties which are not semifractal generated. On the other hand, for each prime field F, the variety generated by all subspace lattices of vector spaces over F is shown to be fractal generated. These countably many varieties and the class of all distributive lattices are the only known fractal generated lattice varieties at present. Four distinct countable distributive fractal lattices are given each of which generates . After showing that each lattice can be embedded in a quasifractal, continuously many quasifractals are given each of which has cardinality and generates the variety of all lattices. Semifractal considerations are applied to construct examples of convexities that include no minimal convexity, thus answering a question of Jakubík. (A convexity is a class of lattices closed under taking homomorphic images, convex sublattices and direct products, a notion due to Ervin Fried.) This research was partially supported by the NFSR of Hungary (OTKA), grant no. T 049433 and K 60148.     

A Cayley theorem for distributive lattices

A Cayley-like representation theorem for distributive lattices is proved. Support of the research of the first author by the Czech Government Research Project MSM 6198959214 is gratefully acknowledged.     

Avoidable structures, I: Finite ordered sets, semilattices and lattices

We find all finite unavoidable ordered sets, finite unavoidable semilattices and finite unavoidable lattices. While working on this paper, the second and third authors were supported by US NSF grant DMS-0604065. The second author was also supported by the Grant Agency of the Czech Republic, grant #201/05/0002 and by the institutional grant MSM0021620839 financed by MSMT.     

Semidirect products of lattices

The semidirect product of lattices is a lattice analogue of the semidirect product of groups. In this article we introduce this construction, show some basic facts and study a class of lattices closed under semidirect products. We also generalise this notion presenting the semidirect product of semilattices. Received February 22, 2005; accepted in final form August 29, 2006.     

Sums, products and negations of contexts and complete lattices

In Formal Concept Analysis, one associates with every context its concept lattice , and conversely, with any complete lattice L the standard context L, constituted by the join-irreducible elements as ‘objects’, the meet-irreducible elements as ‘attributes’, and the incidence relation induced by the lattice order. We investigate the effect of the operators and on various (finite or infinite) sum and product constructions. The rules obtained confirm the ‘exponential’ behavior of and the ‘logarithmic’ behavior of with respect to cardinal operations but show a ‘linear’ behavior on ordinal sums. We use these results in order to establish several forms of De Morgan’s law for the lattice-theoretical negation operator, associating with any complete lattice the concept lattice of the complementary standard context. Received February 7, 2001; accepted in final form January 6, 2006.     

Avoidable structures, II: Finite distributive lattices and nicely structured ordered sets

Let be the ordered set of isomorphism types of finite distributive lattices, where the ordering is by embeddability. We characterize the order ideals in that are well-quasi-ordered by embeddability, and thus characterize the members of that belong to at least one infinite anti-chain in . While working on this paper, the second and third authors were supported by US NSF grant DMS-0604065. The second author was also supported by the Grant Agency of the Czech Republic, grant #201/05/0002 and by the institutional grant MSM0021620839 financed by MSMT.     

Orthocomplemented lattices with a symmetric difference

Modelling an abstract version of the set-theoretic operation of symmetric difference, we first introduce the class of orthocomplemented difference lattices (). We then exhibit examples of ODLs and investigate their basic properties finding, for instance, that any ODL induces an orthomodular lattice (OML) but not all OMLs can be converted to ODLs. We then analyse an appropriate version of ideals and valuations in ODLs and show that the set-representable ODLs form a variety. We finally investigate the question of constructing ODLs from Boolean algebras and obtain, as a by-product, examples of ODLs that are not set-representable but that “live” on set-representable OMLs. Received April 10, 2007; accepted in final form February 12, 2008.     

Characterization of Amalgamated Free Blocks of a Graph von Neumann Algebra

We identify two noncommutative structures naturally associated with countable directed graphs. They are formulated in the language of operators on Hilbert spaces. If G is a countable directed graphs with its vertex set V(G) and its edge set E(G), then we associate partial isometries to the edges in E(G) and projections to the vertices in V(G). We construct a corresponding von Neumann algebra as a groupoid crossed product algebra of an arbitrary fixed von Neumann algebra M and the graph groupoid induced by G, via a graph-representation (or a groupoid action) α. Graph groupoids are well-determined (categorial) groupoids. The graph groupoid of G has its binary operation, called admissibility. This has concrete local parts , for all e ∈ E(G). We characterize of , induced by the local parts of , for all e ∈ E(G). We then characterize all amalgamated free blocks of . They are chracterized by well-known von Neumann algebras: the classical group crossed product algebras , and certain subalgebras (M) of operator-valued matricial algebra . This shows that graph von Neumann algebras identify the key properties of graph groupoids. Received: December 20, 2006. Revised: March 07, 2007. Accepted: March 13, 2007.     

The reflexivity of a Segre product of projective varieties

We study the reflexivity of a Segre product of a projective space and a projective variety Y, and give a criterion for to be reflexive in terms of m, the dimension of Y, the rank of the general Hessian of Y and the characteristic of the ground field. Our study is closely related to a question raised by Kleiman and Piene on the relationship between the conormal map and the Gauss map.     

On the semidistributivity of elements in weak congruence lattices of algebras and groups

Weak congruence lattices and semidistributive congruence lattices are both recent topics in universal algebra. This motivates the main result of the present paper, which asserts that a finite group G is a Dedekind group if and only if the diagonal relation is a join-semidistributive element in the lattice of weak congruences of G. A variant in terms of subgroups rather than weak congruences is also given. It is pointed out that no similar result is valid for rings. An open problem and some results on the join-semidistributivity of weak congruence lattices are also included. This research of the second and third authors was partially supported by Serbian Ministry of Science and Environment, Grant No. 144011 and by the Provincial Secretariat for Science and Technological Development, Autonomous Province of Vojvodina, grant ”Lattice methods and applications”.     

Orthocomplemented lattices in ordered groups

On a partially ordered set G the orthogonality relation is defined by incomparability and is a complete orthocomplemented lattice of double orthoclosed sets. We will prove that the atom space of the lattice has the same order structure as G. Thus if G is a partially ordered set (an ordered group, or an ordered vector space), then is a canonically partially ordered set (an ordered quotient group, or an ordered quotient vector space, respectively). We will also prove: if G is an ordered group with a positive cone P, then the lattice has the covering property iff , where g is an element of G and M is the intersection of all maximal subgroups contained in . Received August 1, 2006; accepted in final form May 29, 2007.     

Quantitative linear independence of an infinite product and its derivatives

We establish measures for the rational linear independence of 1 and the values of the product and its derivatives at finitely many rational points, q ≠ 0,±1 being a fixed integer. This is a quantitative improvement upon Bézivin’s very recent result in this journal. In contrast to his procedure, we use the method of Padé approximations of the second kind to get the above-mentioned improvement, some generalizations, and several irrationality measures.     

Infinite highly connected planar graphs of large girth

We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected.     

The superstar packing problem

Hell and Kirkpatrick proved that in an undirected graph, a maximum size packing by a set of non-singleton stars can be found in polynomial time if this star-set is of the form {S ₁, S ₂, ..., S _k } for some k∈ℤ₊ (S _i is the star with i leaves), and it is NP-hard otherwise. This may raise the question whether it is possible to enlarge a set of stars not of the form {S ₁, S ₂, ..., S _k } by other non-star graphs to get a polynomially solvable graph packing problem. This paper shows such families of depth 2 trees. We show two approaches to this problem, a polynomial alternating forest algorithm, which implies a Berge-Tutte type min-max theorem, and a reduction to the degree constrained subgraph problem of Lovász. Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No. 504438.     

A note on a spanning 3-tree

A tree T is called a k-tree, if the maximum degree of T is at most k. In this paper, we prove that if G is an n-connected graph with independence number at most n + m + 1 (n≥1,n≥m≥0), then G has a spanning 3-tree T with at most m vertices of degree 3.     

Maximal Abelian von Neumann Algebras and Toeplitz Operators with Separately Radial Symbols

This paper mainly concerns abelian von Neumann algebras generated by Toeplitz operators on weighted Bergman spaces. Recently a family of abelian w^*-closed Toeplitz algebras has been obtained (see [5,6,7,8]). We show that this algebra is maximal abelian and is singly generated by a Toeplitz operator with a “common” symbol. A characterization for Toeplitz operators with radial symbols is obtained and generalized to the high dimensional case. We give several examples for abelian von Neumann algebras in the case of high dimensional weighted Bergman spaces, which are different from the one dimensional case.     

Subdirect products of hereditary congruence lattices

A congruence lattice L of an algebra A is called power-hereditary if every 0-1 sublattice of Lⁿ is the congruence lattice of an algebra on Aⁿ for all positive integers n. Let A and B be finite algebras. We prove

On the measure of intersecting families,uniqueness and stability

Let t≥1 be an integer and let A be a family of subsets of {1,2,…,n} every two of which intersect in at least t elements. Identifying the sets with their characteristic vectors in {0,1} ⁿ we study the maximal measure of such a family under a non uniform product measure. We prove, for a certain range of parameters, that the t-intersecting families of maximal measure are the families of all sets containing t fixed elements, and that the extremal examples are not only unique, but also stable: any t-intersecting family that is close to attaining the maximal measure must in fact be close in structure to a genuine maximum family. This is stated precisely in Theorem 1.6. We deduce some similar results for the more classical case of Erdős-Ko-Rado type theorems where all the sets in the family are restricted to be of a fixed size. See Corollary 1.7. The main technique that we apply is spectral analysis of intersection matrices that encode the relevant combinatorial information concerning intersecting families. An interesting twist is that part of the linear algebra involved is done over certain polynomial rings and not in the traditional setting over the reals. A crucial tool that we use is a recent result of Kindler and Safra [22] concerning Boolean functions whose Fourier transforms are concentrated on small sets. Research supported in part by the Israel Science Foundation, grant no. 0329745.     

Terms that are self-dual in Boolean algebras but not in MO 2

An absorption law is an identity of the form p = x. The ternary function x+y+z (ring addition) in Boolean algebras satisfies three absorption laws in two variables. If a term satisfies these three identities in a variety, it is called a minority term for that variety. We construct a minority term p for orthomodular lattices such the identity defines Boolean algebras modulo orthomodular lattices. (The dual of p is denoted by .) Consequently, having a unique minority term function characterizes Boolean algebras among orthomodular lattices. Our main result generalizes this example to arbitrary arity and arbitrary consistent sets of 2-variable absorption laws. Presented by J. Berman.