The Experts below are selected from a list of 6144 Experts worldwide ranked by ideXlab platform
William T. Trotter - One of the best experts on this subject based on the ideXlab platform.
-
the dimension of suborders of the Boolean Lattice
Order, 1994Co-Authors: Graham R. Brightwell, Alexandr V. Kostochka, Henry A. Kierstead, William T. TrotterAbstract:We consider the order dimension of suborders of the Boolean LatticeB n . In particular we show that the suborder consisting of the middle two levels ofB n dimension at most of 6 log3 n. More generally, we show that the suborder consisting of levelss ands+k ofB n has dimensionO(k 2 logn).
Shahriar Shahriari - One of the best experts on this subject based on the ideXlab platform.
-
Partitioning the Boolean Lattice into a minimal number of chains of relatively uniform size
European Journal of Combinatorics, 2003Co-Authors: Tim Hsu, Shahriar Shahriari, Mark J. Logan, Christopher TowseAbstract:Let 2[n] denote the Boolean Lattice of order n, that is, the poset of subsets of {1,..., n} ordered by inclusion. Extending our previous work on a question of Furedi, we show that for any c > 1, there exist functions e(n) ∼ √n/2 and f(n)∼ c√n log n and an integer N (depending only on c) such that for all n < N, there is a chain decomposition of the Boolean Lattice 2[n] into (n ⌊n/2⌋) chains, all of which have size between e(n) and f(n). (A positive answer to Furedi's question would imply that the same result holds for some e(n) ∼ √π/2 √n and f(n) = e(n) + 1.) The main tool used is an apparently new observation about rank-collection in normalized matching (LYM) posets.
-
Width and f-vectors of Cutsets in the Truncated Boolean Lattice☆
Electronic Notes in Discrete Mathematics, 2002Co-Authors: Shahriar ShahriariAbstract:In this paper we will survey a collection of recent results about chains and cutsets in the Boolean Lattice and some other posets. In particular, we consider the possibilities for the width (i.e., the size of the largest anti-chain) and the f-vectors (i.e., the number of subsets of various sizes) of cutsets. Given k chains in the Boolean Lattice, we will also consider the possible number of pair-wise disjoint maximal chains that do not intersect the given k chains.
-
Partitioning the Boolean Lattice into Chains of Large Minimum Size
Journal of Combinatorial Theory Series A, 2002Co-Authors: Tim Hsu, Shahriar Shahriari, Mark J. Logan, Christopher TowseAbstract:Let 2n] denote the Boolean Lattice of order n, that is, the poset of subsets of {1, ?, n} ordered by inclusion. Recall that 2n] may be partitioned into what we call the canonical symmetric chain decomposition (due to de Bruijn, Tengbergen, and Kruyswijk), or CSCD. Motivated by a question of Furedi, we show that there exists a function d(n)~12n such that for any n?0, 2n] may be partitioned into (n?n/2?) chains of size at least d(n). (For comparison, a positive answer to Furedi's question would imply that the same result holds for some d(n)~?/2n.) More precisely, we first show that for 0?j?n, the union of the lowest j+1 elements from each of the chains in the CSCD of 2n] forms a poset Tj(n) with the normalized matching property and log-concave rank numbers. We then use our results on Tj(n) to show that the nodes in the CSCD chains of size less than 2d(n) may be repartitioned into chains of large minimum size, as desired.
-
Games of Chains and Cutsets in the Boolean Lattice II
Order, 2001Co-Authors: Shahriar ShahriariAbstract:Let 2 ^[ n ] denote the poset of all subsets of [ n ]={1,2,..., n } ordered by inclusion. Following Gutterman and Shahriari ( Order 14, 1998, 321–325 ) we consider a game G _ n ( a , b , c ). This is a game for two players. First, Player I constructs a independent maximal chains in 2 ^[ n ]. Player II will extend the collection to a + b independent maximal chains by finding another b independent maximal chains in 2 ^[ n ]. Finally, Player I will attempt to extend the collection further to a + b + c such chains. The last Player who is able to complete her move wins. In this paper, we complete the analysis of G _ n ( a , b , c ) by considering its most difficult instance: when c =2 and a + b +2= n . We prove, the rather surprising result, that, for n ≥7, Player I wins G _ n ( a , n − a −2,2) if and only if a ≥3. As a consequence we get results about extending collections of independent maximal chains, and about cutsets (collections of subsets that intersect every maximal chain) of minimum possible width (the size of largest anti-chain).
-
on the f vectors of cutsets in the Boolean Lattice
Journal of Combinatorial Theory Series A, 2001Co-Authors: Matthew Haines, Shahriar ShahriariAbstract:A cutset in the poset 2[n], of subsets of {1, ?, n} ordered by inclusion, is a subset of 2[n] that intersects every maximal chain. Let 0???1 be a real number. Is it possible to find a cutset in 2[n] that, for each 0?i?n, contains at most ? (ni) subsets of size i? Let ?(n) be the greatest lower bound of all real numbers for which the answer is positive. In this note we prove the rather surprising fact that limn?∞?(n)=0.
István Tomon - One of the best experts on this subject based on the ideXlab platform.
-
Packing the Boolean Lattice with copies of a poset
Journal of the London Mathematical Society, 2019Co-Authors: István TomonAbstract:Let $P$ be a partially ordered set. We prove that if $n$ is sufficiently large, then there exists a packing $\mathcal{P}$ of copies of $P$ in the Boolean Lattice $(2^{[n]},\subset)$ that covers almost every element of $2^{[n]}$: $\mathcal{P}$ might not cover the minimum and maximum of $2^{[n]}$, and at most $|P|-1$ additional points due to divisibility. In particular, if $|P|$ divides $2^{n}-2$, then the truncated Boolean Lattice $2^{[n]}-\{\emptyset,[n]\}$ can be partitioned into copies of $P$. This confirms a conjecture of Lonc from 1991.
-
Partitioning the Boolean Lattice into copies of a poset
Journal of Combinatorial Theory Series A, 2019Co-Authors: Vytautas Gruslys, Imre Leader, István TomonAbstract:Abstract Let P be a poset of size 2 k that has a greatest and a least element. We prove that, for sufficiently large n, the Boolean Lattice 2 [ n ] can be partitioned into copies of P. This resolves a conjecture of Lonc.
-
Tiling the Boolean Lattice with copies of a poset
Electronic Notes in Discrete Mathematics, 2017Co-Authors: Vytautas Gruslys, Imre Leader, István TomonAbstract:Abstract Let P be a partially ordered set with a unique maximal and minimal element, and size 2m, where m is a positive integer. Settling a conjecture of Lonc, we prove that if n is sufficiently large, then the Boolean Lattice 2[n] can be partitioned into isomorphic copies of P. Also, we show that if P has a unique maximum and minimum, but the size of P not necessarily a power of 2, then there exists a constant c = c(P) such that all but at most c elements of 2[n] can be covered by disjoint copies of P.
-
Almost tiling of the Boolean Lattice with copies of a poset
arXiv: Combinatorics, 2016Co-Authors: István TomonAbstract:Let $P$ be a partially ordered set. If the Boolean Lattice $(2^{[n]},\subset)$ can be partitioned into copies of $P$ for some positive integer $n$, then $P$ must satisfy the following two trivial conditions: (1) the size of $P$ is a power of $2$, (2) $P$ has a unique maximal and minimal element. Resolving a conjecture of Lonc, it was shown by Gruslys, Leader and Tomon that these conditions are sufficient as well. In this paper, we show that if $P$ only satisfies condition (2), we can still almost partition $2^{[n]}$ into copies of $P$. We prove that if $P$ has a unique maximal and minimal element, then there exists a constant $c=c(P)$ such that all but at most $c$ elements of $2^{[n]}$ can be covered by disjoint copies of $P$.
-
Decompositions of the Boolean Lattice into Rank-symmetric Chains
The Electronic Journal of Combinatorics, 2016Co-Authors: István TomonAbstract:The Boolean Lattice $2^{[n]}$ is the power set of $[n]$ ordered by inclusion. A chain $c_{0}\subset\cdots\subset c_{k}$ in $2^{[n]}$ is rank-symmetric, if $|c_{i}|+|c_{k-i}|=n$ for $i=0,\ldots,k$; and it is symmetric, if $|c_{i}|=(n-k)/2+i$. We show that there exist a bijection $$p: [n]^{(\geq n/2)}\rightarrow [n]^{(\leq n/2)}$$ and a partial ordering $
Alexandr V. Kostochka - One of the best experts on this subject based on the ideXlab platform.
-
the dimension of interior levels of the Boolean Lattice ii
Order, 1998Co-Authors: Alexandr V. Kostochka, L A TalyshevaAbstract:Extending an old lemma by Dushnik, we establish the dimension d(3, k; n) of the containment order generated by the 3-element and k-element subsets of an n-element set for most k between \(2\sqrt n\) and n.
-
The Dimension of Neighboring Levels of the Boolean Lattice
Order, 1997Co-Authors: Alexandr V. KostochkaAbstract:The order dimension of suborders of the Boolean Lattice\(B_n \) is considered. It is shown that the suborder of\(B_n \) consisting of levels s and s+1 has dimension O(\log n/log log n). This improves a bound in [1].
-
the dimension of suborders of the Boolean Lattice
Order, 1994Co-Authors: Graham R. Brightwell, Alexandr V. Kostochka, Henry A. Kierstead, William T. TrotterAbstract:We consider the order dimension of suborders of the Boolean LatticeB n . In particular we show that the suborder consisting of the middle two levels ofB n dimension at most of 6 log3 n. More generally, we show that the suborder consisting of levelss ands+k ofB n has dimensionO(k 2 logn).
-
the dimension of interior levels of the Boolean Lattice
Order, 1994Co-Authors: Glenn Hurlbert, Alexandr V. Kostochka, L A TalyshevaAbstract:LetP(k,r;n) denote the containment order generated by thek-element andr-element subsets of ann-element set, and letd(k,r;n) be its dimension. Previous research in this area has focused on the casek=1.P(1,n−1;n) is the standard example of ann-dimensional poset, and Dushnik determined the value ofd(1,r;n) exactly, whenr⩾2\(\sqrt n \). Spencer used the Erdos-Szekeres theorem to show thatd(1, 2;n) ∼ lg lgn, and he used the concept of scrambling families of sets to show thatd(1,r;n)=Θ(lg lgn) for fixedr. Furedi, Hajnal, Rodl and Trotter proved thatd(1, 2;n)=lg lgn+(1/2+o(1))lg lg lgn. In this paper, we concentrate on the casek⩾2. We show thatP(2,n−2;n) is (n−1)-irreducible, and we investigated(2,r;n) whenr⩾2\(\sqrt {n - 1} \), obtaining the exact value for almost allr.
Graham R. Brightwell - One of the best experts on this subject based on the ideXlab platform.
-
The Number of Linear Extensions of the Boolean Lattice
Order, 2003Co-Authors: Graham R. Brightwell, Prasad TetaliAbstract:Let L ( Q ^ t ) denote the number of linear extensions of the t -dimensional Boolean Lattice Q ^ t . We use the entropy method of Kahn to show that $$\frac{{\log (L(Q^t ))}}{{2^t }} = \log \left(\begin{gathered} t \hfill \\ \left| \!{\underline {\, t \,}} \right. /\left. {\underline {\, 2 \,}}\! \right| \hfill \\ \end{gathered} \right) - \frac{3} {2}\log e + o(1),$$ where the logarithms are base 2. We also find the exact maximum number of linear extensions of a d -regular bipartite order on n elements, in the case when n is a multiple of 2 d .
-
the dimension of suborders of the Boolean Lattice
Order, 1994Co-Authors: Graham R. Brightwell, Alexandr V. Kostochka, Henry A. Kierstead, William T. TrotterAbstract:We consider the order dimension of suborders of the Boolean LatticeB n . In particular we show that the suborder consisting of the middle two levels ofB n dimension at most of 6 log3 n. More generally, we show that the suborder consisting of levelss ands+k ofB n has dimensionO(k 2 logn).