اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Ramsey Characterisation of Eventually Periodic Words
45
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A factorisation $x = u_1 u_2 cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic, for a given colouring of the finite words $X^*$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramseys theorem that, for textit{any} word $x$, for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation.par A factorisation $x = u_1 u_2 cdots$ is called `super-monochromatic if each word $u_{k_1} u_{k_2} cdots u_{k_n}$, where $k_1 < cdots < k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest.
قيم البحث
اقرأ أيضاً
We define a new class of shift spaces which contains a number of classes of interest, like Sturmian shifts used in discrete geometry. We show that this class is closed under two natural transformations. The first one is called conjugacy and is obtain
ed by sliding block coding. The second one is called the complete bifix decoding, and typically includes codings by non overlapping blocks of fixed length.
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)$.
We extend results regarding a combinatorial model introduced by Black, Drellich, and Tymoczko (2017+) which generalizes the folding of the RNA molecule in biology. Consider a word on alphabet ${A_1, overline{A}_1, ldots, A_m, overline{A}_m}$ in which
$overline{A}_i$ is called the complement of $A_i$. A word $w$ is foldable if can be wrapped around a rooted plane tree $T$, starting at the root and working counterclockwise such that one letter labels each half edge and the two letters labeling the same edge are complements. The tree $T$ is called $w$-valid. We define a bijection between edge-colored plane trees and words folded onto trees. This bijection is used to characterize and enumerate words for which there is only one valid tree. We follow up with a characterization of words for which there exist exactly two valid trees. In addition, we examine the set $mathcal{R}(n,m)$ consisting of all integers $k$ for which there exists a word of length $2n$ with exactly $k$ valid trees. Black, Drellich, and Tymoczko showed that for the $n$th Catalan number $C_n$, ${C_n,C_{n-1}}subset mathcal{R}(n,1)$ but $k otinmathcal{R}(n,1)$ for $C_{n-1}<k<C_n$. We describe a superset of $mathcal{R}(n,1)$ in terms of the Catalan numbers by which we establish more missing intervals. We also prove $mathcal{R}(n,1)$ contains all non-negative integer less than $n+1$.
A new hierarchy of operads over the linear spans of $delta$-cliffs, which are some words of integers, is introduced. These operads are intended to be analogues of the operad of permutations, also known as the associative symmetric operad. We obtain o
perads whose partial compositions can be described in terms of intervals of the lattice of $delta$-cliffs. These operads are very peculiar in the world of the combinatorial operads since, despite to the relative simplicity for their construction, they are infinitely generated and they have nonquadratic and nonhomogeneous nontrivial relations. We provide a general construction for some of their quotients. We use it to endow the spaces of permutations, $m$-increasing trees, $c$-rectangular paths, and $m$-Dyck paths with operad structures. The operads on $c$-rectangular paths admit, as Koszul duals, operads generalizing the duplicial and triplicial operads.
In a series of papers and in his 2009 book on configurations Branko Grunbaum described a sequence of operations to produce new $(n_{4})$ configurations from various input configurations. These operations were later called the Grunbaum Incidence Calcu
lus. We generalize two of these operations to produce operations on arbitrary $(n_{k})$ configurations. Using them, we show that for any $k$ there exists an integer $N_k$ such that for any $n geq N_k$ there exists a geometric $(n_k)$ configuration. We use empirical results for $k = 2, 3, 4$, and some more detailed analysis to improve the upper bound for larger values of $k$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
