当前位置:首页 >> >>

The width of random subsets of Boolean lattices, submitted

The Width of Random Subsets of Boolean Lattices?
Y. Kohayakawa?
Instituto de Matem? atica e Estat? ?stica, Universidade de S? ao Paulo Rua do Mat? ao 1010, 05508–090 S? ao Paulo, Brazil E-mail address : yoshi@ime.usp.br

B. Kreuter
Institut f¨ ur Informatik, Humboldt-Universit¨ at zu Berlin Unter den Linden 6, 10099 Berlin, Germany E-mail address : kreuter@informatik.hu-berlin.de Abstract Suppose we toss an independent coin with probability of success p for each subset of [n] = {1, . . . , n}, and form the random hypergraph P (n, p) by taking as hyperedges the subsets with successful coin tosses. We investigate the cardinality of the largest Sperner family contained in P (n, p). We obtain a sharp result for the range of p = p(n) in which this Sperner family has cardinality comparable to the cardinality of P (n, p).



As is well known, a basic result in extremal set theory is a theorem of Sperner, which determines the width , that is, the maximum cardinality of an antichain, in the poset P (n) = 2[n] . The investigation of extensions of this 74-year-old result has given rise to a surprisingly rich theory; the reader unfamiliar with the more recent developments in this area is encouraged to consult the monograph of Engel [8]. In this note, we are interested in the width of a poset naturally derived from P (n) = 2[n] . Let 0 ≤ p ≤ 1 be given, and consider the random subposet P (n, p) ? P (n), whose elements are randomly chosen from P (n), independently, with probability p each, and the order relation is the naturally induced order. Our main aim here is to investigate the width of the random poset P (n, p). For a good introduction to the theory of random posets, including results on the width, we recommend a survey of Brightwell [7]. It should be observed that, somewhat surprisingly,
Research supported by PROBRAL (proj. 026/95 and 089/99), a CAPES–DAAD exchange programme. Partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997–4), by CNPq (Proc. 300334/93–1, 910064/99–7, and 468516/2000–0), and by FAPESP (Proc. 96/04505–2).
? ?


however, the model of random posets that we are concerned with here has not been studied to any great extent. Indeed, we shall settle here a rather basic problem about the width of P (n, p). We shall observe that the width of P (n, p), measured against the cardinality of P (n, p), varies from 1 to 0 as p grows (this is an easy observation), and we shall identify in our main theorem the parameterization of p that makes it transparent how this decay takes place (see Theorem 1 below). Let us mention that our technique also gives structural information about the largest antichains in P (n, p). It may be of some interest to state a version of our results in terms of counting, and in the language of hypergraphs. Let Hn,m = {H1 , . . . , Hm } be a collection of m subsets of [n]. Denote by α(Hn,m ) the size of the largest Sperner family contained in Hn,m . That is, α(Hn,m ) is the largest cardinality of a subcollection of Hn,m of mutually incomparable elements. De?ne b = b(n) so that m = m(n) = n?b
√ n n

2 .


Theorem 1 below implies that a typical Hn,m (that is, almost all of them) are such that 1 α(Hn,m ) → 1 m and if b = b(n) → ∞ as n → ∞ (2)

1 α(Hn,m ) → 0 if b = b(n) → 0 as n → ∞. (3) m Moreover, if b(n) → b0 as n → ∞, where 0 < b0 < ∞ is some constant, then the ratio α(Hn,m )/m converges to a constant c(b0 ) > 0, which we explicitly identify. The random poset P (n, p) was probably ?rst investigated by R? enyi [15] who, answering a question of Erd? os, determined the minimal asymptotic value of p = p(n) above for which the probability that P (n, p) should itself be an antichain tends to 0. The study of P (n, p) remained dormant for many years, but, recently, motivated by the explosive growth of the research in the theory of random graphs, Kreuter [12] investigated for P (n, p) analogues of some classical problems in random graphs. In modern language, R? enyi established the threshold function for the emergence of the Boolean lattice L = P (1) in P (n, p). Kreuter extended this result by determining the emergence threshold function for a large class of lattices L. The interested reader is referred to [12], which may be thought of as a modern sequel to R? enyi’s pioneering work [15]. For the background from the theory of random graphs, see Bollob? as [2] and Janson, Luczak, and Ruci? nski [10]. Another parameter that is of interest in the study of a poset is its height or length , i.e., the cardinality of a longest chain. For results concerning the length of P (n, p), the reader is referred to Kohayakawa, Kreuter, and Osthus [11]. We mention that Bollob? as and Brightwell [4, 5] have investigated the height of random d-dimensional partial orders and, more generally, of random partial orders de?ned in terms of ‘box spaces’ (certain partially 2

ordered probability spaces). The study of the height of random 2-dimensional partial orders goes back to Ulam [16] (see [5, 7] for further references). The ?avour of the arguments in [11] are, however, closer to the ones in Fill and Pemantle [9] and Bollob? as, Kohayakawa and Luczak [6].

