ترغب بنشر مسار تعليمي؟ اضغط هنا

Largest family without a pair of posets on consecutive levels of the Boolean lattice

62   0   0.0 ( 0 )
 نشر من قبل Jimeng Xiao
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

Suppose $k ge 2$ is an integer. Let $Y_k$ be the poset with elements $x_1, x_2, y_1, y_2, ldots, y_{k-1}$ such that $y_1 < y_2 < cdots < y_{k-1} < x_1, x_2$ and let $Y_k$ be the same poset but all relations reversed. We say that a family of subsets of $[n]$ contains a copy of $Y_k$ on consecutive levels if it contains $k+1$ subsets $F_1, F_2, G_1, G_2, ldots, G_{k-1}$ such that $G_1subset G_2 subset cdots subset G_{k-1} subset F_1, F_2$ and $|F_1| = |F_2| = |G_{k-1}|+1 =|G_{k-2}|+ 2= cdots = |G_{1}|+k-1$. If both $Y_k$ and $Y_k$ on consecutive levels are forbidden, the size of the largest such family is denoted by $mathrm{La}_{mathrm{c}}(n, Y_k, Y_k)$. In this paper, we will determine the exact value of $mathrm{La}_{mathrm{c}}(n, Y_k, Y_k)$.



قيم البحث

اقرأ أيضاً

Given posets $mathbf{P}_1,mathbf{P}_2,ldots,mathbf{P}_k$, let the {em Boolean Ramsey number} $R(mathbf{P}_1,mathbf{P}_2,ldots,mathbf{P}_k)$ be the minimum number $n$ such that no matter how we color the elements in the Boolean lattice $mathbf{B}_n$ w ith $k$ colors, there always exists a poset $mathbf{P}_i$ contained in $mathbf{B}_n$ whose elements are all colored with $i$. This function was first introduced by Axenovich and Walzer~cite{AW}. Recently, many results on determining $R(mathbf{B}_m,mathbf{B}_n)$ have been published. In this paper, we will study the function $R(mathbf{P}_1,mathbf{P}_2,ldots,mathbf{P}_k)$ for each $mathbf{P}_i$s being the $V$-shaped poset. That is, a poset obtained by identifying the minimal elements of two chains. Another major result presented in the paper is to determine the minimal posets $mathbf{Q}$ contained in $mathbf{B}_n$, when $R(mathbf{P}_1,mathbf{P}_2,ldots,mathbf{P}_k)=n$ is determined, having the Ramsey property described in the previous paragraph. In addition, we define the {em Boolean rainbow Ramsey number} $RR(mathbf{P},mathbf{Q})$ the minimum number $n$ such that when arbitrarily coloring the elements in $mathbf{B}_n$, there always exists either a monochromatic $mathbf{P}$ or a rainbow $mathbf{Q}$ contained in $mathbf{B}_n$. The upper bound for $RR(mathbf{P},mathbf{A}_k)$ was given by Chang, Li, Gerbner, Methuku, Nagy, Patkos, and Vizer for general poset $mathbf{P}$ and $k$-element antichain $mathbf{A}_k$. We study the function for $mathbf{P}$ being the $V$-shaped posets in this paper as well.
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 n umber 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.
For a graph $G,$ we consider $D subset V(G)$ to be a porous exponential dominating set if $1le sum_{d in D}$ $left( frac{1}{2} right)^{text{dist}(d,v) -1}$ for every $v in V(G),$ where dist$(d,v)$ denotes the length of the smallest $dv$ path. Similar ly, $D subset V(G)$ is a non-porous exponential dominating set is $1le sum_{d in D} left( frac{1}{2} right)^{overline{text{dist}}(d,v) -1}$ for every $v in V(G),$ where $overline{text{dist}}(d,v)$ represents the length of the shortest $dv$ path with no internal vertices in $D.$ The porous and non-porous exponential dominating number of $G,$ denoted $gamma_e^*(G)$ and $gamma_e(G),$ are the minimum cardinality of a porous and non-porous exponential dominating set, respectively. The consecutive circulant graph, $C_{n, [ell]},$ is the set of $n$ vertices such that vertex $v$ is adjacent to $v pm i mod n$ for each $i in [ell].$ In this paper we show $gamma_e(C_{n, [ell]}) = gamma_e^*(C_{n, [ell]}) = leftlceil tfrac{n}{3ell +1} rightrceil.$
Frankl and Furedi (1989) conjectured that the $r$-graph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest graph-Lagrangian of all $r$-graphs with $m$ edges. In this paper, we establish some bounds for graph-Lagrangians of some special $r$-graphs that support this conjecture.
For any graded poset $P$, we define a new graded poset, $mathcal E(P)$, whose elements are the edges in the Hasse diagram of P. For any group, $G$, acting on the boolean algebra, $B_n$, we conjecture that $mathcal E(B_n/G)$ is Peck. We prove that the conjecture holds for common cover transitive actions. We give some infinite families of common cover transitive actions and show that the common cover transitive actions are closed under direct and semidirect products.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا