A pattern sequence approach to Stern’s sequence

Suppose that w∈1{0,1}^∗ and let a_w(n) be the number of occurrences of the word w in the binary expansion of n. Let {s(n)}_n?0 denote the Stern sequence, defined by s(0)=0, s(1)=1, and for n?1, In this note, we show that where denotes the complement of w (obtained by sending 0?1 and 1?0) and [w]₂ denotes the integer specified by the word w∈{0,1}^∗ interpreted in base 2.     

Coquet-type formulas for the rarefied weighted Thue–Morse sequence

Newman proved for the classical Thue–Morse sequence, ((−1)^s(n))_n≥0, that for all N∈N with real constants satisfying c₂>c₁>0 and λ=log3/log4. Coquet improved this result and deduced , where F(x) is a nowhere-differentiable, continuous function with period 1 and η(N)∈{−1,0,1}. In this paper we obtain for the weighted version of the Thue–Morse sequence that for the sum a Coquet-type formula exists for every r∈{0,1,2} if and only if the sequence of weights is eventually periodic. From the specific Coquet-type formulas we derive parts of the weak Newman-type results that were recently obtained by Larcher and Zellinger.     

On affine difference sets and their multipliers

Let D be an affine difference set of order n in an abelian group G relative to a subgroup N. We denote by π(s) the set of primes dividing an integer and set H^∗=H?{ω}, where H=G/N and ω=∏_σ∈Hσ. In this article, using D we define a map g from H to N satisfying for iff {τ,τ⁻¹}={ρ,ρ⁻¹} and show that for any σ∈H^∗ and any integer m>0 with π(m)⊂π(n). This result is a generalization of J.C. Galati’s theorem on even order n [J.C. Galati, A group extensions approach to affine relative difference sets of even order, Discrete Mathematics 306 (2006) 42-51] and gives a new proof of a result of Arasu-Pott on the order of a multiplier modulo exp(H) ([K.T. Arasu, A. Pott, On quasi-regular collineation groups of projective planes, Designs Codes and Cryptography 1 (1991) 83-92] Section 5).     

Global stability of some symmetric difference equations

Suppose r∈(0,1],m∈N and 1?k₁<k₂<?<k_2m+1, and let S_2m+1={1,2,…,2m+1}. We show that every positive solution to the difference equation

     

On signed cycle domination in graphs

Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑_e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures.     

Sequences of integers with missing quotients

Let S be any set of natural numbers, and A be a given set of rational numbers. We say that S is an A-quotient-free set if x,y∈S implies y/x∉A. Let and , where the supremum is taken over all A-quotient-free sets S, and are the upper and lower asymptotic densities of S respectively. Let ρ(A)=sup_Sδ(S), where the supremum is taken over all A-quotient-free sets S such that δ(S) exists. In this paper we study the properties of , and ρ(A).     

Subordination results for classes of analytic functions related to conic domains defined by a fractional operator

Let a fractional operator (n∈N₀={0,1,2,…}, 0?α<1, λ?0) be defined by

     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

Quasi-convex sequences in the circle and the 3-adic integers

In this paper, we present families of quasi-convex sequences converging to zero in the circle group T, and the group J₃ of 3-adic integers. These sequences are determined by increasing sequences of integers. For an increasing sequence , put gn=an+1−an. We prove that

(a)

the set {0}∪{±³−(an+1)|n∈N} is quasi-convex in T if and only if a₀>0 and gn>1 for every n∈N;

(b)

the set {0}∪{±an³|n∈N} is quasi-convex in the group J₃ of 3-adic integers if and only if gn>1 for every n∈N.

Moreover, we solve an open problem from [D. Dikranjan, L. de Leo, Countably infinite quasi-convex sets in some locally compact abelian groups, Topology Appl. 157 (8) (2010) 1347-1356] providing a complete characterization of the sequences such that {0}∪{±²−(an+1)|n∈N} is quasi-convex in T. Using this result, we also obtain a characterization of the sequences such that the set {0}∪{±²−(an+1)|n∈N} is quasi-convex in R.     

Posets of annular non-crossing partitions of types B and D