Further results
Soon after the results in this note were obtained, Osthus [14] discovered a powerful method of proof inspired in Lubell’s beautiful proof [13] of Sperner’s theorem. Indeed, making use of a technical lemma [11, Lemma 7], Osthus showed that Lubell’s method can be essentially carried over to P (n, p), for a wide range of p = p(n). Write p = p(n) = (r/n)r . Osthus [14] determined α(P (n, p)) up to a multiplicative factor of 1+o(1) if r → ∞ as n → ∞. Moreover, he proved that, with probability tending to 1 as n → ∞, we have α(P (n, p)) = (1 + o(1))p n n/2

when p = ωn?1 log n, where ω = ω (n) is any function with ω → ∞ as n → ∞. (It is an open problem whether the log n factor is required.) The results in this note cover a narrower range of p = p(n), namely, r above has to be √ of order n; note that, however, this is an interesting period of the evolution of P (n, p), as show (1), (2), and (3). Our proof follows the ‘chain decomposition method’, based on matchings, and is self-contained. For a discussion on these classical proofs of Sperner’s theorem, see, e.g., [1] and [3].


Statements of the main results
1 Φ(b) = √ 2π
b ?∞

Denote by Φ the distribution function of the normal distribution, i.e., exp(?x2 /2) dx. g if

For two functions f (n) and g (n), write f ? g if limn→∞ f (n)/g (n) = 1 and f 0 < lim inf f (n)/g (n) ≤ lim sup f (n)/g (n) < ∞.
n→∞ n→∞

Our main result in this note may be formulated as follows. In what follows, we use the term almost surely to mean ‘with probability tending to 1 as n → ∞’. Theorem 1 Let b > 0 be a constant and p = n?b
√ n.

Then we almost surely have

α(P (n, p)) ? Φ(2b) ? Φ(?2b). |P (n, p)| 3

Using standard estimates, we may deduce the following numerical result from Theorem 1. Corollary 2 There is an absolute constant ε0 > 0 for which the following assertion holds. For any ?xed 0 < ε < ε0 , we have that lim P α(P (n, p)) ?ε |P (n, p)| 8 ≤ 3ε2 π = 1.


We shall in fact prove the the following structural result. Theorem 3 Almost surely, one may obtain a Sperner family of cardinality ? α(P (n, p)) from P (n, p) by taking all members of P (n, p) whose cardinalities are in the interval { n/2 ? √ √ b n , . . . , n/2+ b n }, and then removing from this family the elements that are contained in some other element of the family. The proofs of Theorems 1 and 3, which are quite simple and are self-contained, are given in Section 3.2. Since we would like to reach these proofs as soon as possible, our results are presented in a somewhat indirect order. We introduce the main concepts that we shall need and state the three technical lemmas that are required in the proofs of Theorems 1 and 3 in Section 3.2, and immediately give the half-page proof of Theorems 1 and 3. The remainder of this note is devoted to the proofs of the three technical lemmas. Our logarithms are natural logarithms.



In this section, we state some asymptotics involving binomial coe?cients. To simplify the notation, we shall often omit the and signs whenever they are not crucial. Moreover, we may and shall assume whenever needed that n is larger than any ?xed absolute constant. √ Let k , be integers with |k |, | | = O( n) and k + > 0. Then,
n 2

n n ? k, 2 ? , k +


n?k? n 2 ?k

n k+

2n n(k + )

en 2(k + )




For later reference, notice that the multinomial coe?cient on the left-hand side of (4) counts the number of pairs (A, B ) with A ? B ? [n], |A| = n/2 ? k , and |B | = |A| + k + . √ For integers k and m with k = O( m) and large enough m, the following rough bound holds: m 1 em k ≥ . (5) k m k 4

