Generating sets for lattices of dimension two

The dimension of a partially ordered set P is the smallest integer n (if it exists) such that the partial order on P is the intersection of n linear orders. It is shown that if L is a lattice of dimension two containing a sublattice isomorphic to the modular lattice M_2n+1, then every generating set of L has at least n+2 elements. A consequence is that every finitely generated lattice of dimension two and with no infinite chains is finite.     

Maximal dimensional partially ordered sets I. Hiraguchi's theorem

In this paper, I give a new proof of Hiraguchi's Theorem that the dimension of an n-element partially ordered set is at most [frcase|1/2n]. The significant feature of the proof is the lemma which states that a partially ordered set has either a cover of rank 0 or a pair of covers with elements of one incomparable with elements of the other.     

A Bipartite Analogue of Dilworth’s Theorem

Let m(n) be the maximum integer such that every partially ordered set P with n elements contains two disjoint subsets A and B, each with cardinality m(n), such that either every element of A is greater than every element of B or every element of A is incomparable with every element of B. We prove that . Moreover, for fixed ε ∈ (0,1) and n sufficiently large, we construct a partially ordered set P with n elements such that no element of P is comparable with other elements of P and for every two disjoint subsets A and B of P each with cardinality at least , there is an element of A that is comparable with an element of B.     

Local dendrites with unique n-fold hyperspace

Let Z be a metric continuum and n be a positive integer. Let Cn(Z) be the hyperspace of the nonempty closed subsets of Z with at most n components. In this paper we prove the following result: Let X be a local dendrite such that every point of X has a neighborhood which is a dendrite whose set of end points is closed and Z is any continuum such that Cn(X) is homeomorphic to Cm(Z) for some n,m?3, then X is homeomorphic to Z.     

On Inductive Limits for Systems of <Emphasis Type="Italic">C</Emphasis>*-Algebras

We consider a covariant functor from the category of an arbitrary partially ordered set into the category of C*-algebras and their *-homomorphisms. In this case one has inductive systems of algebras over maximal directed subsets. The article deals with properties of inductive limits for those systems. In particular, for a functor whose values are Toeplitz algebras, we show that each such an inductive limit is isomorphic to a reduced semigroup C*-algebra defined by a semigroup of rationals. We endow an index set for a family of maximal directed subsets with a topology and study its properties. We establish a connection between this topology and properties of inductive limits.     

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.     

Convex subsets of 2n and bounded truth-table reducibility

Let 2ⁿ be the set of n-tuples of 0's and 1's, partially ordered componentwise. A characterization is given of the possible decompositions of arbitrary subsets of 2ⁿ as disjoint unions of sets which are convex in this ordering; this result is used to obtain a decomposition theorem for Boolean functions in terms of monotone functions. The second half of the paper contains applications to recursion theory; in particular, canonical forms for certain minimum-norm bounded-truth-table reductions are obtained.     

Symmetrisation of n-operads and compactification of real configuration spaces

It is well known that the forgetful functor from symmetric operads to nonsymmetric operads has a left adjoint Sym₁ given by product with the symmetric group operad. It is also well known that this functor does not affect the category of algebras of the operad. From the point of view of the author's theory of higher operads, the nonsymmetric operads are 1-operads and Sym₁ is the first term of the infinite series of left adjoint functors Symn, called symmetrisation functors, from n-operads to symmetric operads with the property that the category of one object, one arrow, …, one (n−1)-arrow algebras of an n-operad A is isomorphic to the category of algebras of Symn(A).In this paper we consider some geometrical and homotopical aspects of the symmetrisation of n-operads. We follow Getzler and Jones and consider their decomposition of the Fulton-Macpherson operad of compactified real configuration spaces. We construct an n-operadic counterpart of this compactification which we call the Getzler-Jones operad. We study the properties of Getzler-Jones operad and find that it is contractible and cofibrant in an appropriate model category. The symmetrisation of the Getzler-Jones operad turns out to be exactly the operad of Fulton and Macpherson. These results should be considered as an extension of Stasheff's theory of 1-fold loop spaces to n-fold loop spaces n?2. We also show that a space X with an action of a contractible n-operad has a natural structure of an algebra over an operad weakly equivalent to the little n-disks operad. A similar result holds for chain operads. These results generalise the classical Eckman-Hilton argument to arbitrary dimension.Finally, we apply the techniques to the Swiss-Cheese type operads introduced by Voronov and prove analogous results in this case.     

The graphs G(n, k) of the Johnson Schemes are unique for n ≥ 20

Let G(n, k) denote the graph of the Johnson Scheme J(n, k), i.e., the graph whose vertices are all k-subsets of a fixed n-set, with two vertices adjacent if and only if their intersection is of size k ? 1. It is known that G(n, k) is a distance regular graph with diameter k. Much work has been devoted to the question of whether a distance regular graph with the parameters of G(n, k) must isomorphic to G(n, k). In this paper, this question is settled affirmatively for n ≥ 20. In fact the result is proved with weaker conditions.     

G-decomposition of Kn, where G has four vertices or less

The complete graph K_n, is said to have a G-decomposition if it is the union of edge disjoint subgraphs each isomorphic to G. The set of values of n for which K_n has a G-decomposition is determined if G has four vertices or less.     

n-point sets and graphs of functions

We prove that, for every n?2, there exists an n-point set (a plane set which hits every line in exactly n points) that is homeomorphic to the graph of a function from R to R; for n?4, there exist both 0-dimensional and 1-dimensional examples. This raises the question (which we do not answer) of whether n-point sets for different n's could be homeomorphic.     

Characterizations of n-connected and n-line connected graphs

The following two theorems are proved: (1) A graph G with at least n + 1 points, n ≥ 2, is n-connected if and only if for each set S of n distinct points of G and for each two point subset T of S there is a cycle of G that contains the points of T and avoids the points of S ? T. (2) A graph G with at least n + 1 lines, n ≥ 2, with no isolated points is n-line connected if and only if for each set S of n distinct lines of G and for each two line subset T of S there is a circuit of G that contains the lines of T and avoids the lines of S ? T.     

A new characterization of matrices with the consecutive ones property

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment.     

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.     

Partial Orders on Weak Orders Convex Subsets

We study a visibility relation on the nonempty connected convex subsets of a finite partially ordered set and we investigate the partial orders representable as a visibility relation of such subsets of a weak order. Moreover, we consider restrictions where the subsets of the weak order are total orders or isomorphic total orders.     

A proof of Frankl’s union-closed sets conjecture for dismantlable lattices

For a lattice L, let Princ(L) denote the ordered set of principal congruences of L. In a pioneering paper, G. Grätzer characterized the ordered set Princ(L) of a finite lattice L; here we do the same for a countable lattice. He also showed that every bounded ordered set H is isomorphic to Princ(L) of a bounded lattice L. We prove a related statement: if an ordered set H with a least element is the union of a chain of principal ideals (equivalently, if 0 \({\in}\) H and H has a cofinal chain), then H is isomorphic to Princ(L) of some lattice L.     

Basis theorems for continuous n-colorings

This article is devoted to the study of continuous colorings of the n-element subsets of a Polish space.The homogeneity numberhm(c) of an n-coloring c:n[X]→2 is the least size of a family of c-homogeneous sets that covers X. An n-coloring is uncountably homogeneous if hm(c)>ℵ₀. Answering a question of B. Miller, we show that for every n>1 there is a finite family B of continuous n-colorings on ω² such that every uncountably homogeneous, continuous n-coloring on a Polish space contains a copy of one of the colorings from B. We also give upper and lower bounds for the minimal size of such a basisB.     

Maximal dimensional partially ordered sets III: a characterization of Hiraguchi's inequality for interval dimension

Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ?_n such that if |X| ?2n+1, the dim X < n unless X contains one of the posets from ?_n. Although |?₃|=24, for each n ≥ 4, ?_n contains only the crown S⁰_n — the poset consisting of all 1 element and n ? 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S⁰_n.     

An asymptotic formula for the maximum size of an h-family in products of partially ordered sets

An h-family of a partially ordered set P is a subset of P such that no h + 1 elements of the h-family lie on any single chain. Let S₁, S₂,… be a sequence of partially ordered sets which are not antichains and have cardinality less than a given finite value. Let P_n be the direct product of S₁,…, S_n. An asymptotic formula of the maximum size of an h-family in P_n is given, where $\text{h=o(}\text{n}\text{)}$ and n → ∞.     

Ordered Sets that are Reconstructible from Two Cards and the Number of Comparabilities

This paper proves that, if there is an ordered set P that is not reconstructible, then each of its two-point-deleted subsets must be isomorphic to another one, or, it must violate a condition that is related to, but weaker than, rigidity. The conditions are inspired by an argument by Bollobas and they provide a connection between positive reconstruction results and partial counterexamples that was, so far, nonexistent in order reconstruction.