On factorable degree sequences

We call a degree sequence graphic (respectively, k-factorable, connected k-factorable) if there exists a graph (respectively, a graph with a k-factor, a graph with a connected k-factor) with the given degree sequence. In this paper we give a necessary and sufficient condition for a k-factorable sequence to be connected k-factorable when k ? 2. We also prove that every k-factorable sequence is (k − 2) factorable and 2-factorable, and also 1-factorable, when the sequence is of even length. Some conjectures are stated and it is also proved that, if {d_i} and {d_i − k} are graphic, then {d_i − r} is graphic for 0 ≤ r ≤ k provided rn is even.     

A note on properties of locally finitely convergent sequences with respect to median filter

Let F_k be a mapping from R^Z to R^Z, satisfying that for x∈R^Z and n∈Z, F_k(x)(n) is the (k+1)th largest value (median value) of the 2k+1 numbers x(n−k),…,x(n),…,x(n+k). In [3] [W.Z. Ye, L. Wang, L.G. Xu, Properties of locally convergent sequences with respect to median filter, Discrete Mathematics 309 (2009) 2775–2781], we conjectured that for k∈{2,3}, if there exists n₀∈Z such that x is locally finitely convergent with respect to F_k on {n₀,…,n₀+k−1}, then x is finitely convergent with respect to F_k. In this paper, we obtain some sufficient conditions for a sequence finitely converging with respect to median filters. Based on these results, we prove that the conjecture is true.     

On the modular sumset partition problem

A sequence m₁≥m₂≥?≥m_k of k positive integers isn-realizable if there is a partition X₁,X₂,…,X_k of the integer interval [1,n] such that the sum of the elements in X_i is m_i for each i=1,2,…,k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k≤(p−1)/2 are realizable for any prime p≥3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n≥(4k)³, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability.     

Behaving sequences

Let S be a sequence over an additively written abelian group. We denote by h(S) the maximum of the multiplicities of S, and by ∑(S) the set of all subsums of S. In this paper, we prove that if S has no zero-sum subsequence of length in [1,h(S)], then either |∑(S)|?2|S|−1, or S has a very special structure which implies in particular that ∑(S) is an interval. As easy consequences of this result, we deduce several well-known results on zero-sum sequences.     

Long cycles in 4-connected planar graphs

Let G be a 4-connected planar graph on n vertices. Malkevitch conjectured that if G contains a cycle of length 4, then G contains a cycle of length k for every k∈{n,n−1,…,3}. This conjecture is true for every k∈{n,n−1,…,n−6} with k≥3. In this paper, we prove that G also has a cycle of length n−7 provided n≥10.     

Sums and k-sums in abelian groups of order k

Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence a₁,…,ar that does not have 0 as a k-sum is attained at the sequence b₁,…,br−k+1,0,…,0, where b₁,…,br−k+1 is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value k−1 times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader.     

deBruijn-like sequences and the irregular chromatic number of paths and cycles

A deBruijn sequence of orderk, or a k-deBruijn sequence, over an alphabet A is a sequence of length |A|^k in which the last element is considered adjacent to the first and every possible k-tuple from A appears exactly once as a string of k-consecutive elements in the sequence. We will say that a cyclic sequence is deBruijn-like if for some k, each of the consecutive k-element substrings is distinct.A vertex coloring χ:V(G)→[k] of a graph G is said to be proper if no pair of adjacent vertices in G receive the same color. Let C(v;χ) denote the multiset of colors assigned by a coloring χ to the neighbors of vertex v. A proper coloring χ of G is irregular if χ(u)=χ(v) implies that C(u;χ)≠C(v;χ). The minimum number of colors needed to irregularly color G is called the irregular chromatic number of G. The notion of the irregular chromatic number pairs nicely with other parameters aimed at distinguishing the vertices of a graph. In this paper, we demonstrate a connection between the irregular chromatic number of cycles and the existence of certain deBruijn-like sequences. We then determine the exact irregular chromatic number of C_n and P_n for n≥3, thus verifying two conjectures given by Okamoto, Radcliffe and Zhang.     

Reduced limits for nonlinear equations with measures

We consider equations (E) −Δu+g(u)=μ in smooth bounded domains Ω⊂RN, where g is a continuous nondecreasing function and μ is a finite measure in Ω. Given a bounded sequence of measures (μk), assume that for each k?1 there exists a solution uk of (E) with datum μk and zero boundary data. We show that if uk→u# in L¹(Ω), then u# is a solution of (E) relative to some finite measure μ#. We call μ# the reduced limit of (μk). This reduced limit has the remarkable property that it does not depend on the boundary data, but only on (μk) and on g. For power nonlinearities g(t)=|t|^q−1t, ∀t∈R, we show that if (μk) is nonnegative and bounded in W−2,q(Ω), then μ and μ# are absolutely continuous with respect to each other; we then produce an example where μ#≠μ.     

On shortest crucial words avoiding abelian powers

