首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
We consider the problem of reconstructing compositions of an integer from their subcompositions, which was raised by Raykova (albeit disguised as a question about layered permutations). We show that every composition w of n?3k+1 can be reconstructed from its set of k-deletions, i.e., the set of all compositions of n-k contained in w. As there are compositions of 3k with the same set of k-deletions, this result is best possible.  相似文献   

3.
We say that a rank-unimodal poset P has rapidly decreasing rank numbers, or the RDR property, if above (resp. below) the largest ranks of P, the size of each level is at most half of the previous (resp. next) one. We show that a finite rank-unimodal, rank-symmetric, normalized matching, RDR poset of width w has a partition into w chains such that the sizes of the chains are one of two consecutive integers. In particular, there exists a partition of the linear lattices Ln(q) (subspaces of an n-dimensional vector space over a finite field, ordered by inclusion) into chains such that the number of chains is the width of Ln(q) and the sizes of the chains are one of two consecutive integers.  相似文献   

4.
5.
We answer the question, when a partial order in a partially ordered algebraic structure has a compatible linear extension. The finite extension property enables us to show, that if there is no such extension, then it is caused by a certain finite subset in the direct square of the base set. As a consequence, we prove that a partial order can be linearly extended if and only if it can be linearly extended on every finitely generated subalgebra. Using a special equivalence relation on the above direct square, we obtain a further property of linearly extendible partial orders. Imposing conditions on the lattice of compatible quasi orders, the number of linear orders can be determined. Our general approach yields new results even in the case of semi-groups and groups.  相似文献   

6.
The Cartesian product of lattices is a lattice, called a product space, with componentwise meet and join operations. A sublattice of a lattice L is a subset closed for the join and meet operations of L. The sublattice hullLQ of a subset Q of a lattice is the smallest sublattice containing Q. We consider two types of representations of sublattices and sublattice hulls in product spaces: representation by projections and representation with proper boundary epigraphs. We give sufficient conditions, on the dimension of the product space and/or on the sublattice hull of a subset Q, for LQ to be entirely defined by the sublattice hulls of the two-dimensional projections of Q. This extends results of Topkis (1978) and of Veinott [Representation of general and polyhedral subsemilattices and sublattices of product spaces, Linear Algebra Appl. 114/115 (1989) 681-704]. We give similar sufficient conditions for the sublattice hull LQ to be representable using the epigraphs of certain isotone (i.e., nondecreasing) functions defined on the one-dimensional projections of Q. This also extends results of Topkis and Veinott. Using this representation we show that LQ is convex when Q is a convex subset in a vector lattice (Riesz space), and is a polyhedron when Q is a polyhedron in Rn.We consider in greater detail the case of a finite product of finite chains (i.e., totally ordered sets). We use the representation with proper boundary epigraphs and provide upper and lower bounds on the number of sublattices, giving a partial answer to a problem posed by Birkhoff in 1937. These bounds are close to each other in a logarithmic sense. We define a corner representation of isotone functions and use it in conjunction with the representation with proper boundary epigraphs to define an encoding of sublattices. We show that this encoding is optimal (up to a constant factor) in terms of memory space. We also consider the sublattice hull membership problem of deciding whether a given point is in the sublattice hull LQ of a given subset Q. We present a good characterization and a polynomial time algorithm for this sublattice hull membership problem. We construct in polynomial time a data structure for the representation with proper boundary epigraphs, such that sublattice hull membership queries may be answered in time logarithmic in the size |Q| of the given subset.  相似文献   

7.
The following problem was posed by C.A. Nicol: given any finite sequence of positive integers, find the permutation for which the continuant (i.e. the continued fraction denominator) having these entries is maximal, resp. minimal. The extremal arrangements are known for the regular continued fraction expansion. For the singular expansion induced by the backward shift ⌈1/x⌉-1/x the problem is still open in the case of maximal continuants. We present the explicit solutions for sequences with pairwise different entries and for sequences made up of any pair of digits occurring with any given (fixed) multiplicities. Here the arrangements are uniquely described by a certain generalized continued fraction. We derive this from a purely combinatorial result concerning the partial order structure of the set of permutations of a linearly ordered vector. This set has unique extremal elements which provide the desired extremal arrangements. We also prove that the palindromic maximal continuants are in a simple one-to-one correspondence with the Fine and Wilf words with two coprime periods which gives a new analytic and combinatorial characterization of this class of words.  相似文献   

8.
C. H. Ryter  J. Schmid 《Order》1994,11(3):257-279
We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.This work was supported in part by Swiss NSF grant 20-32644.91.  相似文献   