√ Let an integer i with |i| ≤ (log n) n and a real number b with 0 < b = O(1) be given. Then, for large n, we have √ √ b n n n 2|i| + b n √ √ ≤ 1+ n/2 + i n/2 + i + b n n/2 ? |i| ? b n + 1 5 log n √ √ b n = n 5b . ≤ exp (6) n For a set-system Q ? P (n) and an integer i with |i| ≤ n/2, denote by Qi the ( n/2 ? i)th layer of Q, i.e., Qi = {x: x ∈ Q and |x| = n/2 ? i}. For a set of integers S ? {? n/2 , . . . , n/2 }, let QS = i∈S Qi . The set QS will sometimes be viewed as a graph, where {x, y } is an edge in QS if and only if x ? y or y ? x. Instead of P (n, p)S we write PS (n, p), and instead of Q{i,j } we simply write Qi,j . Suppose 0 < p < 1 and 0 < ε < 1 are given, and let X be binomially distributed with parameters p and N . Then, the standard Cherno? bound for large deviations states that 1 P [|X ? N p| ≥ εN p] ≤ 2 exp ? ε2 N p 3 (7)

(see, e.g., [10, Corollary 2.3]). Routine calculations using the Cherno? bound give the following simple estimate on |Pi (n, p)|. Fact 4 Suppose p ≥ (2/3)n . Then, with probability at least 1 ? exp {?(5/4)n }, for every √ integer i with |i| ≤ (log n) n, we have |Pi (n, p)| = 1 + O 1 n n p. n/2 ? i


Main lemmas and the proofs of Theorems 1 and 3

We shall now introduce some key concepts and three lemmas that will allow us to prove Theorems 1 and 3. Since the lemmas are somewhat technical, their proofs are postponed to the Section 3.3. Let a positive integer n, reals 0 < ε(n) < 1, 0 < p(n) < 1, and c = c(n) > 0 be given. √ √ Let j be an integer with c n ≤ |j | ≤ (log n) n. De?ne i = i(j ) by putting √ i = j ? sgn(j ) 2c n , (8) √ where sgn(j ) denotes the sign of j . Note that, then, we have |j ? i| = 2c n and, moreover, |i| ≤ |j |. In what follows, we shall often be interested in the bipartite graph Qi,j with i and j as above. We now introduce some important de?nitions for what follows. We shall say that Q ? P (n) is (c, ε, p, j )-uniform if properties (a ) and (b ) below are ful?lled. 5

(a ) The number of vertices of Qi,j that have degree larger than (1 + ε) n/2 + |j | √ p 2c n

is at most 2 exp(?ε?1 )|Qj |. (b ) The number of vertices in Qj that have Qi,j -degree smaller than (1 ? ε) is at most exp(?ε?1 )|Qj |. The set-system Q ? P (n) will be called (c, ε, p)-uniform if the following properties are ful?lled: √ (i ) For all integers j with |j | ≤ (log n) n, we have |Qj | = (1 + Θ(1/n)) n p. n/2 ? j n/2 + |j | √ p 2c n

√ √ (ii ) Let S = {?n/2, . . . , ?(log n) n} ∪ {(log n) n, . . . , n/2}. Then |QS | ≤ 2n p/n. √ √ (iii ) For all integers j with c n ≤ |j | ≤ (log n) n, the set-system Q is (c, ε, p, j )-uniform. Now we state three lemmas that together imply Theorems 1 and 3. Lemma 5 Let c = c(n) > 0 with c = O(1) be given. Let p = n?c n (4c/e)2c n and √ √ put S = {?c n, . . . , c n}. Then, almost surely, the number of edges in PS (n, p) is at √ most 2n p/ n. Lemma 6 For c = c(n) > 0 with c = O(1), de?ne ε = 2?c n/2 , and p = n?c Then, almost surely, the random set-system P (n, p) is (c, ε, p)-uniform.
√ √ √ √ n (9c/e)2c n . √ √

Lemma 7 Let c = c(n) > 0 with c = O(1) be given. De?ne p = n?c n (9c/e)2c n and let 0 < ε ≤ 1/n be given. Assume that Q is (c, ε, p)-uniform. Then the width of Q is at most ? ? n n 2 ? ? p. +O n/2 ? j n √
|j |<c n


We now deduce Theorems 1 and 3 from Lemmas 5, 6, and 7. Proof of Theorems 1 and 3. Let b > 0 be given. De?ne c = c(n) by p=n
√ ?b n √ 2c n


√ ?c n

4c e


Then c = b + o(1). Let S be as in Lemma 5. Then removing from PS (n, p) all elements that are contained in some other element of PS (n, p) yields a Sperner subfamily S of P (n, p). By Fact 4 and Lemma 5 this subfamily is almost surely of cardinality at least 1+O 1 n n 2n p ? √ p ? (Φ(2c) ? Φ(?2c))2n p n/2 ? i n ? (Φ(2b) ? Φ(?2b))2n p. (9)

