Note on the description of join-distributive lattices by permutations

Let L be a join-distributive lattice with length n and width(JiL) ≤ k. There are two ways to describe L by k ? 1 permutations acting on an n-element set: a combinatorial way given by P.H. Edelman and R. E. Jamison in 1985 and a recent lattice theoretical way of the second author. We prove that these two approaches are equivalent. Also, we characterize join-distributive lattices by trajectories.     

Dimension and decomposition in modular upper-continuous lattices

Slim rectangular lattices are special planar semimodular lattices introduced by G. Grätzer and E. Knapp in 2009. They are finite semimodular lattices L such that the ordered set Ji L of join-irreducible elements of L is the cardinal sum of two nontrivial chains. After describing these lattices of a given length n by permutations, we determine their number, |SRectL(n)|. Besides giving recursive formulas, which are effective up to about n = 1000, we also prove that |SRectL(n)| is asymptotically (n - 2)! · \({e^{2}/2}\). Similar results for patch lattices, which are special rectangular lattices introduced by G. Czédli and E. T. Schmidt in 2013, and for slim rectangular lattice diagrams are also given.     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

The sorting order on a Coxeter group

Let (W,S) be an arbitrary Coxeter system. For each word ω in the generators we define a partial order—called the ω-sorting order—on the set of group elements Wω⊆W that occur as subwords of ω. We show that the ω-sorting order is a supersolvable join-distributive lattice and that it is strictly between the weak and Bruhat orders on the group. Moreover, the ω-sorting order is a “maximal lattice” in the sense that the addition of any collection of Bruhat covers results in a nonlattice.Along the way we define a class of structures called supersolvable antimatroids and we show that these are equivalent to the class of supersolvable join-distributive lattices.     

Permutation designs

An (n, k)-permutation design is a collection of k! permutations on n elements such that for any choice of k elements all k! permutations of these elements appear as subpermutations in the collection. For every n we construct an (n, n ? 1)-permutation design. There is a rather unique (6, 4)-design but no (5, 3)- and (7, 4)-design. Permutation designs and ordered triple systems are special cases of ordered designs. For all n ≠ 2 (mod 3) we have an ordered triple system containing no triples twice.     

Rank 72 high minimum norm lattices

Given a polarization of an even unimodular lattice and integer k?1, we define a family of unimodular lattices L(M,N,k). Of special interest are certain L(M,N,3) of rank 72. Their minimum norms lie in {4,6,8}. Norms 4 and 6 do occur. Consequently, 6 becomes the highest known minimum norm for rank 72 even unimodular lattices. We discuss how norm 8 might occur for such a L(M,N,3). Our method constructs such L(M,N,k) in dimensions 96, 120 and 128 with minimum norms 8.     

A structure theorem for dismantlable lattices and enumeration

The concept of `adjunct' operation of two lattices with respect to a pair of elements is introduced. A structure theorem namely, `A finite lattice is dismantlable if and only if it is an adjunct of chains' is obtained. Further it is established that for any adjunct representation of a dismantlable lattice the number of chains as well as the number of times a pair of elements occurs remains the same. If a dismantlable lattice L has n elements and n+k edges then it is proved that the number of irreducible elements of L lies between n-2k-2 and n-2. These results are used to enumerate the class of lattices with exactly two reducible elements, the class of lattices with n elements and upto n+1 edges, and their subclasses of distributive lattices and modular lattices. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

Missing edge coverings of bipartite graphs and the geometry of the Hausdorff metric

In this paper, we examine the problem of finding the number ${k}$ of elements at a given location on the line segment between two elements in the geometry the Hausdorff metric imposes on the set ${\mathcal{H} (\mathbb{R}^{n})}$ of all nonempty compact sets in n-dimensional real space. We demonstrate that this problem is equivalent to counting the edge coverings of simple bipartite graphs. We prove the novel results that there exist no simple bipartite graphs with exactly 19 or 37 edge coverings, and hence there do not exist any two elements of ${\mathcal{H} (\mathbb{R}^{n})}$ with exactly 19 or 37 elements at a given location lying between them—although there exist pairs of elements in ${\mathcal{H} (\mathbb{R}^{n})}$ that have k elements at any given location between them for infinitely many values of k, including k from 1 to 18 and 20 to 36. This paper extends results in the geometry of the Hausdorff metric given in J. Geom. 92: 28–59 (2009). In addition to our results about counting edge coverings, we give a brief introduction to this geometry.     

Free resolutions for multiple point spaces

This paper relates the multiple point spaces in the source and target of a corank 1 map-germ ${(\mathbb {C}^n, 0)\to(\mathbb {C}^{n+1}, 0)}$ . Let f be such a map-germ, and, for 1 ≤ k ≤ multiplicity( f ), let D ^k ( f ) be its k’th multiple point scheme – the closure of the set of ordered k-tuples of pairwise distinct points sharing the same image. There are natural projections D ^k+1( f ) → D ^k ( f ), determined by forgetting one member of the (k + 1)-tuple. We prove that the matrix of a presentation of ${\mathcal {O}_{D^{k+1}(f)}}$ over ${\mathcal {O}_{D^k(f)}}$ appears as a certain submatrix of the matrix of a suitable presentation of ${\mathcal {O}_{\mathbb {C}^n,0}}$ over ${\mathcal {O}_{\mathbb {C}^{n+1},0}}$ . This does not happen for germs of corank > 1.     

Class numbers of definite binary quadratic lattices over algebraic function fields

