اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRamsey Properties for $V$-shaped Posets in the Boolean Lattices
74
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 sma
llest $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$.
In 1964, ErdH{o}s, Hajnal and Moon introduced a saturation version of Turans classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition
of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the ErdH{o}s-Szekeres theorem about monotone subsequences and saturati
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 o
f $[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)$.
In this note we study and obtain factorization theorems for colorings of matrices and Grassmannians over $mathbb{R}$ and ${mathbb{C}}$, which can be considered metr
Motivated by generalizing Khovanovs categorification of the Jones polynomial, we study functors $F$ from thin posets $P$ to abelian categories $mathcal{A}$. Such functors $F$ produce cohomology theories $H^*(P,mathcal{A},F)$. We find that CW posets,
that is, face posets of regular CW complexes, satisfy conditions making them particularly suitable for the construction of such cohomology theories. We consider a category of tuples $(P,mathcal{A},F,c)$, where $c$ is a certain ${1,-1}$-coloring of the cover relations in $P$, and show the cohomology arising from a tuple $(P,mathcal{A},F,c)$ is functorial, and independent of the coloring $c$ up to natural isomorphism. Such a construction provides a framework for the categorification of a variety of familiar topological/combinatorial invariants: anything expressible as a rank-alternating sum over a thin poset.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
