Extension theorems for linear lattices with positive algebraic basis

An ordered linear spaceV with positive wedgeK is said to satisfy extension property (E1) if for every subspaceL ₀ ofV such thatL ₀ ∩K is reproducing inL ₀, and every monotone linear functionalf ₀ defined onL ₀,f ₀ has a monotone linear extension to all ofV. A linear latticeX is said to satisfy extension property (E2) if for every sublatticeL ofX, and every linear functionalf defined onL which is a lattice homomorphism,f has an extensionf′ to all ofX which is also a linear functional and a lattice homomorphism. In this paper it is shown that a linear lattice with a positive algebraic basis has both extension property (E1) and (E2). In obtaining this result it is shown that the linear span of a lattice idealL and an extremal element not inL is again a lattice ideal. (HereX does not have to have a positive algebraic basis.) It is also shown that a linear lattice which possesses property (E2) must be linearly and lattice isomorphic to a functional lattice. An example is given of a function lattice which has property (E2) but does not have a positive algebraic basis. Yudin [12] has shown a reproducing cone in ann-dimensional linear lattice to be the intersection of exactlyn half-spaces. Here it is shown that the positive wedge in ann-dimensional archimedean ordered linear space satisfying the Riesz decomposition property must be the intersection ofn half-spaces, and hence the space must be a linear lattice with a positive algebraic basis. The proof differs from those given for the linear lattice case in that it uses no special techniques, only well known results from the theory of ordered linear space.     

Codimension and pseudometric in co-Heyting algebras

In this paper, we introduce a notion of dimension and codimension for every element of a bounded distributive lattice L. These notions prove to have a good behavior when L is a co-Heyting algebra. In this case the codimension gives rise to a pseudometric on L which satisfies the ultrametric triangle inequality. We prove that the Hausdorff completion of L with respect to this pseudometric is precisely the projective limit of all its finite dimensional quotients. This completion has some familiar metric properties, such as the convergence of every monotonic sequence in a compact subset. It coincides with the profinite completion of L if and only if it is compact or equivalently if every finite dimensional quotient of L is finite. In this case we say that L is precompact. If L is precompact and Hausdorff, it inherits many of the remarkable properties of its completion, specially those regarding the join/meet irreducible elements. Since every finitely presented co-Heyting algebra is precompact Hausdorff, all the results we prove on the algebraic structure of the latter apply in particular to the former. As an application, we obtain the existence for every positive integers n, d of a term t _{n, d} such that in every co-Heyting algebra generated by an n-tuple a, t _{n, d} (a) is precisely the maximal element of codimension d.     

Further characterizations of cubic lattice graphs

A cubic lattice graph with characteristic n is a graph whose points can be identified with the ordered triplets on n symbols and two points are adjacent whenever the corresponding triplets have two coordinates in common. An L₂ graph is a graph whose points can be identified with the ordered pairs on n symbols such that two points are adjacent if and only if the corresponding pairs have a common coordinate. The main result of this paper is two new characterizations and shows the relation between cubic lattice and L₂ graphs. The main result also suggests a conjecture concerning the characterization of interchange graphs of complete m-partite graphs.     

Varieties of Lattices with Geometric Descriptions

A lattice L is spatial if every element of L is a join of completely join-irreducible elements of L (points), and strongly spatial if it is spatial and the minimal coverings of completely join-irreducible elements are well-behaved. Herrmann et al. proved in 1994 that every modular lattice can be embedded, within its variety, into an algebraic and spatial lattice. We extend this result to n-distributive lattices, for fixed n. We deduce that the variety of all n-distributive lattices is generated by its finite members, thus it has a decidable word problem for free lattices. This solves two problems stated by Huhn in 1985. We prove that every modular (resp., n-distributive) lattice embeds within its variety into some strongly spatial lattice. Every lattice which is either algebraic modular spatial or bi-algebraic is strongly spatial. We also construct a lattice that cannot be embedded, within its variety, into any algebraic and spatial lattice. This lattice has a least and a largest element, and it generates a locally finite variety of join-semidistributive lattices.     

Optimal recovery of linear functionals on sets of finite dimension

