Networks and chain coverings in partial orders and their products

For an arbitrary poset P, subposets {P _i : 1ik} form a transitive basis of P if P is the transitive closure of their union. Let u be the minimum size of a covering of P by chains within posets of the basis, s the maximum size of a family of elements with no pair comparable in any basis poset, and a the maximum size of an antichain in P. Define a dense covering to be a collection D of chains within basis posets such that each element belongs to a chain in D within each basis poset and is the top of at least k-1 chains and the bottom of at least k-1 chains in D. Dense coverings generalize ordinary chain coverings of poset. Let d=min {|D|–(k–1)|P|}. For an arbitrary poset and transitive basis, a convenient network model for dense coverings yields the following: Theorem 1: da, with equality iff P has a minimum chain decomposition in which every pair of consecutive elements on each chain are comparable in some basis poset. Theorem 2: usda. Theorem 3: s=d iff s=a. The most interesting special case is where the transitive basis expresses P as the product of two posets, in which case u and s measure the minimum and maximum sizes of unichain coverings and semiantichains.     

Sperner Partition Systems

A Spernerk‐partition system on a set X is a set of partitions of X into k classes such that the classes of the partitions form a Sperner set system (so no class from a partition is a subset of a class from another partition). These systems were defined by Meagher, Moura, and Stevens in [6] who showed that if , then the largest Sperner k‐partition system has size . In this paper, we find bounds on the size of the largest Sperner k‐partition system where k does not divide the size of X, specifically, we give upper and lower bounds when , and .     

Admissible values of one parameter for maximal Sperner families of subsets of the type (<Emphasis Type="Italic">k,k</Emphasis> + 1)

In this paper we generalize one assertion (obtained by us earlier) on admissible values of a certain parameter for partial maximal Sperner families (m. S. f.) of subsets of a finite set of the type (k, k + 1). We also prove that the minimal value of the parameter under consideration for all m. S. f. of the type (k, k + 1), except for two families, is less than \(\left( {_k^{n - 1} } \right)\) ? 1.     

Maximum Antichains in Random Subsets of a Finite Set

We consider the random poset (n, p) which is generated by first selecting each subset of [n]={1, …, n} with probability p and then ordering the selected subsets by inclusion. We give asymptotic estimates of the size of the maximum antichain for arbitrary p=p(n). In particular, we prove that if pn/log n→∞, an analogue of Sperner's theorem holds: almost surely the maximum antichain is (to first order) no larger than the antichain which is obtained by selecting all elements of (n, p) with cardinality n/2. This is almost surely not the case if pn=∞.     

Strong Sperner property of the subgroup lattice of an Abelianp-group

Letn andk be arbitrary positive integers,p a prime number and L_(k ⁿ)(p) the subgroup lattice of the Abelianp-group (Z/p ^k ) ⁿ . Then there is a positive integerN(n,k) such that whenp N(n,k),L _(k ^N )(p) has the strong Sperner property.     

On the Sperner Capacity of the Cyclic Triangle

Using a single trick it is shown that the Sperner capacity of the cyclic triangle equals log 2.     

The Sperner Capacity of Linear and Nonlinear Codes for the Cyclic Triangle

Shannon introduced the concept of zero-error capacity of a discrete memoryless channel. The channel determines an undirected graph on the symbol alphabet, where adjacency means that symbols cannot be confused at the receiver. The zero-error or Shannon capacity is an invariant of this graph. Gargano, Körner, and Vaccaro have recently extended the concept of Shannon capacity to directed graphs. Their generalization of Shannon capacity is called Sperner capacity. We resolve a problem posed by these authors by giving the first example (the two orientations of the triangle) of a graph where the Sperner capacity depends on the orientations of the edges. Sperner capacity seems to be achieved by nonlinear codes, whereas Shannon capacity seems to be attainable by linear codes. In particular, linear codes do not achieve Sperner capacity for the cyclic triangle. We use Fourier analysis or linear programming to obtain the best upper bounds for linear codes. The bounds for unrestricted codes are obtained from rank arguments, eigenvalue interlacing inequalities and polynomial algebra. The statement of the cyclic q-gon problem is very simple: what is the maximum size N _q(n) of a subset S _n of {0, 1, \(\ldots\) , q?1} ⁿ with the property that for every pair of distinct vectors x = (x _i), y = (y _i) \(\in \) S _n, we have x _j ?y _j ≡ 1(mod q) for some j? For q = 3 (the cyclic triangle), we show N ₃(n)?2 ⁿ . If however S _n is a subgroup, then we give a simple proof that \(\left| {S_n } \right| \leqslant \sqrt 3 ^n \) .