9512.net

# 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).

1

Introduction

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 . 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 . 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).
? ?

1

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 .

(1)

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  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  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 , which may be thought of as a modern sequel to R? enyi’s pioneering work . For the background from the theory of random graphs, see Bollob? as  and Janson, Luczak, and Ruci? nski . 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 . 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  (see [5, 7] for further references). The ?avour of the arguments in  are, however, closer to the ones in Fill and Pemantle  and Bollob? as, Kohayakawa and Luczak .

Further results
Soon after the results in this note were obtained, Osthus  discovered a powerful method of proof inspired in Lubell’s beautiful proof  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  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.,  and .

2

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.

n→∞

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.

3
3.1

Proofs
Preliminaries

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 + )

k+

.

(4)

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

3.2

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

6

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

=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.

3.3

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))]
k,

2n n(k + ) =O 2 n

en 2(k + )

k+

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

n ? 3/4

e√ n 4c

√ 2c n

7

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

2

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

n

√ ?c n

9c e

√ 2c n

≥ 22 c

n

= ε ?4 .

(10)

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

n

≤ ε|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

4

Acknowledgements

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.

References
 Ian Anderson, Combinatorics of ?nite sets, The Clarendon Press Oxford University Press, New York, 1987. 1  B? ela Bollob? as, Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. 1  , Combinatorics, Cambridge University Press, Cambridge, 1986, Set systems, hypergraphs, families of vectors and combinatorial probability. 1  B? ela Bollob? as and Graham Brightwell, Box-spaces and random partial orders, Trans. Amer. Math. Soc. 324 (1991), no. 1, 59–72. 1  , The height of a random partial order: concentration of measure, Ann. Appl. Probab. 2 (1992), no. 4, 1009–1018. 1  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  Graham Brightwell, Models of random partial orders, Surveys in combinatorics, 1993 (Keele), Cambridge Univ. Press, Cambridge, 1993, pp. 53–83. 1, 1  Konrad Engel, Sperner theory, Cambridge University Press, Cambridge, 1997. 1  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  Svante Janson, Tomasz Luczak, and Andrzej Ruci? nski, Random graphs, Wiley-Interscience, New York, 2000. 1, 3.1  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  B. Kreuter, Small sublattices in random subsets of Boolean lattices, Random Structures Algorithms 13 (1998), no. 3-4, 383–407. 1

10

 D. Lubell, A short proof of Sperner’s lemma, J. Combinatorial Theory 1 (1966), 299. 1  Deryk Osthus, Maximum antichains in random subsets of a ?nite set, J. Combin. Theory Ser. A 90 (2000), no. 2, 336–346. 1  A. R? enyi, On random subsets of a ?nite set, Mathematica (Cluj) 3 (1961), 355–362. 1  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

11 更多相关文章：

isomorphic to the Galois lattice of (X; X; )...We denote by 2X the set of all subsets of X...boolean lattice, we obtain an isomorphic boolean ...
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  ...
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....
2. Closed Subsets of a Lattice ? ? ? ? Let D be a non empty set ...(12) Let L1 , L2 be Boolean lattices. Suppose the lattice structure of ...
we mean the class of k-element subsets of S....Submitted. ? B. Bollobas, On generalized graphs...., Logarithmic order of free distributive lattices....
Set Overlap in Mining of Frequent Itemsets.pdf
To reduce the cost, the following property is used: every subsets of a ...Our interest is focused on the algorithm based on closed itemset lattice, ...
The deduction theorem for quantum logic { some nega....pdf
of orthomodular lattices admits the deduction ...the subsets of A such that the model (matrix)...lantern and the sixteen-element Boolean algebra 24...
On the coherence of supremum preserving upper previ....pdf
xg, x 2 R. An ample eld R on 5, 20] is a class of subsets of ...( ; R) is a complete joinmorphism 4] between the complete lattices (R;...

structure and localization of electronic states in ...vefold symmetric quasilattice is constructed by ...ve identical subsets and analyze the spectral ...
Compactness of Lim-inf Topology.pdf
{inf B; B ranges over subsets of L: B ∈ ...Let us observe that every top-lattice which is ...Suppose the carrier of L1 = the carrier of L2...
Beitrage zur Algebra und Geometrie Contributions to....pdf
The ingredients of the 2-dimensional case of this theorem are a lattice ...(3) where A1 ; : : : ; An are cyclic subsets of the nite abelian ...
Improved inclusion-exclusion identities via closure....pdf
In the proof of his famous inclusion-exclusion variant for semilattices, ...Evidently, subsets of are closed. A base of is a minimal non-empty ...
Nontrivial fixed point in nonabelian models.pdf
percolation properties of certain subsets of the target spin manifold . This was presented at the 1992 lattice conference together with nonrigorous ...
...theory and for weakly associative lattices.pdf
rings, lattices and Boolean algebras are de ned by equational identities. Such...of candidates and ran Otter searches with members or subsets of the ...
08-Finite Boolean algebra_图文.ppt
(P(S),?) is a lattice For any subsets of S, S1 and S2, S1∪S2 is the (unique) least upper bound of S1 and S2; and S1∩S2 is the (...
...Equations with General Operators on the Unit Int....pdf
of the general fuzzy relation equations introduced....Given an ordered set (A, ≤) and subsets S1 ...Note that when (A, ≤) is a complete lattice...
Representable posets and their order components.pdf
lattice such that its ordered set of prime ...the Stone space of a countable atomless Boolean ...subsets of the rational interval (0, 1) ordered...
Partially ordered monads and powerset Kleene algebras.pdf
(1) The powerset monad Let L be a completely distributive lattice. For ..., where P X is the set of subsets of X, ηX (x) = {x} and ?X...
Gridigrator A Very Fast Volume Renderer for 3D Scal....pdf
to select subsets of the data to gridigrate, ...curvilinear lattice and a deposition function speci...Curvilinear Volumes,”, submitted for publication. ...
Direct decompositions of non-algebraic complete lattices.pdf
? Denote by Sp (A) the lattice of algebraic subsets of a complete lattice A. If A is Boolean, then Sp (A) is subdirectly irreducible (Proposition...