We study the set of annular non-crossing permutations of type B, and we introduce a corresponding set of annular non-crossing partitions of type B, where p and q are two positive integers. We prove that the natural bijection between and is a poset isomorphism, where the partial order on is induced from the hyperoctahedral group B_p+q, while is partially ordered by reverse refinement. In the case when q=1, we prove that is a lattice with respect to reverse refinement order.We point out that an analogous development can be pursued in type D, where one gets a canonical isomorphism between and . For q=1, the poset coincides with a poset “NC^(D)(p+1)” constructed in a paper by Athanasiadis and Reiner [C.A. Athanasiadis, V. Reiner, Noncrossing partitions for the group D_n, SIAM Journal of Discrete Mathematics 18 (2004) 397-417], and is a lattice by the results of that paper.     

Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P⊆R² and a positive real d, a unit disk graph, denoted by (P,d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by where . Let T_m,n(d) be a unit disk graph defined on a vertex set P(m,n) and a positive real d. Let be the kth power of T_m,n(1).In this paper, we show necessary and sufficient conditions that [ is perfect] and/or [ is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T_m,n(d),w) and .     

A tripling construction for overlarge sets of KTS

An overlarge set of , denoted by , is a collection {(X?{x},B_x):x∈X}, where X is a (v+1)-set, each (X?{x},B_x) is a and {B_x:x∈X} forms a partition of all triples on X. In this paper, we give a tripling construction for overlarge sets of KTS. Our main result is that: If there exists an with a special property, then there exists an . It is obtained that there exists an for u=2²ⁿ⁻¹−1 or u=qⁿ, where prime power q≡7 (mod 12) and m≥0,n≥1.     

On classes of analytic functions related to conic domains

We introduce classes of analytic functions related to conic domains, using a new linear multiplier fractional differential operator (n∈N₀={0,1,…}, 0?α<1, λ?0), which is defined as

D⁰f(z)=f(z),     

How to play the Majority game with a liar

The Majority game is played by a questioner () and an answerer (). holds n elements, each of which can be labeled as 0 or 1. is trying to identify some element holds as having the Majority label or, in the case of a tie, claim there is none. To do this asks questions comparing whether two elements have the same or different label. ’s goal is to ask as few questions as possible while ’s goal is to delay as much as possible. Let q^∗ denote the minimal number of questions needed for to identify a Majority element regardless of ’s answers.In this paper we investigate upper and lower bounds for q^∗ in a variation of the Majority game, where is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).     

Rearrangement of conditionally convergent series on a small set

We consider ideals I of subsets of the set of natural numbers such that for every conditionally convergent series _∑n∈ωan and every there is a permutation such that _∑n∈ωaπr(n)=r and

     

General neighbour-distinguishing index via chromatic number

An edge colouring of a graph G without isolated edges is neighbour-distinguishing if any two adjacent vertices have distinct sets consisting of colours of their incident edges. The general neighbour-distinguishing index of G is the minimum number of colours in a neighbour-distinguishing edge colouring of G. Gy?ri et al. [E. Gy?ri, M. Horňák, C. Palmer, M. Wo?niak, General neighbour-distinguishing index of a graph, Discrete Math. 308 (2008) 827-831] proved that provided G is bipartite and gave a complete characterisation of bipartite graphs according to their general neighbour-distinguishing index. The aim of this paper is to prove that if χ(G)≥3, then . Therefore, if log₂χ(G)∉Z, then .     

Forbidden configurations and repeated induction

For a given k×? matrix F, we say a matrix A has no configurationF if no k×? submatrix of A is a row and column permutation of F. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define as the maximum number of columns in an m-rowed simple matrix which has no configuration F. A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines exactly, where K_k denotes the k×2^k simple matrix. We extend this in several ways. For two matrices G,H on the same number of rows, let [G∣H] denote the concatenation of G and H. Our first two sets of results are exact bounds that find some matrices B,C where and . Our final result provides asymptotic boundary cases; namely matrices F for which is O(m^p) yet for any choice of column α not in F, we have is Ω(m^p+1). This is evidence for a conjecture of Anstee and Sali. The proof techniques in this paper are dominated by repeated use of the standard induction employed in forbidden configurations. Analysis of base cases tends to dominate the arguments. For a k-rowed (0,1)-matrix F, we also consider a function which is the minimum number of columns in an m-rowed simple matrix for which each k-set of rows contains F as a configuration.     

Haj?asz-Sobolev imbedding and extension

The author establishes some geometric criteria for a Haj?asz-Sobolev -extension (resp. -imbedding) domain of Rn with n?2, s∈(0,1] and p∈[n/s,∞] (resp. p∈(n/s,∞]). In particular, the author proves that a bounded finitely connected planar domain Ω is a weak α-cigar domain with α∈(0,1) if and only if for some/all s∈[α,1) and p=(2−α)/(s−α), where denotes the restriction of the Triebel-Lizorkin space on Ω.