√ |i|≤c n

This establishes the lower bound in Theorem 1. We now observe the following: if we now prove that (9) is also an asymptotic an upper bound for the width of P (n, p), then the family S proves Theorem 3, as S is as described in the statement of that theorem. Let us therefore prove that (9) is indeed an upper bound for the width of P (n, p). We now de?ne c = c(n) by √ 2c n √ √ ?b n ? c n 9c p=n =n . e Again, c = b + o(1). By Lemmas 6 and 7, the width of P (n, p) is almost surely at most ? Φ(2c) ? Φ(?2c) + O 1 n 2n p ? (Φ(2b) ? Φ(?2b)) 2n p, 2

and hence (9) is an upper bound for the width of P (n, p), as required.


Proofs of the lemmas

It now remains to prove Lemmas 5, 6, and 7. √ Proof of Lemma 5. Denote by k, the sum over all pairs of integers k , with |k |, | | ≤ c n and k + > 0. For Q ? P (n), denote by XS (Q) the number of edges in QS . Then, by (4) and the comment immediately after that estimate regarding the multinomial coe?cient on the left-hand side of (4), we have E [XS (P (n, p))]

2n n(k + ) =O 2 n

en 2(k + )


p2 p2 = O 2n n?3/4 p .

n ? 3/4

e√ n 4c

√ 2c n


√ By Markov’s inequality, almost surely we have XS ≤ 2n p/ n, as required.


Proof of Lemma 6. Fact 4 immediately gives that condition (i ) holds almost surely. One may also easily check that condition (ii ) is almost surely satis?ed. To prove that condition (iii ) √ √ holds almost surely, it is enough to show that, for any j with c n ≤ |j | ≤ (log n) n, the set-system P (n, p) is (c, ε, p, j )-uniform with probability at least, say, 1 ? 1/n. √ √ In what follows, we ?x j with c n ≤ |j | ≤ (log n) n and bound from above the probability that P (n, p) is not (c, ε, p, j )-uniform. By symmetry, we may assume that j > 0 √ 2+ √ j and thus i = i(j ) in (8) is i = j ? 2c n . In particular, a set in Pj (n) contains n/ 2c n elements from Pi (n). For each x ∈ Pj (n), let Yx be the random variable whose value is the the number of neighbours of x in Pi (n, p) if x ∈ Pj (n, p), and 0 otherwise. For all x ∈ Pj (n), the random variable Yx conditioned on x ∈ Pj (n, p) is binomially distributed with parameters p and 2+ √ j . Furthermore, by (5), if n is large enough, N = n/ 2c n 1 Np ≥ n en √ 4c n
√ 2c n


√ ?c n

9c e

√ 2c n

≥ 22 c


= ε ?4 .


By (7), if X is binomially distributed with parameters p and N , 1 1 P [|X ? N p| ≥ εN p] ≤ 2 exp ? ε2 N p ≤ 2 exp ? ε?2 . 3 3 Denote by Z the number of elements in Pj (n, p) with degree larger than (1+ ε)N p or smaller than (1 ? ε)N p. By linearity of expectation, E [Z ] = O 1 n p · exp ? ε?2 n/2 ? j 3 .

By Markov’s inequality and Fact 4, the probability that Z > exp ?ε?1 |Pj (n, p)| is, very crudely, at most 1/2n. We have thus dealt with condition (b ) and one part of condition (a ). As to the remaining part of condition (a ), we notice that the degree of a vertex from Pi (n, p) in Pi,j (n, p) is binomially distributed with parameters p and n/2 ? i √ 2c n ≤ n/2 + |j | √ 2c n = N,

where we made use of the fact that |i| ≤ |j | = j . Hence the expected number of elements in Pi (n, p) with degree larger than (1 + ε)N p is, by (6), at most 1 2 exp ? ε?2 3 n 1 p ≤ 2 exp ? ε?2 n/2 + i 3 8 n pn10c , n/2 + j

