Fici et al. defined a word to be a k-power if it is the concatenation of k consecutive identical blocks, and an r-antipower if it is the concatenation of r pairwise distinct blocks of the same size. They defined N(k, ...
详细信息
Fici et al. defined a word to be a k-power if it is the concatenation of k consecutive identical blocks, and an r-antipower if it is the concatenation of r pairwise distinct blocks of the same size. They defined N(k, r) as the smallest l such that every binary word of length l contains either a k-power or an r-antipower. In this note we obtain some new upper and lower bounds on N(k, r). We also consider avoiding 3-antipowers and 4-antipowers over larger alphabets, and obtain a lower bound for N(k, 5) in the binary case. (C) 2020 Elsevier B.V. All rights reserved.
The non-uniform dispersion process on the infinite integer line is a synchronous process where n particles are placed at the origin initially, and any particle not exclusively occupying an integer site will move at th...
详细信息
The non-uniform dispersion process on the infinite integer line is a synchronous process where n particles are placed at the origin initially, and any particle not exclusively occupying an integer site will move at the next time step to the right adjacent integer with probability p(n) and to the left with probability 1 - p(n) independently. We characterize the longest distance from the origin when the dispersion process stops, which is shown to be Theta(n) with high probability for fairly general P-n. (C) 2020 Elsevier B.V. All rights reserved.
A de Bruijn sequence of order n over a k-symbol alphabet is a circular sequence where each length -n sequence occurs exactly once. We present a way of extending de Bruijn sequences by adding a new symbol to the alphab...
详细信息
A de Bruijn sequence of order n over a k-symbol alphabet is a circular sequence where each length -n sequence occurs exactly once. We present a way of extending de Bruijn sequences by adding a new symbol to the alphabet: the extension is performed by embedding a given de Bruijn sequence into another one of the same order, but over the alphabet with one more symbol, while ensuring that there are no long runs without the new symbol. Our solution is based on auxiliary graphs derived from the de Bruijn graph and solving a problem of maximum flow. (C) 2020 Elsevier B.V. All rights reserved.
For all k >= 1, we show that deciding whether a graph is k-planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show that the gap version of this decision p...
详细信息
For all k >= 1, we show that deciding whether a graph is k-planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show that the gap version of this decision problem is NP-complete. In particular, given a graph with local crossing number either at most k >= 1 or at least 2k, we show that it is NP-complete to decide whether the local crossing number is at most k or at least 2k. This algorithmic lower bound proves the non-existence of a (2 - epsilon)-approximation algorithm for any fixed k >= 1. In addition, we analyze the sometimes competing relationship between the local crossing number (maximum number of crossings per edge) and crossing number (total number of crossings) of a drawing. We present results regarding the non-existence of drawings that simultaneously approximately minimize both the local crossing number and crossing number of a graph. (C) 2020 Published by Elsevier B.V.
In 1996, Neville Robbins proved the amazing fact that the coefficient of X-n in the Fibonacci infinite product Pi(n >= 2) (1 - X-Fn ) = (1 -X)(1 -X-2)(1 -X-3)(1 -X-5)(1 -X-8) ... = 1 - X - X-2 + X-4 + ... is always...
详细信息
In 1996, Neville Robbins proved the amazing fact that the coefficient of X-n in the Fibonacci infinite product Pi(n >= 2) (1 - X-Fn ) = (1 -X)(1 -X-2)(1 -X-3)(1 -X-5)(1 -X-8) ... = 1 - X - X-2 + X-4 + ... is always either -1, 0, or 1. The same result was proved later by Federico Ardila using a different method. Meanwhile, in 2001, Jean Berstel gave a simple 4-state transducer that converts an "illegal" Fibonacci representation into a "legal" one. I show how to obtain the Robbins-Ardila result from Berstel's with almost no work at all, using purely computational techniques that can be performed by existing software. (C) 2020 Elsevier B.V. All rights reserved.
In the coupon collector's problem with group drawings, a collector buys independent, identically distributed subsets of fixed size s >= 2 out of a totality of ncoupons. Let W-n,W-s denote the number of such sub...
详细信息
In the coupon collector's problem with group drawings, a collector buys independent, identically distributed subsets of fixed size s >= 2 out of a totality of ncoupons. Let W-n,W-s denote the number of such subsets necessary to obtain each coupon at least once. We prove that, among all distributions that act on the class of all ((n)(s)) subsets of size sof the coupons, the uniform distribution minimizes the expectation of W-n,W-s if s = n - 1. However, if 3 <= s <= 100 and s + 2 <= n <= 500, computer algebra shows that the uniform distribution does not minimize E(W-n,W-s). We conjecture that the latter property holds for each s >= 3 and each n >= s + 2. (c) 2021 Elsevier B.V. All rights reserved.
A subset S of vertices in a graph G with vertex set V and edge set E is a dominating set of G if every vertex of V \ S is adjacent to a vertex in S. The minimum cardinality of a dominating set is the dominating number...
详细信息
A subset S of vertices in a graph G with vertex set V and edge set E is a dominating set of G if every vertex of V \ S is adjacent to a vertex in S. The minimum cardinality of a dominating set is the dominating number gamma (G) of G. G is a 3-gamma-critical graph if gamma (G) = 3 and gamma (G + e) <= 2 for e is not an element of E;G is bicritical if G - u - v contains a perfect matching for every pair of distinct vertices u, v is an element of V. In this paper, we characterize 3-connected 3-gamma-critical graphs G of even order which are not bicritical: two classes of graphs, which generalizes the result: if the minimum degree of G is at least 4, then G is bicritical N. Ananchuen and M.D. Plummer (2014) [2]. (C) 2020 Elsevier B.V. All rights reserved.
We show that the number of length-n words over a k-letter alphabet having no even palindromic prefix is the same as the number of length-n unbordered words, by constructing an explicit bijection between the two sets. ...
详细信息
We show that the number of length-n words over a k-letter alphabet having no even palindromic prefix is the same as the number of length-n unbordered words, by constructing an explicit bijection between the two sets. A slightly different but analogous result holds for those words having no odd palindromic prefix. Using known results on borders, we get an asymptotic enumeration for the number of words having no even (resp., odd) palindromic prefix. We obtain an analogous result for words having no nontrivial palindromic prefix. Finally, we obtain similar results for words having no square prefix, thus proving a 2013 conjecture of Chaffin, Linderman, Sloane, and Wilks. (C) 2020 Elsevier B.V. All rights reserved.
If the bisection width of a 2-connected graph G of even order n is not less than n/2, i.e., if the graph satisfies the even cut condition, then G has at least 3n/2 - 2 edges. Here we characterize the 2-connected extre...
详细信息
If the bisection width of a 2-connected graph G of even order n is not less than n/2, i.e., if the graph satisfies the even cut condition, then G has at least 3n/2 - 2 edges. Here we characterize the 2-connected extremal graphs with 3n/2 - 2 edges for every n >= 4. For n >= 10 an extremal graph has two high-degree vertices, the other vertices have degree 2 and they are located on paths suspended between these poles. (C) 2020 Elsevier B.V. All rights reserved.
Pattern avoiding machines were introduced recently by Claesson, Cerbai and Ferrari as a particular case of the two-stacks in series sorting device. They consist of two restricted stacks in series, ruled by a right-gre...
详细信息
Pattern avoiding machines were introduced recently by Claesson, Cerbai and Ferrari as a particular case of the two-stacks in series sorting device. They consist of two restricted stacks in series, ruled by a right-greedy procedure and the stacks avoid some specified patterns. Some of the obtained results have been further generalized to Cayley permutations by Cerbai, specialized to particular patterns by Defant and Zheng, or considered in the context of functions over the symmetric group by Berlow. In this work we study pattern avoiding machines where the first stack avoids a pair of patterns of length 3 and investigate those pairs for which sortable permutations are counted by the (binomial transform of the) Catalan numbers and the Schroder numbers. (C) 2021 Published by Elsevier B.V.
暂无评论