共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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 n2?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n2?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. 相似文献
4.
Drew Armstrong 《Journal of Combinatorial Theory, Series A》2009,116(8):1285-1305
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. 相似文献
5.
Christoph Bandt 《Journal of Combinatorial Theory, Series A》1976,21(3):384-392
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. 相似文献
6.
Robert L. Griess Jr. 《Journal of Number Theory》2010,130(7):1512-1519
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. 相似文献
7.
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. 相似文献
8.
George Markowsky 《Discrete Mathematics》1980,29(3):275-285
We show that there exist a set of polynomials {Lk?k = 0, 1?} such that Lk(n) is the number of elements of rank k in the free distributive lattice on n generators. L0(n) = L1(n) = 1 for all n and the degree of Lk is k?1 for k?1. We show that the coefficients of the Lk can be calculated using another family of polynomials, Pj. We show how to calculate Lk for k = 1,…,16 and Pj 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 Lk's and Pj's. 相似文献
9.
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 + θ) log2 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.$$
10.
Katrina Honigs 《Journal of Geometry》2013,104(1):107-125
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. 相似文献
11.
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. 相似文献
12.
Ulrike Korte 《Journal of Number Theory》1984,19(1):33-39
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 , 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 (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. 相似文献
13.
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∈N0). 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. 相似文献
14.
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. 相似文献
15.
J. Martinez 《Algebra Universalis》1973,3(1):247-260
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. 相似文献
16.
D.T Todorov 《Journal of Combinatorial Theory, Series A》1985,39(1):83-101
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 [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case . 相似文献
17.
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. 相似文献
18.
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. 相似文献
19.
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. 相似文献
20.
Mary Lou Daily 《Journal of Number Theory》1976,8(4):424-433
For n a positive integer and A1, A2, …, Ak sets of nonnegative integers, sufficient conditions are found which imply that the sum of the cardinalities of the sets 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. 相似文献