Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPoset Ramsey Numbers for Boolean Lattices
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
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.
In this paper, we consider a variant of Ramsey numbers which we call complementary Ramsey numbers $bar{R}(m,t,s)$. We first establish their connections to pairs of Ramsey $(s,t)$-graphs. Using the classification of Ramsey $(s,t)$-graphs for small $s,t$, we determine the complementary Ramsey numbers $bar{R}(m,t,s)$ for $(s,t)=(4,4)$ and $(3,6)$.
Given graphs $G$ and $H$ and a positive integer $k$, the emph{Gallai-Ramsey number}, denoted by $gr_{k}(G : H)$ is defined to be the minimum integer $n$ such that every coloring of $K_{n}$ using at most $k$ colors will contain either a rainbow copy of $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G in {P_{4}, P_{5}}$. In the case where $G = P_{4}$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G = P_{5}$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.
Given graphs $H_1, dots, H_t$, a graph $G$ is $(H_1, dots, H_t)$-Ramsey-minimal if every $t$-coloring of the edges of $G$ contains a monochromatic $H_i$ in color $i$ for some $iin{1, dots, t}$, but any proper subgraph of $G $ does not possess this property. We define $mathcal{R}_{min}(H_1, dots, H_t)$ to be the family of $(H_1, dots, H_t)$-Ramsey-minimal graphs. A graph $G$ is dfn{$mathcal{R}_{min}(H_1, dots, H_t)$-saturated} if no element of $mathcal{R}_{min}(H_1, dots, H_t)$ is a subgraph of $G$, but for any edge $e$ in $overline{G}$, some element of $mathcal{R}_{min}(H_1, dots, H_t)$ is a subgraph of $G + e$. We define $sat(n, mathcal{R}_{min}(H_1, dots, H_t))$ to be the minimum number of edges over all $mathcal{R}_{min}(H_1, dots, H_t)$-saturated graphs on $n$ vertices. In 1987, Hanson and Toft conjectured that $sat(n, mathcal{R}_{min}(K_{k_1}, dots, K_{k_t}) )= (r - 2)(n - r + 2)+binom{r - 2}{2} $ for $n ge r$, where $r=r(K_{k_1}, dots, K_{k_t})$ is the classical Ramsey number for complete graphs. The first non-trivial case of Hanson and Tofts conjecture for sufficiently large $n$ was setteled in 2011, and is so far the only settled case. Motivated by Hanson and Tofts conjecture, we study the minimum number of edges over all $mathcal{R}_{min}(K_3, mathcal{T}_k)$-saturated graphs on $n$ vertices, where $mathcal{T}_k$ is the family of all trees on $k$ vertices. We show that for $n ge 18$, $sat(n, mathcal{R}_{min}(K_3, mathcal{T}_4)) =lfloor {5n}/{2}rfloor$. For $k ge 5$ and $n ge 2k + (lceil k/2 rceil +1) lceil k/2 rceil -2$, we obtain an asymptotic bound for $sat(n, mathcal{R}_{min}(K_3, mathcal{T}_k))$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
