Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIncomparable copies of a poset in the Boolean lattice
148
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $B_n$ be the poset generated by the subsets of $[n]$ with the inclusion as relation and let $P$ be a finite poset. We want to embed $P$ into $B_n$ as many times as possible such that the subsets in different copies are incomparable. The maximum number of such embeddings is asymptotically determined for all finite posets $P$ as $frac{{n choose lfloor n/2rfloor}}{M(P)}$, where $M(P)$ denotes the minimal size of the convex hull of a copy of $P$. We discuss both weak and strong (induced) embeddings.
rate research
Read More
The maximum size, $La(n,P)$, of a family of subsets of $[n]={1,2,...,n}$ without containing a copy of $P$ as a subposet, has been intensively studied. Let $P$ be a graded poset. We say that a family $mathcal{F}$ of subsets of $[n]={1,2,...,n}$ contains a emph{rank-preserving} copy of $P$ if it contains a copy of $P$ such that elements of $P$ having the same rank are mapped to sets of same size in $mathcal{F}$. The largest size of a family of subsets of $[n]={1,2,...,n}$ without containing a rank-preserving copy of $P$ as a subposet is denoted by $La_{rp}(n,P)$. Clearly, $La(n,P) le La_{rp}(n,P)$ holds. In this paper we prove asymptotically optimal upper bounds on $La_{rp}(n,P)$ for tree posets of height $2$ and monotone tree posets of height $3$, strengthening a result of Bukh in these cases. We also obtain the exact value of $La_{rp}(n,{Y_{h,s},Y_{h,s}})$ and $La(n,{Y_{h,s},Y_{h,s}})$, where $Y_{h,s}$ denotes the poset on $h+s$ elements $x_1,dots,x_h,y_1,dots,y_s$ with $x_1<dots<x_h<y_1,dots,y_s$ and $Y_{h,s}$ denotes the dual poset of $Y_{h,s}$.
Let $mathrm{G}$ be a subgroup of the symmetric group $mathfrak S(U)$ of all permutations of a countable set $U$. Let $overline{mathrm{G}}$ be the topological closure of $mathrm{G}$ in the function topology on $U^U$. We initiate the study of the poset $overline{mathrm{G}}[U]:={f[U]mid fin overline{mathrm{G}}}$ of images of the functions in $overline{mathrm{G}}$, being ordered under inclusion. This set $overline{mathrm{G}}[U]$ of subsets of the set $U$ will be called the emph{poset of copies for} the group $mathrm{G}$. A denomination being justified by the fact that for every subgroup $mathrm{G}$ of the symmetric group $mathfrak S(U)$ there exists a homogeneous relational structure $R$ on $U$ such that $overline G$ is the set of embeddings of the homogeneous structure $R$ into itself and $overline{mathrm{G}}[U]$ is the set of copies of $R$ in $R$ and that the set of bijections $overline Gcap mathfrak S(U)$ of $U$ to $U$ forms the group of automorphisms of $mathrm{R}$.
A subposet $Q$ of a poset $Q$ is a textit{copy of a poset} $P$ if there is a bijection $f$ between elements of $P$ and $Q$ such that $x le y$ in $P$ iff $f(x) le f(y)$ in $Q$. For posets $P, P$, let the textit{poset Ramsey number} $R(P,P)$ be the smallest $N$ such that no matter how the elements of the Boolean lattice $Q_N$ are colored red and blue, there is a copy of $P$ with all red elements or a copy of $P$ with all blue elements. Axenovich and Walzer introduced this concept in textit{Order} (2017), where they proved $R(Q_2, Q_n) le 2n + 2$ and $R(Q_n, Q_m) le mn + n + m$, where $Q_n$ is the Boolean lattice of dimension $n$. They later proved $2n le R(Q_n, Q_n) le n^2 + 2n$. Walzer later proved $R(Q_n, Q_n) le n^2 + 1$. We provide some improved bounds for $R(Q_n, Q_m)$ for various $n,m in mathbb{N}$. In particular, we prove that $R(Q_n, Q_n) le n^2 - n + 2$, $R(Q_2, Q_n) le frac{5}{3}n + 2$, and $R(Q_3, Q_n) le frac{37}{16}n + frac{39}{16}$. We also prove that $R(Q_2,Q_3) = 5$, and $R(Q_m, Q_n) le (m - 2 + frac{9m - 9}{(2m - 3)(m + 1)})n + m + 3$ for all $n ge m ge 4$.
The partition lattice and noncrossing partition lattice are well studied objects in combinatorics. Given a graph $G$ on vertex set ${1,2,dots, n}$, its bond lattice, $L_G$, is the subposet of the partition lattice formed by restricting to the partitions whose blocks induce connected subgraphs of $G$. In this article, we introduce a natural noncrossing analogue of the bond lattice, the noncrossing bond poset, $NC_G$, obtained by restricting to the noncrossing partitions of $L_G$. Both the noncrossing partition lattice and the bond lattice have many nice combinatorial properties. We show that, for several families of graphs, the noncrossing bond poset also exhibits these properties. We present simple necessary and sufficient conditions on the graph to ensure the noncrossing bond poset is a lattice. Additionally, for several families of graphs, we give combinatorial descriptions of the Mobius function and characteristic polynomial of the noncrossing bond poset. These descriptions are in terms of a noncrossing analogue of non-broken circuit (NBC) sets of the graphs and can be thought of as a noncrossing version of Whitneys NBC theorem for the chromatic polynomial. We also consider the shellability and supersolvability of the noncrossing bond poset, providing sufficient conditions for both. We end with some open problems.
The abstract induced subgraph poset of a graph is the isomorphism class of the induced subgraph poset of the graph, suitably weighted by subgraph counting numbers. The abstract bond lattice and the abstract edge-subgraph poset are defined similarly by considering the lattice of subgraphs induced by connected partitions and the poset of edge-subgraphs, respectively. Continuing our development of graph reconstruction theory on these structures, we show that if a graph has no isolated vertices, then its abstract bond lattice and the abstract induced subgraph poset can be constructed from the abstract edge-subgraph poset except for the families of graphs that we characterise. The construction of the abstract induced subgraph poset from the abstract edge-subgraph poset generalises a well known result in reconstruction theory that states that the vertex deck of a graph with at least 4 edges and without isolated vertices can be constructed from its edge deck.12
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
