Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNovel structures in Stanley sequences
144
0
0.0
(
0
)
Added by
David Rolnick
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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. First, 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.
rate research
Read More
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 with 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 prove that the uniform recurrence of morphic sequences is decidable. For this we show that the number of derived sequences of uniformly recurrent morphic sequences is bounded. As a corollary we obtain that uniformly recurrent morphic sequences are primitive substitutive sequences.
Recently, Yan and the first named author investigated systematically the enumeration of inversion or ascent sequences avoiding vincular patterns of length $3$, where two of the three letters are required to be adjacent. They established many connections with familiar combinatorial families and proposed several interesting conjectures. The objective of this paper is to address two of their conjectures concerning the enumeration of $underline{12}0$-avoiding inversion or ascent sequences.
In network modeling of complex systems one is often required to sample random realizations of networks that obey a given set of constraints, usually in form of graph measures. A much studied class of problems targets uniform sampling of simple graphs with given degree sequence or also with given degree correlations expressed in the form of a joint degree matrix. One approach is to use Markov chains based on edge switches (swaps) that preserve the constraints, are irreducible (ergodic) and fast mixing. In 1999, Kannan, Tetali and Vempala (KTV) proposed a simple swap Markov chain for sampling graphs with given degree sequence and conjectured that it mixes rapidly (in poly-time) for arbitrary degree sequences. While the conjecture is still open, it was proven for special degree sequences, in particular, for those of undirected and directed regular simple graphs, of half-regular bipartite graphs, and of graphs with certain bounded maximum degrees. Here we prove the fast mixing KTV conjecture for novel, exponentially large classes of irregular degree sequences. Our method is based on a canonical decomposition of degree sequences into split graph degree sequences, a structural theorem for the space of graph realizations and on a factorization theorem for Markov chains. After introducing bipartite splitted degree sequences, we also generalize the canonical split graph decomposition for bipartite and directed graphs.
Given a finite set of nonnegative integers A with no 3-term arithmetic progressions, the Stanley sequence generated by A, denoted S(A), is the infinite set created by beginning with A and then greedily including strictly larger integers which do not introduce a 3-term arithmetic progressions in S(A). Erdos et al. asked whether the counting function, S(A,x), of a Stanley sequence S(A) satisfies S(A,x)>x^{1/2-epsilon} for every epsilon>0 and x>x_0(epsilon,A). In this paper we answer this question in the affirmative; in fact, we prove the slightly stronger result that S(A,x)geq (sqrt{2}-epsilon)sqrt{x} for xgeq x_0(epsilon,A).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