provided n is large enough. Again, by Markov’s inequality and Fact 4, with probability at most 1/2n, more than exp ?ε?1 |Pj (n, p)| elements in Pi (n, p) have degree larger than (1+ ε)N p in Pi,j (n, p), and the lemma follows. 2 In the proof of Lemma 7 we need the following auxiliary result. Lemma 8 Let 0 < c(n) = O(1) be given. De?ne p = n?c n (9c/e)2c n . Let 0 < ε ≤ 1/n be √ √ given, and let Q be (c, ε, p, j )-uniform for some j with c n ≤ |j | ≤ (log n) n. De?ne i = i(j ) as in (8). Then there is a matching in Qi,j that covers all but at most 4ε|Qj | elements from Qj , as long as n is su?ciently large.
2+ √ |j | p. Call the resulting Proof. Remove all vertices of Qi,j of degree larger than (1 + ε) n/ 2c n set-system Ri,j . By (a ), the number of edges of Qi,j incident to the vertices that have been removed may be bounded from above, very crudely, by √ √

2 exp(?ε?1 )|Qj |

n √ 2c n

≤ 2 exp(?ε?1 )|Qj |n2c


≤ ε|Qj |p,

provided n is large enough. Using condition (b ), we see that the number of edges e(Ri,j ) in Ri,j is at least 1 ? exp(?ε?1 ) (1 ? ε)|Qj | n/2 + |j | n/2 + |j | √ √ p ? ε|Qj |p ≥ (1 ? 2ε)|Qj | p. 2c n 2c n

2+ √ |j | p. Since the edgeMoreover, Ri,j has maximum degree at most ?(Ri,j ) ≤ (1 + ε) n/ 2c n set of the bipartite graph Ri,j may be partitioned into ?(Ri,j ) matchings, the graph Ri,j contains a matching covering at least

e(Ri,j ) 1 ? 2ε ≥ |Qj | ≥ (1 ? 4ε)|Qj | ?(Ri,j ) 1+ε elements from Qj , provided n is large enough. 2

√ √ Proof of Lemma 7. For each j with c n ≤ |j | ≤ (log n) n, ?x a matching in Qi,j that covers all but ≤ 4ε|Qj | elements from Qj , as given by Lemma 8. Let R be the spanning subgraph of Q having as edges the union of all these matchings. A component in the graph R corresponds to a chain in Q, when Q is considered as a poset. Hence the width of Q is at most the number of components of R. The graph R is a disjoint union of paths. Therefore the number of components of R is just the number of vertices in R minus the number of edges in R. By properties (i ), (ii ), 9

and Lemma 8, the number of components of R is, therefore, almost surely at most
√ |j |≥(log n) n

|Qj | +

√ √ c n≤|j |<(log n) n

4ε|Qj | +

√ |j |<c n

|Qj | n ?p n/2 ? j 2

2n 1 ≤ ? +4 1+O n n and the lemma follows as ε ≤ 1/n.

1 ε2n + 1 + O n

√ |j |<c n



We are grateful to an anonymous referee for his or her comments. We are also grateful to Professor Bruce Rothschild for his generous handling of this note.

[1] Ian Anderson, Combinatorics of ?nite sets, The Clarendon Press Oxford University Press, New York, 1987. 1 [2] B? ela Bollob? as, Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. 1 [3] , Combinatorics, Cambridge University Press, Cambridge, 1986, Set systems, hypergraphs, families of vectors and combinatorial probability. 1 [4] B? ela Bollob? as and Graham Brightwell, Box-spaces and random partial orders, Trans. Amer. Math. Soc. 324 (1991), no. 1, 59–72. 1 [5] , The height of a random partial order: concentration of measure, Ann. Appl. Probab. 2 (1992), no. 4, 1009–1018. 1 [6] B? ela Bollob? as, Yoshiharu Kohayakawa, and Tomasz Luczak, On the diameter and radius of random subgraphs of the cube, Random Structures Algorithms 5 (1994), no. 5, 627–648. 1 [7] Graham Brightwell, Models of random partial orders, Surveys in combinatorics, 1993 (Keele), Cambridge Univ. Press, Cambridge, 1993, pp. 53–83. 1, 1 [8] Konrad Engel, Sperner theory, Cambridge University Press, Cambridge, 1997. 1 [9] James Allen Fill and Robin Pemantle, Percolation, ?rst-passage percolation and covering times for Richardson’s model on the n-cube, Ann. Appl. Probab. 3 (1993), no. 2, 593–629. 1 [10] Svante Janson, Tomasz Luczak, and Andrzej Ruci? nski, Random graphs, Wiley-Interscience, New York, 2000. 1, 3.1 [11] Y. Kohayakawa, B. Kreuter, and D. Osthus, The length of random subsets of Boolean lattices, Random Structures Algorithms 16 (2000), no. 2, 177–194. 1, 1 [12] B. Kreuter, Small sublattices in random subsets of Boolean lattices, Random Structures Algorithms 13 (1998), no. 3-4, 383–407. 1