Let k≥2 be an integer. An abeliankth power is a word of the form X₁X₂?X_k where X_i is a permutation of X₁ for 2≤i≤k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but Wx ends with an abelian kth power for any letter x occurring in W.Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4n−7 for n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−13 for n≥5. They have also conjectured that for any k≥4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ?_k(n), is k²n−(k²+k+1). This is currently the best known upper bound for ?_k(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1) for n≥5 and k≥4. In this note, we improve this lower bound by proving that for n≥2k−1, ?_k(n)≥k²n−(2k³−3k²+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.     

On the chromatic number of random d-regular graphs

In this work we show that, for any fixed d, random d-regular graphs asymptotically almost surely can be coloured with k colours, where k is the smallest integer satisfying d<2(k−1)log(k−1). From previous lower bounds due to Molloy and Reed, this establishes the chromatic number to be asymptotically almost surely k−1 or k. If moreover d>(2k−3)log(k−1), then the value k−1 is discarded and thus the chromatic number is exactly determined. Hence we improve a recently announced result by Achlioptas and Moore in which the chromatic number was allowed to take the value k+1. Our proof applies the small subgraph conditioning method to the number of equitable k-colourings, where a colouring is equitable if the number of vertices of each colour is equal.     

Geometric formulas for Smale invariants of codimension two immersions

We give three formulas expressing the Smale invariant of an immersion f of a (4k−1)-sphere into (4k+1)-space. The terms of the formulas are geometric characteristics of any generic smooth map g of any oriented 4k-dimensional manifold, where g restricted to the boundary is an immersion regularly homotopic to f in (6k−1)-space.The formulas imply that if f and g are two non-regularly homotopic immersions of a (4k−1)-sphere into (4k+1)-space then they are also non-regularly homotopic as immersions into (6k−1)-space. Moreover, any generic homotopy in (6k−1)-space connecting f to g must have at least a_k(2k−1)! cusps, where a_k=2 if k is odd and a_k=1 if k is even.     

Polynomial Cunningham chains

A sequence of prime numbers p₁,p₂,p₃,…, such that pi=2pi−1+? for all i, is called a Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the smallest positive integer such that 2pk+? is composite, then we say the chain has length k. It is conjectured that there are infinitely many Cunningham chains of length k for every positive integer k. A sequence of polynomials f₁(x),f₂(x),… in Z[x], such that f₁(x) has positive leading coefficient, each fi(x) is irreducible in Q[x] and fi(x)=xfi−1(x)+? for all i, is defined to be a polynomial Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the least positive integer such that fk+1(x) is reducible in Q[x], then we say the chain has length k. In this article, for polynomial Cunningham chains of both kinds, we prove that there are infinitely many chains of length k and, unlike the situation in the integers, that there are infinitely many chains of infinite length, by explicitly giving infinitely many polynomials f₁(x), such that fk+1(x) is the only term in the sequence that is reducible.     

Limit sets of automatic sequences

We show that for every k-automatic sequence there exists a natural number p>0 such that the sequences of the form (k^pn+j)_n?0 with j=0,…,p−1 are scaling sequences for f. Moreover, we demonstrate that every limit set is the union of certain basic limit sets.     

Representations of trigonometric Cherednik algebras of rank one in positive characteristic

In this paper, we classify the irreducible representations of the trigonometric Cherednik algebras of rank 1 in characteristic p>0. There are two cases. One is the “quantum” case, where “Planck’s constant” is nonzero and generic irreducible representations have dimension 2p. In this case, smaller representations exist if and only if the “coupling constant” k is in ; namely, if k is an even integer such that 0≤k≤p−1, then there exist irreducible representations of dimensions p−k and p+k, and if k is an odd integer such that 1≤k≤p−2, then there exist irreducible representations of dimensions k and 2p−k. The other case is the “classical” case, where “Planck’s constant” is zero and generic irreducible representations have dimension 2. In that case, one-dimensional representations exist if and only if the “coupling constant” k is zero.     

Colourings of graphs with two consecutive odd cycle lengths

In 1992 Gyárfás showed that a graph G having only k odd cycle lengths is (2k+1)-colourable, if it does not contain a K_2k+2. In this paper, we will present the results for graphs containing only odd cycles of length 2m−1 and 2m+1 as done in [S. Matos Camacho, Colourings of graph with prescribed cycle lengths, diploma thesis, TU Bergakademie Freiberg, 2006. [3]]. We will show that these graphs are 4-colourable.     

The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x,y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2 so that D contains a spanning strong subdigraph with at most 2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n^c) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2n−2−k arcs.We furthermore prove that if k≥1 and D has no cut vertex then it has a kernel of order at most (2k−1)². We finally discuss related problems and conjectures.     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

Linear recurrence relations for binomial coefficients modulo a prime

We investigate when the sequence of binomial coefficients modulo a prime p, for a fixed positive integer k, satisfies a linear recurrence relation of (positive) degree h in the finite range 0?i?k. In particular, we prove that this cannot occur if 2h?k<p−h. This hypothesis can be weakened to 2h?k<p if we assume, in addition, that the characteristic polynomial of the relation does not have −1 as a root. We apply our results to recover a known bound for the number of points of a Fermat curve over a finite field.     

Second order asymptotic behaviour of subordinated sequences with longtailed subordinator

Suppose that {a(n)} is a discrete probability distribution on the set N₀={0,1,2,…} and {p(n)} is some non-negative sequence defined on the same set. The equation defines a new sequence {b(n)}. Here {a*k(n)} denotes the k-fold convolution of the distribution {a(n)}. In the paper the asymptotic behaviour of the sequence {b(n)} is investigated. It is known that for the large classes of the sequences {a(n)} and {p(n)}, b(n)∼σp([σn]), where 1/σ is the mean of the distribution {a(n)}. The main object of the present work is to estimate the difference b(n)−σp([σn]) for some classes of the sequences {a(n)} and {p(n)}.