Suppose that X is a linear space and L ₁, …, L _n is a system of linearly independent functionals on P, where P ? X is a bounded set of dimension n + 1. Suppose that the linear functional L ₀ is defined in X. In this paper, we find an algorithm that recovers the functional L ₀ on the set P with the least error among all linear algorithms using the information L ₁ f, …, L _n f, f ∈ P.     

The level polynomials of the free distributive lattices

We show that there exist a set of polynomials {L_k?k = 0, 1?} such that L_k(n) is the number of elements of rank k in the free distributive lattice on n generators. L₀(n) = L₁(n) = 1 for all n and the degree of L_k is k?1 for k?1. We show that the coefficients of the L_k can be calculated using another family of polynomials, P_j. We show how to calculate L_k for k = 1,…,16 and P_j for j = 0,…,10. These calculations are enough to determine the number of elements of each rank in the free distributive lattice on 5 generators a result first obtained by Church [2]. We also calculate the asymptotic behavior of the L_k's and P_j's.     

An upper bound on the domination number of a graph with minimum degree 2

A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let P_n and C_n denote a path and a cycle, respectively, on n vertices. Let k₁(F) and k₂(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P₃,P₄,P₅,C₅} and {P₁,P₂}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .     

On the dimension of ordered sets with the 2-cutset property

An ordered setP is said to have 2-cutset property if, for every elementx ofP, there is a setS of elements ofP which are noncomparable tox, with |S|?2, such that every maximal chain inP meets {x}∪S. We consider the following question: Does there exist ordered sets with the 2-cutset property which have arbitrarily large dimension? We answer the question in the negative by establishing the following two results.Theorem: There are positive integersc andd such that every ordered setP with the 2-cutset property can be represented asP=X∪Y, whereX is an ordinal sum of intervals ofP having dimension ?d, andY is a subset ofP having width ?c. Corollary: There is a positive integern such that every ordered set with the 2-cutset property has dimension ?n.     

A subclass of Ockham algebras

Here we introduce a subclass of the class of Ockham algebras ( L ; f ) for which L satisfies the property that for every x ∈ L , there exists n ≥ 0 such that fn ( x ) and fn+1 ( x ) are complementary. We characterize the structure of the lattice of congruences on such an algebra ( L ; f ). We show that the lattice of compact congruences on L is a dual Stone lattice, and in particular, that the lattice Con L of congruences on L is boolean if and only if L is finite boolean. We also show that L is congruence coherent if and only if it is boolean. Finally, we give a sufficient and necessary condition to have the subdirectly irreducible chains.     

On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

Some theorems on graphs and posets

In this journal, Leclerc proved that the dimension of the partially ordered set consisting of all subtrees of a tree T, ordered by inclusion, is the number of end points of T. Leclerc posed the problem of determining the dimension of the partially ordered set P consisting of all induced connected subgraphs of a connected graph G for which P is a lattice.In this paper, we prove that the poset P consisting of all induced connected subgraphs of a nontrivial connected graph G, partially ordered by inclusion, has dimension n where n is the number of noncut vertices in G whether or not P is a lattice. We also determine the dimension of the distributive lattice of all subgraphs of a graph.     

Tilings of parallelograms with similar triangles

We say that a triangle δ tiles the polygonP ifP can be decomposed into finitely many non-overlapping triangles similar to δ. Let P bea parallelogram with anglesδ andπ -δ (0 <δ ≤π/2) and let δ be a triangle with anglesα, Β, γ (α ≤Β ≤γ). We prove that if δ tilesP then eitherδ ε α,Β,γ,π -γ, π - 2γ or dimL _P =dimL _δ. We also prove that for every parallelogramP, and for every integern (wheren≥ 2,n ? 3) there is a triangle δ so thatn similar copies of δ tileP.     

The lattice automorphisms of the dominance ordering

In this paper it is shown that the lattice L_n of partitions of n under the dominance ordering is totally asymmetric, except for the cases n = 6 and 7 where the automorphism group is $\text{Z}$₂ × $\text{Z}$₂. As a consequence, partition conjugation is the only antiautomorphism of L_n if n ≠ 6, 7.     

On the Order Dimension of Convex Geometries

We study the order dimension of the lattice of closed sets for a convex geometry. We show that the lattice of closed subsets of the planar point set of Erd?s and Szekeres from 1961, which is a set of 2 ^n???2 points and contains no vertex set of a convex n-gon, has order dimension n???1 and any larger set of points has order dimension at least n.     

Unimodular lattices with long shadow

Let L be an odd unimodular lattice of dimension n with shadow n−16. If min(L)?3 then dim(L)?46 and there is a unique such lattice in dimension 46 and no lattices in dimensions 44 and 45. To prove this, a shadow theory for theta series with spherical coefficients is developed.     

Cohomology of a class of Kadison-Singer algebras

Let L be the complete lattice generated by a nest N on an infinite-dimensional separable Hilbert space H and a rank one projection P ξ given by a vector ξ in H. Assume that ξ is a separating vector for N , the core of the nest algebra Alg(N ). We show that L is a Kadison-Singer lattice, and hence the corresponding algebra Alg(L) is a Kadison-Singer algebra. We also describe the center of Alg(L) and its commutator modulo itself, and show that every bounded derivation from Alg(L) into itself is inner, and all n-th bounded cohomology groups H n (Alg(L), B(H)) of Alg(L) with coefficients in B(H) are trivial for all n≥1.     

Approximately reducing subspaces for unbounded linear operators

We give sufficient conditions for generation of strongly continuous contraction semigroups of linear operators on Hilbert or Banach space. Let L be a dissipative (unbounded) linear operator in a Hilbert space $\text{H}$ and let {P_n} be an increasing sequence of self-adjoint projections converging weakly to the identity projection. We show that if there is a positive integer k such that for all n the range of P_n is contained in the domain of L and mapped by L into the range of P_{n + k}, and if the sequence {LP_n ? P_nLP_n} is dominated in norm (∥LP_n ? P_nLP_n∥ ? a_n) by some {a_n} ? $\text{R}$₊ with ∑_{n = 1}^∞a_n^?1 = ∞, then the closure of the restriction of L to ∪_{n = 1}^∞ range (P_n) is the infinitesimal generator of a strongly continuous contraction semigroup on $\text{H}$. Applications to an important class of finite perturbations, properly larger than the finite Kato perturbations, are given.We also give sufficient conditions for generation of contraction semigroups when {P_γ} (indexed by a directed set) is a set of bounded self-adjoint operators converging weakly to the identity and each having range contained in D(L). In the latter theorem, and in an analogous theorem for dissipative linear operators L in a Banach space, we do not assume that L interchanges at most finitely many of the approximately reducing operators P_γ.     

On a restricted cross-intersection problem

Suppose A and B are families of subsets of an n-element set and L is a set of s numbers. We say that the pair (A,B) is L-cross-intersecting if |A∩B|∈L for every A∈A and B∈B. Among such pairs (A,B) we write PL(n) for the maximum possible value of |A||B|. In this paper we find an exact bound for PL(n) when n is sufficiently large, improving earlier work of Sgall. We also determine P{2}(n) and P{1,2}(n) exactly, which respectively confirm special cases of a conjecture of Ahlswede, Cai and Zhang and a conjecture of Sgall.     

Properties of Standard n-Ideals of a Lattice

An n-ideal of a lattice L is a convex sublattice containing a fixed element n L and it is called standard if it is a standard element of the lattice of n-ideals I_n(L). In this paper we have shown that, for a neutral element n of a lattice L, the principal n-ideal a_n of a lattice L is a standard n-ideal if and only if a n is standard and a n is dual standard. We have also shown that if n is a neutral element and (n] and [n) are relatively complemented, then every homomorphism n-kernels of L is a standard n-ideal and every standard n-ideal is the n-kernel of precisely one congruence relation. Finally, we have shown that, for a relatively complemented lattice L with 0 and 1, C(L) is a Boolean algebra if and only if every standard n-ideal of L is a principal n-ideal.AMS Subject Classification (2000) 06B10 06B99 06C15     

Secant varieties of toric varieties

Let X_P be a smooth projective toric variety of dimension n embedded in P^r using all of the lattice points of the polytope P. We compute the dimension and degree of the secant variety . We also give explicit formulas in dimensions 2 and 3 and obtain partial results for the projective varieties X_A embedded using a set of lattice points A⊂P∩Zⁿ containing the vertices of P and their nearest neighbors.