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

? ?

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 [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].

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

[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

10

[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

11

- The length of random subsets of Boolean lattices. Random Structures Algorithms 16
- How special are Cohen and random forcings i.e. Boolean algebras of the family of subsets of
- Computation of the Bisection Width for Random d-Regular Graphs J. Daz 1
- Absence of diffusion in certain random lattices Numerical evidence
- The number of boolean functions computed by formulas of a given size. Random Structures and
- The circular topology of rhythm in asynchronous random boolean networks
- The Role of Redundancy in the Robustness of Random Boolean Networks
- On the Threshold of Chaos in Random Boolean Cellular Automata
- Optimization and Physics On the satisfiability of random Boolean formulae
- Analysis of random Boolean networks using the average sensitivity

更多相关文章：
**
科学文献.pdf
**

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 [39] ...**
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*....**
Polish Academy ***of* Sciences.pdf

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* ...**
Address for editorial correspondence.pdf
**

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;...**
带结构 模型 非晶.pdf
**

structure and localization*of* electronic states in ...vefold symmetric quasi*lattice* 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 semi*lattices,* ...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 [1]. 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...

isomorphic to

A pseudo-

We introduce

2. Closed

we mean

To reduce

xg, x 2 R. An ample eld R on 5, 20] is a class

structure and localization

{inf B; B ranges over

In

percolation properties

rings

(P(S),?) is a

(1)

to select

? Denote by Sp (A)