[13] D. Lubell, A short proof of Sperner’s lemma, J. Combinatorial Theory 1 (1966), 299. 1 [14] Deryk Osthus, Maximum antichains in random subsets of a ?nite set, J. Combin. Theory Ser. A 90 (2000), no. 2, 336–346. 1 [15] A. R? enyi, On random subsets of a ?nite set, Mathematica (Cluj) 3 (1961), 355–362. 1 [16] Stanislaw M. Ulam, Monte Carlo calculations in problems of mathematical physics, Modern mathematics for the engineer: Second series, McGraw-Hill, New York, 1961, pp. 261–281. 1


Games of chains and cutsets in the Boolean lattice.pdf
chains and cutsets in the Boolean lattice_专业...lattice of order n, the width (the a maximum ...of all the subsets of [n] ordered by inclusion...
Matroid Theory and Its Applications.pdf
The lattice of all intersections of subsets of H[Φ], ordered by reverse...Zaslavsky, “Signed graphs”, submitted. Proofs of the Matroid, Covering, ...
Lattice games J. M..pdf
The basic players are the nonzero join-irreducible elements of the lattice ...are the subsets of the set N and 2N ; [; \ form a Boolean algebra....
Mass problems and intuitionism.pdf
A pseudo-Boolean algebra is a lattice L such ...Muchnik degrees of nonempty Π0 subsets of 2ω...random reals, Theorem 8.12 of Simpson [39] ...
-?lters (introduced in [1]) are isomorphic lattices. In the study of ...subsets of X (= clopen) is a basis for X and it is a Boolean ...
c [B).pdf
a topological space and A, B denote subsets of...lattice and p , q denote elements of the ...Boolean properties of sets. Journal of Formalized ...
...theory based on completeresiduated lattice-value....pdf
A special residuated lattice is the Boolean ...nition of residuated lattice-valued logic and ...subsets of X , respectively; | X | denotes ...
Complemented ordered sets.pdf
We introduce the concept of complementary elements ...then the subsets ; and S are complementary; (2...Fig. 4 are boolean sets wich are not lattices....
...Multiple-Valued Model-Checking Using Lattice Rep....pdf
ne the concept of multiple-valued sets over quasi-boolean lattices and give...are subsets of some U , we denote the classical complement of a set S ...
A topological characterization of the stable and mi....pdf
Boolean equations which are satisfied by those ...of degrees realized in ri o subsets of U u. ...lattices, with 2 t: regarded as a lattice ...
Mining Reliable Models of Associations in Dynamic D....pdf
the data is a random sample drawn from an ...where and are subsets of , is obtained by . ...lattice of itemsets into smaller sub-lattices, ...
Multiple description lattice vector quantization.pdf
We consider the problem of designing a lattice-...subsets of working/nonworking channels), ...It was shown in 12], via a random coding ...
More on the lattice of many sorted equivalence rela....pdf
More on the lattice of many sorted equivalence ...(M ) is a family of many sorted subsets of ...Boolean properties of sets. Formalized ‘ ...
We show that the set of such subsets of P H...fact by using the method of random restrictions..... Entailment relations and distributive lattices. ...
the homology of the h-complex of a Boolean ...certain classes of supersolvable lattices are ...subsets of {1, . . . , n} by inclusion. ...
On the f-vectors of Cutsets in the Boolean Lattice.pdf
On the f-vectors of Cutsets in the Boolean Lattice_专业资料。A cutset in the poset 2 [n], of subsets of {1,..., n} ordered by inclusion, ...
...bipartite graphs and sublattices of the Boolean lattices_....pdf
Unmixed bipartite graphs and sublattices of the Boolean lattices_专业资料。...The width of random su... 暂无评价 11页 免费 喜欢此文档的还喜欢 Sub...
of Isomorphic Lattices 111 110 101 010 100 000 ...For any subsets V,T, V?T iff. aV|aT, and...satisfied, the poset is not a Boolean algebra. ...
Complete Lattices.pdf
In the ?rst section the lattice of subsets of distinct set is introduced....It is shown that this lattice is Boolean, i.e. distributive and ...
Université Catholique de Louvain The Lattice of Do....pdf
For a given topological space all its closed domains form a Boolean lattice...In the beginning some useful theorems about subsets of topological spaces are...

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。