Let k be an algebraic function field of one variable X having a finite field GF(q) of constants with q elements, q odd. Confined to imaginary quadratic extensions $\text{K}\text{k}$, class number formulas are developed for both the maximal and nonmaximal binary quadratic lattices L on (K, N), where N denotes the norm from K to k. The class numbers of L grow either with the genus g(k) of k (assuming the fields under consideration have bounded degree) or with the relative genus $\text{g(}\text{K}\text{k}\text{)}$ (assuming the lattices under consideration have bounded scale). In contrast to analogous theorems concerning positive definite binary quadratic lattices over totally real number fields, k is not necessarily totally real.     

Comparability graphs of lattices

A theorem of N. Terai and T. Hibi for finite distributive lattices and a theorem of Hibi for finite modular lattices (suggested by R.P. Stanley) are equivalent to the following: if a finite distributive or modular lattice of rank d contains a complemented rank 3 interval, then the lattice is (d+1)-connected.In this paper, the following generalization is proved: Let L be a (finite or infinite) semimodular lattice of rank d that is not a chain (d∈N₀). Then the comparability graph of L is (d+1)-connected if and only if L has no simplicial elements, where z∈L is simplicial if the elements comparable to z form a chain.     

Timelike Hypersurfaces in the Standard Lorentzian Space Forms Satisfying L k x = Ax + b

In this paper, we study connected orientable timelike hypersurfaces isometrically immersed by ${x : M_1^{n} \rightarrow {\tilde{M}}_1^{n+1}(c)}$ into the de Sitter space ${\mathbb{S}_1^{n+1}}$ (when c = 1) or anti-de Sitter space ${\mathbb{H}_1^{n+1}}$ (when c = ?1) satisfying the condition L _k x = Ax + b, where the second order differential operator L _k is the linearized operator associated with the first normal variation of the (k + 1)-th mean curvature of M for an integer k, 0 ≤ k < n, A is a matrix and b is a vector. We characterize these hypersurfaces when b = 0 or when the k-th mean curvature of M is constant.     

Archimedean lattices

Anarchimedean lattice is a complete algebraic latticeL with the property that for each compact elementc∈L, the meet of all the maximal elements in the interval [0,c] is 0.L ishyper-archimedean if it is archimedean and for eachx∈L, [x, 1] is archimedean. The structure of these lattices is analysed from the point of view of their meet-irreducible elements. If the lattices are also Brouwer, then the existence of complements for the compact elements characterizes a particular class of hyper-archimedean lattices. The lattice ofl-ideals of an archimedean lattice ordered group is archimedean, and that of a hyper-archimedean lattice ordered group is hyper-archimedean. In the hyper-archimedean case those arising as lattices ofl-ideals are fully characterized.     

On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.     

Generalized monotone approximation inL p Space

Letf(x) ∈L _p[0,1], 1?p? ∞. We shall say that functionf(x)∈Δ^k (integerk?1) if for anyh ∈ [0, 1/k] andx ∈ [0,1?kh], we have Δ _h ^k f(x)?0. Denote by ∏ _n the space of algebraic polynomials of degree not exceedingn and define $$E_{n,k} (f)_p : = \mathop {\inf }\limits_{\mathop {P_n \in \prod _n }\limits_{P_n^{(\lambda )} \geqslant 0} } \parallel f(x) - P_n (x)\parallel _{L_p [0,1]} .$$ We prove that for any positive integerk, iff(x) ∈ Δ ^k ∩ L _p[0, 1], 1?p?∞, then we have $$E_{n,k} (f)_p \leqslant C\omega _2 \left( {f,\frac{1}{n}} \right)_p ,$$ whereC is a constant only depending onk.     

Isotone maps on lattices

Let ${\mathcal{L} = (Li | i \in I)}$ be a family of lattices in a nontrivial lattice variety V, and let ${\varphi_{i} : L_{i} \rightarrow M}$ , for ${i \in I}$ , be isotone maps (not assumed to be lattice homomorphisms) to a common lattice M (not assumed to lie in V). We show that the maps ${\varphi_{i}}$ can be extended to an isotone map ${\varphi : L \rightarrow M}$ , where ${L = {\rm Free}_{V} \mathcal{L}}$ is the free product of the L _i in V. This was known for V = L, the variety of all lattices. The above free product L can be viewed as the free lattice in V on the partial lattice P formed by the disjoint union of the L _i . The analog of the above result does not, however, hold for the free lattice L on an arbitrary partial lattice P. We show that the only codomain lattices M for which that more general statement holds are the complete lattices. On the other hand, we prove the analog of our main result for a class of partial lattices P that are not-quite-disjoint unions of lattices. We also obtain some results similar to our main one, but with the relationship lattices : orders replaced either by semilattices : orders or by lattices : semilattices. Some open questions are noted.     

Largest independent sets of certain regular subgraphs of the derangement graph

The derangement graph is the Cayley graph on the symmetric group \(\mathcal {S}_{n}\) whose generating set \(D_{n}\) is the set of permutations on \([n]=\{1, \ldots , n\}\) without any 1-cycle. For any fixed positive integer \(k \le n\), the Cayley graph generated by the subset of \(D_{n}\) consisting of permutations without any i-cycles for all \(1 \le i \le k\) is a regular subgraph of the derangement graph. In this paper, we determine the smallest eigenvalue of these subgraphs and show that the set of all the largest independent sets in these subgraphs is equal to the set of all the largest independent sets in the derangement graph, provided n is sufficiently large in terms of k.     

A fundamental inequality for the sum of sets of m-tuples

For n a positive integer and A₁, A₂, …, A_k sets of nonnegative integers, sufficient conditions are found which imply that the sum of the cardinalities of the sets $\text{{1, 2, …, n} ? A}{}_{\mathrm{i}}\text{(i = 1, 2, …, k)}$ does not exceed the cardinality of the intersection of {1, 2, …, n} and the number theoretic sum of the k sets. Some of the results are generalized to sets of m-tuples of nonnegative integers.