اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMore Kolakoski Sequences
69
0
0.0
(
0
)
تأليف
Bernd Sing
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Our goal in this article is to review the known properties of the mysterious Kolakoski sequence and at the same time look at generalizations of it over arbitrary two letter alphabets. Our primary focus will here be the case where one of the letters is odd while the other is even, since in the other cases the sequences in question can be rewritten as (well-known) primitive substitution sequences. We will look at word and letter frequencies, squares, palindromes and complexity.
قيم البحث
اقرأ أيضاً
Given a set of integers with no three in arithmetic progression, we construct a Stanley sequence by adding integers greedily so that no arithmetic progression is formed. This paper offers two main contributions to the theory of Stanley sequences. Fir
st, we characterize well-structured Stanley sequences as solutions to constraints in modular arithmetic, defining the modular Stanley sequences. Second, we introduce the basic Stanley sequences, where elements arise as the sums of subsets of a basis sequence, which in the simplest case is the powers of 3. Applications of our results include the construction of Stanley sequences with arbitrarily large gaps between terms, answering a weak version of a problem by ErdH{o}s et al. Finally, we generalize many results about Stanley sequences to $p$-free sequences, where $p$ is any odd prime.
Given a set of integers containing no 3-term arithmetic progressions, one constructs a Stanley sequence by choosing integers greedily without forming such a progression. Independent Stanley sequences are a well-structured class of Stanley sequences w
ith two main parameters: the character $lambda(A)$ and the repeat factor $rho(A)$. Rolnick conjectured that for every $lambda in mathbb{N}_0backslash{1, 3, 5, 9, 11, 15}$, there exists an independent Stanley sequence $S(A)$ such that $lambda(A) =lambda$. This paper demonstrates that $lambda(A) otin {1, 3, 5, 9, 11, 15}$ for any independent Stanley sequence $S(A)$.
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is quasirandom; such pairs (H_1,H_2) are called forcing. Non-bipartite forcing pairs were first discove
red by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), 1-38]: they showed that (K_t,F) is forcing where F is the graph that arises from K_t by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma 7, 2019] strengthened this result for t=3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t>3. We show that (t+2)/2 doublings always suffice.
In this paper we demonstrate connections between three seemingly unrelated concepts. (1) The discrete isoperimetric problem in the infinite binary tree with all the leaves at the same level, $ {mathcal T}_{infty}$: The $n$-th edge isoperimetric n
umber $delta(n)$ is defined to be $min_{|S|=n, S subset V({mathcal T}_{infty})} |(S,bar{S})|$, where $(S,bar{S})$ is the set of edges in the cut defined by $S$. (2) Signed almost binary partitions: This is the special case of the coin-changing problem where the coins are drawn from the set ${pm (2^d - 1): $d$ is a positive integer}$. The quantity of interest is $tau(n)$, the minimum number of coins necessary to make change for $n$ cents. (3) Certain Meta-Fibonacci sequences: The Tanny sequence is defined by $T(n)=T(n{-}1{-}T(n{-}1))+T(n{-}2{-}T(n{-}2))$ and the Conolly sequence is defined by $C(n)=C(n{-}C(n{-}1))+C(n{-}1{-}C(n{-}2))$, where the initial conditions are $T(1) = C(1) = T(2) = C(2) = 1$. These are well-known meta-Fibonacci sequences. The main result that ties these three together is the following: $$ delta(n) = tau(n) = n+ 2 + 2 min_{1 le k le n} (C(k) - T(n-k) - k).$$ Apart from this, we prove several other results which bring out the interconnections between the above three concepts.
Let $pi_1=(d_1^{(1)}, ldots,d_n^{(1)})$ and $pi_2=(d_1^{(2)},ldots,d_n^{(2)})$ be graphic sequences. We say they emph{pack} if there exist edge-disjoint realizations $G_1$ and $G_2$ of $pi_1$ and $pi_2$, respectively, on vertex set ${v_1,dots,v_n}$ s
uch that for $jin{1,2}$, $d_{G_j}(v_i)=d_i^{(j)}$ for all $iin{1,ldots,n}$. In this case, we say that $(G_1,G_2)$ is a $(pi_1,pi_2)$-textit{packing}. A clear necessary condition for graphic sequences $pi_1$ and $pi_2$ to pack is that $pi_1+pi_2$, their componentwise sum, is also graphic. It is known, however, that this condition is not sufficient, and furthermore that the general problem of determining if two sequences pack is $NP$- complete. S.~Kundu proved in 1973 that if $pi_2$ is almost regular, that is each element is from ${k-1, k}$, then $pi_1$ and $pi_2$ pack if and only if $pi_1+pi_2$ is graphic. In this paper we will consider graphic sequences $pi$ with the property that $pi+mathbf{1}$ is graphic. By Kundus theorem, the sequences $pi$ and $mathbf{1}$ pack, and there exist edge-disjoint realizations $G$ and $mathcal{I}$, where $mathcal{I}$ is a 1-factor. We call such a $(pi,mathbf{1})$ packing a {em Kundu realization}. Assume that $pi$ is a graphic sequence, in which each term is at most $n/24$, that packs with $mathbf{1}$. This paper contains two results. On one hand, any two Kundu realizations of the degree sequence $pi+mathbf{1}$ can be transformed into each other through a sequence of other Kundu realizations by swap operations. On the other hand, the same conditions ensure that any particular 1-factor can be part of a Kundu realization of $pi+mathbf{1}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