9.
Some examples of Σ1 1-universal preorders are presented, in the form of various relations of embeddability between countable coloured total orders. As an application, strengthening a theorem of (Marcone, A. and Rosendal, C.: The Complexity of Continuous Embeddability between Dendrites, J. Symb. Log. 69 (2004), 663–673), the Σ1 1-universality of continuous embeddability for dendrites whose branch points have order 3 is obtained.  相似文献   

10.
Roger Labahn 《Order》1992,9(4):349-355
In the n-dimensional cube, we determine the maximum size of antichains having a lower shadow of exactly m elements in the k-th level.  相似文献   

11.
Paul J. Tanenbaum 《Order》1996,13(4):339-350
We characterize the polysemic interval pairs—pairs of posets that admit simultaneous interval and interval-containment representations—and present algorithms to recoginze them and construct polysemic interval representations.This work, supported in part by NSF grant CCR-9300079, also appears in the author's doctoral thesis [9], written at the Johns Hopkins University under the supervision of Professors Edward R. Scheinerman and Michael T. Goodrich.  相似文献   

12.
We characterize the codominance pairs-pairs of posets that admit simultaneous dominance representations in the (x, y)-and (–x, y)-coordinate systems-and present a linear algorithm to recognize them and construct codominance representations. We define dominance polysemy as a generalization of codominance and describe several related problems and preliminary results.This author's research, supported in part by NSF grant CCR-9300079, also appears in his doctoral thesis [15], written, at the Johns Hopkins University under the supervision of Professors Edward R. Scheinerman and Michael T. Goodrich.This author's research, supported in part by an NSERC operating grant and an FCAR team grant, was performed in part during a visit at INRIA Sophia Antipolis.  相似文献   

13.
Letn>0 be an element of the setN of nonnegative integers, and lets(x)=x 1+...+x n , forx=(x 1, ...,x n ) N n . Adiagonal polynomial order inN n is a bijective polynomialp:N n N (with real coefficients) such that, for allx,y N n ,p(x)<p(y) whenevers(x)<s(y). Two diagonal polynomial orders areequivalent if a relabeling of variables makes them identical. For eachn, Skolem (1937) found a diagonal polynomial order. Later, Morales and Lew (1992) generalized this polynomial order, obtaining a family of 2 n–2 (n>1) inequivalent diagonal polynomial orders. Here we present, for eachn>0, a family of (n – 1)! diagonal polynomial orders, up to equivalence, which contains the Morales and Lew diagonal orders.  相似文献   

14.
15.
In this paper, we present a new approach for studying meanders in terms of noncrossing partitions. We show how this approach leads to a natural partial order on the set of meanders. In particular, meanders form a graded poset with regard to this partial order.  相似文献   

16.
Eugen Popa 《Positivity》2006,10(3):555-571
It is proved that the Laplace transform establishes a bijection between a class of resolvents (Vα)α>0 and a class of semi-groups Φ of kernels, acting on an abstract ordered convex cone. The compactness (in some weak topology) of the closed convex envelopes of the trajectories: Φ(t, x), t > 0, resp. of (nVn)kx, n, k ∈ ȑ, plays a central role in these results.  相似文献   

17.
In anydense posetP (and in any Boolean lattice in particular) every maximal antichainS may be partitioned into disjoint subsetsS 1 andS 2, such that the union of the downset ofS 1 with the upset ofS 2 yields the entire poset:D(S 1) U (S 2) =P. To find a similar splitting of maximal antichains in posets is NP-hard in general.Research was partially carried out when the second author visited the first author in Bielefeld and it was partially supported by OTKA grant T016358  相似文献   

18.
The set system satisfiesProperty B if there exists a partitionX 1X 2=X such that any element of intersects both classes. Here, we study the following problem: We are givenk set systems on the underlying setX, and we are seeking ak-partition ofX such that any element of theith set system intersectsX i for everyi.The paper received its final form when the author enjoyed the hospitality of L.A. Székely of the University of South Carolina, Columbia, South Carolina, USA. The research was partially supported by the Hungarian Scientific Fund, Grant no. T16358.  相似文献   

19.
This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.  相似文献   

20.
    
We examine finite words over an alphabet of pairs of letters, where each word w1w2 ... wt is identified with its reverse complement where ( ). We seek the smallest k such that every word of length n, composed from Γ, is uniquely determined by the set of its subwords of length up to k. Our almost sharp result (k~ 2n = 3) is an analogue of a classical result for “normal” words. This problem has its roots in bioinformatics. Received October 19, 2005  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号