Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLargest family without a pair of posets on consecutive levels of the Boolean lattice
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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)$.
rate research
Read More
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$ with $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 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.
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. Similarly, $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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
