共查询到20条相似文献,搜索用时 31 毫秒
1.
Jerrold R Griggs 《Journal of Combinatorial Theory, Series A》1980,28(2):156-168
A ranked poset P has the Sperner property if the sizes of the largest rank and of the largest antichain in P are equal. A natural strengthening of the Sperner property is condition S: For all k, the set of elements of the k largest ranks in P is a Sperner k-family. P satisfies condition T if for all k there exist disjoint chains in P each of which meets the k largest ranks and which covers the kth largest rank. It is proven here that if P satisfies S, it also satisfies T, and that the converse, although in general false, is true for posets with unimodal Whitney numbers. Conditions S and T and the Sperner property are compared here with two other conditions on posets concerning the existence of certain partitions of P into chains. 相似文献
2.
One of central issues in extremal set theory is Sperner’s theorem and its generalizations. Among such generalizations is the best-known LYM (also known as BLYM) inequality and the Ahlswede–Zhang (AZ) identity which surprisingly generalizes the BLYM into an identity. Sperner’s theorem and the BLYM inequality has been also generalized to a wide class of posets. Another direction in this research was the study of more part Sperner systems. In this paper we derive AZ type identities for regular posets. We also characterize all maximum 2-part Sperner systems for a wide class of product posets. 相似文献
3.
Let B(n) be the subset lattice of \({\{1,2,\dots, n\}.}\) Sperner’s theorem states that the width of B(n) is equal to the size of its biggest level. There have been several elegant proofs of this result, including an approach that shows that B(n) has a symmetric chain partition. Another famous result concerning B(n) is that its cover graph is hamiltonian. Motivated by these ideas and by the Middle Two Levels conjecture, we consider posets that have the Hamiltonian Cycle–Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. We show that the subset lattices have the HC-SCP property, and we obtain this result as a special case of a more general treatment. 相似文献
4.
Vivek Dhand 《Journal of Algebraic Combinatorics》2014,39(4):783-806
Young’s partition lattice L(m,n) consists of integer partitions having m parts where each part is at most n. Using methods from complex algebraic geometry, R. Stanley proved that this poset is rank-symmetric, unimodal, and strongly Sperner. Moreover, he conjectured that it has a symmetric chain decomposition, which is a stronger property. Despite many efforts, this conjecture has only been proved for min(m,n)≤4. In this paper, we decompose L(m,n) into level sets for certain tropical polynomials derived from the secant varieties of the rational normal curve in projective space, and we find that the resulting subposets have an elementary raising and lowering algorithm. As a corollary, we obtain a symmetric chain decomposition for the subposet of L(m,n) consisting of “sufficiently generic” partitions. 相似文献
5.
Richard P. Stanley 《Order》1984,1(1):29-34
An elementary, self-contained proof of a result of Pouzet and Rosenberg and of Harper is given. This result states that the quotient of certain posets (called unitary Peck) by a finite group of automorphisms retains some nice properties, including the Sperner property. Examples of unitary Peck posets are given, and the techniques developed here are used to prove a result of Lovász on the edge-reconstruction conjecture.Supported in part by a National Science Foundation research grant. 相似文献
6.
Lacking an explicit formula for the numbers T
0(n) of all order relations (equivalently: T
0 topologies) on n elements, those numbers have been explored only up to n=13 (unlabeled posets) and n=15 (labeled posets), respectively.In a new approach, we used an orderly algorithm to (i) generate each unlabeled poset on up to 14 elements and (ii) collect enough information about the posets on 13 elements to be able to compute the number of labeled posets on 16 elements by means of a formula by Erné. Unlike other methods, our algorithm avoids isomorphism tests and can therefore be parallelized quite easily. The underlying principle of successively adding new elements to small objects is applicable to lattices and other kinds of order structures, too. 相似文献
7.
Henri Mühle 《Journal of Algebraic Combinatorics》2017,45(3):745-775
We prove that the noncrossing partition lattices associated with the complex reflection groups G(d, d, n) for \(d,n\ge 2\) admit symmetric decompositions into Boolean subposets. As a result, these lattices have the strong Sperner property and their rank-generating polynomials are symmetric, unimodal, and \(\gamma \)-nonnegative. We use computer computations to complete the proof that every noncrossing partition lattice associated with a well-generated complex reflection group is strongly Sperner, thus answering affirmatively a question raised by D. Armstrong. 相似文献
8.
A refinement of an algorithm developed by Culberson and Rawlins yields the numbers of all partially ordered sets (posets) with n points and k antichains for n11 and all relevant integers k. Using these numbers in connection with certain formulae derived earlier by the first author, one can now compute the numbers of all quasiordered sets, posets, connected posets etc. with n points for n14. Using the well-known one-to-one correspondence between finite quasiordered sets and finite topological spaces, one obtains the numbers of finite topological spaces with n points and k open sets for n11 and all k, and then the numbers of all topologies on n14 points satisfying various degrees of separation and connectedness properties, respectively. The number of (connected) topologies on 14 points exceeds 1023. 相似文献
9.
Yasutaka Ihara 《Israel Journal of Mathematics》1992,80(1-2):135-153
We shall prove some stability property of the graded Lie algebraD
n of certain derivations associated with pure sphere braid group onn strings; in fact, thatD
n forn≥6. These Lie algebrasD
n are connected with some bigl-adic Galois representations, and the stability property is related to some conjecture of Grothendieck. 相似文献
10.
11.
Jerrold R Griggs Dean Sturtevant Michael Saks 《Journal of Combinatorial Theory, Series A》1980,29(3):391-394
A ranked poset P satisfies condition S if for all k the set of elements of the k largest ranks in P is a Sperner k-family. It satisfies condition T if for all k there exist disjoint chains in P which each meet the k largest ranks and which cover the kth largest rank. Griggs employed the theory of saturated partitions to prove that if P satisfies S it also satisfies T, and that the converse is true for posets with unimodal Whitney numbers. Here we present new proofs of these facts which do not require the existence of saturated partitions. The first result is proven with a simple network flow argument and the second is proven directly. 相似文献
12.
Emanuel Knill 《Graphs and Combinatorics》1994,10(2-4):145-157
A family of sets ? islocally k- wide if and only if the width (as a poset ordered by inclusion) of ? is at mostk for everyx. The directed covering graph of a locally 1-wide family of sets is a forest of rooted trees. It is shown that if ? is a locallyk-wide family of subsets of {1,...,n}, then |?|≤(2k) k?1 n. The proof involves a counting argument based on families of closed sets associated with theSperner closures in the filters of ?. The Sperner closure ofU in ? is the intersection of the members of the greatest Sperner antichain of ? U = {V ∈ ?|V ?U}. This closure operation is related to a generalization of maximality in posets. 相似文献
13.
Michael Crumley 《代数通讯》2013,41(8):3349-3382
It is generally believed (and for the most part it is probably true) that Lie theory, in contrast to the characteristic zero case, is insufficient to tackle the representation theory of algebraic groups over prime characteristic fields. However, in this article we show that, for a large and important class of unipotent algebraic groups (namely the unipotent upper triangular groups Un), and under a certain hypothesis relating the characteristic p to both n and the dimension d of a representation (specifically, p ≥ max(n, 2d)), Lie theory is completely sufficient to determine the representation theories of these groups. To finish, we mention some important analogies (both functorial and cohomological) between the characteristic zero theories of these groups and their “generic” representation theory in characteristic p. 相似文献
14.
Theprofile of a hypergraph onn vertices is (f
0, f1, ...,f
n) wheref
i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain
many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton). 相似文献
15.
V. K. Kharchenko 《Journal of Mathematical Sciences》2003,116(1):3063-3073
It is proved that under an existence condition, the dimension of all n-linear quantum Lie operations lies between (n - 2)! and (n - 1)!; moreover, the low bound is attained if the intersection of all conforming (i.e., satisfying the existence condition) subsets of a given set of quantum variables is nonempty. The upper bound is attained if all subsets are conforming. The space of multilinear quantum Lie operations is almost always generated by symmetric operations. All exceptional cases are given. In particular, the space of general n-linear Lie operations is always generated by general symmetric quantum Lie operations. Bibliography: 24 titles. 相似文献
16.
17.
Curtis Bennett Kathy J. Dempsey Bruce E. Sagan 《Journal of Algebraic Combinatorics》1994,3(3):261-283
We construct a family of partially ordered sets (posets) that are q-analogs of the set partition lattice. They are different from the q-analogs proposed by Dowling [5]. One of the important features of these posets is that their Whitney numbers of the first and second kind are just the q-Stirling numbers of the first and second kind, respectively. One member of this family [4] can be constructed using an interpretation of Milne [9] for S[n, k] as sequences of lines in a vector space over the Galois field F
q. Another member is constructed so as to mirror the partial order in the subspace lattice. 相似文献
18.
J. Bourgain 《Israel Journal of Mathematics》1988,63(1):79-97
It is shown that the almost sure convergence property for certain sequences of operators {S
n{ implies a uniform bound on the metrical entropy of the sets {S
nf|n=1, 2, ...{, wheref is taken in theL
2-unit ball. This criterion permits one to unify certain counterexamples due to W. Rudin [Ru] and J.M. Marstrand [Mar] and
has further applications. The theory of Gaussian processes is crucial in our approach. 相似文献
19.
In this paper, we introduce a new algebraic concept, which we call squarefree P-modules. This concept is inspired from Karu's proof of the non-negativity of the cd-indices of Gorenstein* posets, and supplies a way to study cd-indices from the viewpoint of commutative algebra. Indeed, by using the theory of squarefree P-modules, we give several new algebraic and combinatorial results on CW-posets. First, we define an analogue of the cd-index for any CW-poset and prove its non-negativity when a CW-poset is Cohen–Macaulay. This result proves that the h-vector of the barycentric subdivision of a Cohen–Macaulay regular CW-complex is unimodal. Second, we prove that the Stanley–Reisner ring of the barycentric subdivision of an odd dimensional Cohen–Macaulay polyhedral complex has the weak Lefschetz property. Third, we obtain sharp upper bounds of the cd-indices of Gorenstein* posets for a fixed rank generating function. 相似文献
20.
We determine the Lie superalgebras that are graded by the
root system B(m,n) of the
orthosymplectic Lie superalgebra osp(2m +
1,2n).
Mathematics Subject Classification (2000) Primary 17B70, Secondary 17A70 相似文献